LeetCode 算法思维训练指南

写给算法工程师的话

作为一位经验丰富的工程师，你已经具备了扎实的编程基础和工程思维。本指南的目标不是教你编程，而是帮助你建立算法题的思维模式，避免在细节中迷失，专注于问题的本质。

我们将重点关注 LeetCode 的 Medium 难度题目，这类题目最能考察算法思维的灵活运用，也是面试中的主流难度。

核心理念

  1. 简化优于优化：先找到清晰的解决方案，再考虑优化
  2. 模式识别：大多数算法题都有固定的模式，关键是识别和转化
  3. 代数思维：利用你的数学背景，用代数和矩阵的角度理解问题
  4. 函数式思维：递归和不可变性往往能让问题更清晰

章节安排

第一部分：思维基础

第1章：算法思维与复杂度分析

建立正确的思维框架，避免过度复杂化

  • 算法题的本质：约束条件下的优化
  • 复杂度直觉：根据数据规模判断可行解法
  • 简化思维：从暴力到优化的系统路径 (#215 数组中第K大元素)
  • 调试思维：快速定位逻辑错误

第2章：数组与哈希表的巧妙运用

最基础也最灵活的数据结构

  • 数组索引的多重含义与原地操作 (#41 缺失的第一个正数, #287 寻找重复数)
  • 哈希表的三种核心用法：去重、计数、映射 (#49 字母异位词分组, #128 最长连续序列)
  • 前缀和与差分数组：区间操作优化 (#560 和为K的子数组, #238 除自身以外数组的乘积)
  • 滑动窗口与双指针模板 (#3 无重复字符的最长子串, #15 三数之和)

第二部分：核心技巧

第3章：双指针与滑动窗口

线性时间的艺术

  • 相向双指针：有序数组的利用 (#11 盛最多水的容器, #16 最接近的三数之和)
  • 快慢指针：链表与数组去重 (#142 环形链表II, #80 删除有序数组中的重复项II)
  • 滑动窗口：最长/最短子串问题 (#209 长度最小的子数组, #438 找到字符串中所有字母异位词)
  • 多指针协作：三数之和、四数之和 (#15 三数之和, #18 四数之和)

第4章：二分查找的变体

对数时间的威力

  • 标准二分与边界处理 (#34 在排序数组中查找元素的第一个和最后一个位置)
  • 二分答案：最大化最小值问题 (#875 爱吃香蕉的珂珂, #1011 在D天内送达包裹的能力)
  • 旋转数组与山峰数组 (#33 搜索旋转排序数组, #162 寻找峰值)
  • 二分查找的抽象：单调性与决策函数 (#287 寻找重复数, #378 有序矩阵中第K小的元素)

第5章：栈与单调栈

维护有序性的利器

  • 栈的基本应用：括号匹配、表达式求值 (#71 简化路径, #150 逆波兰表达式求值)
  • 单调栈：下一个更大/更小元素 (#739 每日温度, #503 下一个更大元素II)
  • 最大矩形与柱状图问题 (#84 柱状图中最大的矩形, #85 最大矩形)
  • 栈与递归的关系 (#394 字符串解码, #341 扁平化嵌套列表迭代器)

第三部分：递归与搜索

第6章：树的递归思维

自相似结构的优雅处理

  • 递归三要素：终止条件、递归体、返回值 (#236 二叉树的最近公共祖先, #114 二叉树展开为链表)
  • 自顶向下vs自底向上 (#543 二叉树的直径, #124 二叉树中的最大路径和)
  • 路径问题：从根到叶、任意路径 (#113 路径总和II, #437 路径总和III)
  • 树的序列化与构造 (#297 二叉树的序列化与反序列化, #105 从前序与中序遍历序列构造二叉树)

第7章：回溯与剪枝

搜索空间的系统探索

  • 回溯模板：选择、探索、撤销 (#46 全排列, #216 组合总和III)
  • 排列组合子集问题 (#90 子集II, #47 全排列II, #491 递增子序列)
  • N皇后与数独：约束满足 (#51 N皇后, #37 解数独)
  • 剪枝技巧：可行性与最优性剪枝 (#39 组合总和, #40 组合总和II)

第8章：BFS与DFS的选择

图遍历的两种视角

  • BFS：最短路径与层序遍历 (#103 二叉树的锯齿形层序遍历, #127 单词接龙)
  • DFS：连通性与拓扑排序 (#200 岛屿数量, #207 课程表)
  • 双向BFS优化 (#126 单词接龙II, #752 打开转盘锁)
  • 记忆化搜索：DFS+缓存 (#329 矩阵中的最长递增路径, #139 单词拆分)

第四部分：动态规划

第9章：动态规划的本质

从递归到记忆化到迭代

  • 重叠子问题与最优子结构 (#96 不同的二叉搜索树, #95 不同的二叉搜索树II)
  • 状态定义的艺术 (#198 打家劫舍, #337 打家劫舍III)
  • 递推vs递归：两种实现方式 (#63 不同路径II, #64 最小路径和)
  • 空间优化：滚动数组与状态压缩 (#309 最佳买卖股票时机含冷冻期, #714 买卖股票的最佳时机含手续费)

第10章：背包问题家族

DP的经典模式

  • 01背包：选或不选的决策 (#416 分割等和子集, #494 目标和)
  • 完全背包：无限使用的优化 (#322 零钱兑换, #518 零钱兑换II)
  • 多重背包与分组背包 (#474 一和零)
  • 背包的变体：恰好装满、方案计数 (#377 组合总和IV, #139 单词拆分)

第11章：区间DP与状态压缩

高级DP技巧

  • 区间DP：戳气球、矩阵链乘法 (#312 戳气球, #1039 多边形三角剖分的最低得分)
  • 数位DP：统计特定范围内的数 (#233 数字1的个数, #902 最大为N的数字组合)
  • 状态压缩：用二进制表示集合 (#464 我能赢吗, #847 访问所有节点的最短路径)
  • 概率DP与期望DP (#688 骑士在棋盘上的概率, #837 新21点)

第五部分：高级主题

第12章：图算法精选

复杂关系的建模与处理

  • 图的表示：邻接表vs邻接矩阵 (#133 克隆图, #310 最小高度树)
  • 最短路径：Dijkstra、Bellman-Ford (#743 网络延迟时间, #787 K站中转内最便宜的航班)
  • 最小生成树：Kruskal、Prim (#1584 连接所有点的最小费用, #1168 水资源分配优化)
  • 并查集：连通性与等价类 (#684 冗余连接, #721 账户合并)

第13章：贪心算法的正确性

局部最优到全局最优

  • 贪心选择性质的证明 (#55 跳跃游戏, #45 跳跃游戏II)
  • 区间调度与活动选择 (#435 无重叠区间, #452 用最少数量的箭引爆气球)
  • 哈夫曼编码与最优合并 (#1167 连接木棍的最低费用, #253 会议室II)
  • 贪心的反例与陷阱 (#406 根据身高重建队列, #621 任务调度器)

第14章：数学与位运算技巧

巧妙的数学洞察

  • 位运算：异或的妙用、位掩码技巧 (#137 只出现一次的数字II, #260 只出现一次的数字III)
  • 数论基础：GCD、质数、模运算 (#166 分数到小数, #50 Pow(x, n))
  • 组合数学：排列组合公式的应用 (#31 下一个排列, #60 排列序列)
  • 几何问题：凸包、最近点对 (#149 直线上最多的点数, #223 矩形面积)

使用建议

  1. 循序渐进：每章都建立在前面的基础上
  2. 重视思路：理解"为什么这样想"比"怎么实现"更重要
  3. 练习反思：做题后总结模式，而不是记忆具体解法
  4. AI辅助：善用AI工具理解题意和验证思路，但要自己完成核心推理

学习目标

完成本指南后，你应该能够：

  • 快速识别题目类型和适用的算法模式
  • 避免常见的思维陷阱和过度复杂化
  • 在30-45分钟内解决大部分Medium难度题目
  • 清晰地解释你的思路和权衡

让我们开始这段算法思维的修炼之旅。