Appearance
归纳总结
- 临界点分析
名词记录
- 回文 Palindrome
刷题路径
以下是算法面试中高频出现的经典题目，涵盖基础数据结构、常见算法思想，适合面试前重点复习：
一、数组与字符串
- 两数之和
- 最长回文子串（中心扩展法或动态规划）。
- 盛最多水的容器
- 三数之和
- 字符串转换整数 (atoi)处理边界、符号、溢出问题。
二、链表
- 反转链表
- 环形链表
- 合并两个有序链表
- 删除链表的倒数第 N 个结点
- 两两交换链表中的节点
三、树与图
- 二叉树的层序遍历
- 二叉树的前/中/后序遍历
- 二叉树的最大深度
- 路径总和
- 二叉搜索树的最近公共祖先
- 岛屿数量
四、动态规划
- 爬楼梯
- 最长递增子序列
- 最长公共子序列
- 零钱兑换
- 编辑距离
五、排序与查找
- 二分查找
- 合并区间
- 快速排序/归并排序
六、其他经典题
- LRU 缓存
- 全排列
- 括号生成
- 接雨水
- 最小栈
复习建议
- 优先掌握 双指针、递归/回溯、动态规划、BFS/DFS 等核心思想。
- 同一题目尝试多种解法（如递归 vs 迭代），理解时间/空间复杂度差异。
- 手写代码时注意边界条件（如空输入、单元素、溢出等）。
这些题目覆盖了面试中 80%以上的算法考点，熟练掌握后可应对大部分场景。
prompt
算法题：4. 三数之和
1. 打印题目
2. 使用golang解题
3. 使用多种思路解题，并分析
4. 总结和归纳经验
5. 使用 golang的表驱动测试，这样一个题目才有多个数据验证是否正确
6. 贴出leetcode 传送门地址
7. 结合代码逐步讲解
8. 代码太精简了不方便理解，写细致点💡 动态规划的本质：
一句话：用空间换时间，把重复的子问题结果保存下来，避免重复计算。
比喻：你在迷宫里走路，每次都会经过一些相同的点。你把“从起点到这个点的最短路径”记下来，下次再路过这个点，就不用重新走一遍试错，直接拿答案！
✅ 动态规划的 5 步通用套路（背熟）：
明确状态（State）
- 定义 dp[i] 表示什么？是子问题的哪种最优解？
确定选择（Decision）
- 当前状态可以从哪些状态转移过来？
写出状态转移方程（Transition Function）
- 例如：
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
- 例如：
确定初始值（Base Case）
- 比如 dp[0] = 0，dp[1] = cost[0]
自底向上求解（迭代 or 记忆化递归）
- 最后拿 dp[n] 或 dp[n-1] 返回结果
🧠 必须掌握的 3 大动态规划类型（+例题讲解）
🍭 1. 线性 DP —— 一条路往前走
📌 典型问题：爬楼梯、最小花费爬楼梯、打家劫舍
🌰 示例一：爬楼梯（Climbing Stairs）
每次可以爬 1 步或 2 步，有多少种方式爬到第 n 阶？
- 状态：
dp[i]表示到第 i 阶的方法数 - 转移：
dp[i] = dp[i-1] + dp[i-2] - 初始：
dp[0]=1,dp[1]=1 - 递推：自底向上求
dp[n]
这就是经典的“斐波那契变体”。
🔒 2. 区间 DP —— 区间上的最优划分问题
📌 典型问题：戳气球、矩阵连乘、回文子串划分
🌰 示例二：戳气球（Burst Balloons）
气球排一排，每戳一个气球能获得一定分数，求最大得分。
状态：
dp[i][j]表示戳爆区间 (i, j) 的最大得分转移：尝试在 (i,j) 之间选择一个气球
k作为最后戳爆的pythondp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])初始值：长度为 1 的区间为 0
结果：
dp[0][n+1]
这类 DP 是两层循环的升级，关键在区间的顺序、枚举方式。
🎒 3. 背包型 DP —— 选择物品填容量
📌 典型问题：0-1 背包、完全背包、分割等和
🌰 示例三：0-1 背包问题（经典）
给你 n 个物品，每个有重量 w 和价值 v，背包容量为 C，最大价值多少？
状态：
dp[i][j]表示前 i 个物品，在容量 j 下的最大价值转移：
- 不选第 i 个：
dp[i][j] = dp[i-1][j] - 选第 i 个：
dp[i][j] = dp[i-1][j-w[i]] + v[i] - 综合：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
- 不选第 i 个：
初始值：
dp[0][*] = 0
注意背包类问题的“状态”和“容量”双维度。
🚨 动态规划的常见坑点
- 没定义清楚状态（搞不懂 dp[i] 是什么）
- 转移方程写错（状态之间关系理不清）
- 递推顺序错了（二维 DP 时特别容易炸）
- 空间可以优化没优化（线性 DP 可以滚动数组）
- 暴力递归写太多（记忆化搜索不如直接自底向上）
🧪 拓展例子：
🌰 示例四：最长递增子序列（LIS）
dp[i]表示以第 i 个结尾的最长递增子序列长度- 状态转移：
dp[i] = max(dp[j] + 1)，j < i 且 nums[j] < nums[i] - 初始值：
dp[*] = 1 - 最终答案：max(dp)
📦 总结金句：
动态规划不是魔法，它就是穷举 + 记忆的高级形式。只要你能定义“子问题”并想清楚“子问题怎么转移”，那就是 DP 的地盘。
稳住，骚年。你现在已经掌握了 DP 的框架 + 典型题型 + 3 套例子。如果你要我帮你“某题手把手过一遍”，直接贴题我就安排。
要刷题的话，推荐从这几题下手热身：
- LeetCode 70. Climbing Stairs
- LeetCode 198. House Robber
- LeetCode 322. Coin Change
- LeetCode 300. Longest Increasing Subsequence
- LeetCode 221. Maximal Square