LeetCode 核心题型分类与解题模式速查手册

Posted on Edited on In

数据结构

1. 数组与矩阵 (核心模式归类)

A. 原地修改 / 数组作为哈希表 (实现 $O(1)$ 额外空间)

B. 矩阵遍历与坐标变换

  • 54. 螺旋矩阵【模式：四边界收缩；$(u, d, l, r)$ 指针随遍历向内挤压】
  • 36. 有效的数独【模式：一维化索引；利用 (r/3)*3 + c/3 映射九宫格】
  • 189. 轮转数组【模式：三次翻转；通过 reverse 实现 $O(1)$ 空间位移】
  • 31. 下一个排列【模式：标准算法；找 pivot -> 找更大数 -> 交换并反转】

C. 双指针、贪心与接雨水 (处理单调性或边界)

  • 11. 盛最多水的容器【模式：对撞指针；每次移动较短边以求更大容积】
  • 42. 接雨水【模式：双指针/单调栈；核心是“木桶原理”，高度由短板决定】
  • 407. 接雨水 II【模式：BFS + 优先队列；从外向内收缩 3D 边界】
  • 283. 移动零【模式：快慢指针；一个负责遍历，一个负责存放非零值】
  • 228. 汇总区间【模式：分组循环 / 双指针；核心：通过 nums[j+1] != nums[j]+1 识别连续区间断点】
  • 134. 加油站【模式：贪心；记录总收益与局部余量判断起点】
  • 135. 分发糖果【模式：双向遍历；确保同时满足左右邻居约束】

D. 前缀和与子数组 (处理区间和/积)

E. 区间处理 (排序 + 贪心)

  • 56. 合并区间【模式：区间合并；核心：按起点排序，维护 [L, R]，利用 l <= cur_right 动态扩展右边界】
  • 57. 插入区间【模式：分类讨论；核心：将区间分为“左侧不重叠”、“中间重叠合并”、“右侧不重叠”三部分处理】
  • 452. 用最少数量的箭引爆气球【模式：区间交集；核心：按终点排序，贪心选择重叠区域的边缘】
  • 435. 无重叠区间【模式：贪心留空；核心：按终点排序，尽量保留先结束的区间，以给后续留出更多空间】
  • 646. 最长数对链【模式：贪心；核心：按第二个数排序，贪心选择结束最早的区间，同 435 题】
  • 253. 会议室 II【模式：上下车/差分思想；核心：将起点看作 +1，终点看作 -1，求最大并发数；或利用小顶堆维护当前结束时间】
  • 228. 汇总区间【模式：分组循环 / 双指针；核心：识别连续数字序列的断点】
  • 2580. 统计将重叠区间合并成组的方案数【模式：区间合并 + 组合数学；核心：合并后得到 m 个独立连通块，结果为 $2^m$】

F. 查找、排序与二分

G. 哈希计数与频率统计 (利用数组或 Map 记录状态)

  • 1. 两数之和【模式：在线哈希查找；核心：在一次遍历中同时进行“查找”与“存入”，实现 $O(n)$ 时间复杂度】
  • 128. 最长连续序列【模式：哈希集合 + 智能起点；核心：利用 unordered_set 实现 $O(1)$ 查找，仅从序列起点 (x-1 不存在) 开始计数，确保 $O(n)$ 复杂度】
  • 217. 存在重复元素【模式：哈希集合；核心：利用 unordered_set 实现 $O(n)$ 频率检测，最基础的去重思想】
  • 219. 存在重复元素 II【模式：固定窗口哈希；核心：维护大小为 k 的 unordered_set】
  • 220. 存在重复元素 III【模式：滑动窗口 + 有序集合；核心：利用 std::set::lower_bound 寻找满足范围条件的元素】
  • 202. 快乐数【模式：循环检测；核心：利用 unordered_set 记录历史值或使用“快慢指针”在 $O(1)$ 空间内检测无限循环】
  • 383. 赎金信【模式：字符计数；利用 int[26] 数组实现 $O(n)$ 时间 $O(1)$ 空间的高性能频率校验】
  • 242. 有效的字母异位词【模式：频率对比；核心：利用 int[26] 计数，通过“先加后减”配合“负数早期退出”实现 $O(n)$ 校验】
  • 49. 字母异位词分组【模式：等类规约；核心：利用“排序后的字符串”或“字符频次”作为 Map 的 Key 进行归一化分类】
  • 387. 字符串中的第一个唯一字符【模式：两次遍历；先统计频次，再找第一个频次为 1 的索引】
  • 205. 同构字符串【模式：索引映射；通过 mapS[s[i]] == mapT[t[i]] 校验字符映射的一致性】
  • 290. 单词规律【模式：双向哈希；核心：利用双 Map 或 Map+Set 建立 char 与 string 的双射关系，注意利用 stringstream 处理单词拆分】
  • 266. 判断一个字符串是否是回文排列【模式：奇偶计数；回文排列最多只能有一个字符出现奇数次】
  • 409. 最长回文串【模式：贪心构造；统计成对出现的字符，最后可选加一个奇数项作为中心】

H. 缺失/重复/只出现一次的数字 (标记为负数/原地置换/位运算)

2. 栈与单调栈 (核心模式归类)

A. 基础栈应用与模拟 (处理嵌套、撤销与状态存取)

  • 20. 有效的括号【模式：括号匹配；核心：利用栈的 LIFO 特性处理嵌套关系】
  • 150. 逆波兰表达式求值【模式：后缀表达式计算；核心：遇到运算符弹出两数计算，注意减/除顺序】
  • 224. 基本计算器【模式：符号栈模拟；核心：利用栈维护当前括号层级的“全局正负号”，实现 $O(n)$ 一次遍历展开括号】
  • 155. 最小栈【模式：双栈/辅助栈；核心：同步维护一个“当前的最小值”栈】
  • 232. 用栈实现队列【模式：双栈翻转；核心：利用入栈和出栈两个容器实现 FIFO】
  • 394. 字符串解码【模式：多栈状态存取；核心：分别用栈存储当前的倍数 cnt 和已拼出的 string】
  • 71. 简化路径【模式：路径模拟；核心：遇到 .. 执行出栈，配合 stringstream 拆分单词】

B. 单调栈基础 (在线性时间内寻找左右最近的极值)

C. 单调栈进阶 (处理区间面积与贡献度计算)

  • 84. 柱状图中最大的矩形【模式：左右扩展边界；核心：利用单调栈一次性确定每个柱子的左、右边界，求最大矩形面积】
  • 907. 子数组的最小值之和【模式：贡献度法；核心：计算每个元素作为最小值的区间覆盖范围 $(i-L)*(R-i)$】
  • 2866. 美丽塔 II【模式：前后缀单调栈；核心：分别计算左侧和右侧的单调递增和，最后枚举顶点取 Max】
  • 768. 最多能完成排序的块 II【模式：单调栈维护块极值；核心：栈中每个元素代表一个“块”的最大值，重叠则合并】

D. 栈与贪心/其他

3. 队列、双端队列与堆 (用于滑动窗口极值或动态 TopK)

4. 链表 (核心模式归类)

A. 基础操作与反转 (双指针、递归与 Dummy Node)

B. 快慢指针与环形检测

  • 141. 环形链表【模式：快慢指针；核心：利用步长差 $(2-1=1)$，在 $O(n)$ 时间 $O(1)$ 空间内检测链表是否有环】
  • 142. 环形链表 II【模式：双指针追赶；核心：相遇后将一指针归零，同步慢走寻找环入口】
  • 19. 删除链表的倒数第 N 个结点【模式：快慢指针；核心：利用 $n$ 步位移差定位倒数第 $n+1$ 个节点（前驱节点）】
  • 61. 旋转链表【模式：成环解环；核心：先连成环再在 $n-(k%n)$ 处断开，简化指针操作】
  • 876. 链表的中间结点【模式：快慢指针；核心：fast 走两步 slow 走一步，fast 到头时 slow 在中点】
  • 287. 寻找重复数【模式：映射找环；将数组索引视为链表指针，转化为环入口问题】

C. 合并、排序与分隔

D. 复杂链表与采样

  • 138. 随机链表的复制【模式：原地克隆；核心：A->A'->B->B' 插入法，实现 $O(1)$ 空间拷贝随机指针】
  • 382. 链表随机节点【模式：水塘抽样；核心：从未知长度流中等概率采样，确保概率为 $1/i$】
  • 146. LRU 缓存【模式：哈希表 + 双向链表；实现 $O(1)$ 的访问与淘汰】
  • 460. LFU 缓存【模式：双哈希表 + 频次链表；实现 $O(1)$ 的频率敏感淘汰】

5. 二叉树与树形结构 (核心模式归类)

A. 遍历、属性与结构基础 (递归与迭代)

B. 路径、祖先与贡献度计算 (DFS 进阶)

C. 构造、变换与序列化

D. 二叉搜索树 (BST 专项)

6. 树与图论 (Tree & Graph - 核心模式归类)

A. 树的基础与进阶 (Tree)

B. 网格搜索与连通性 (DFS/BFS)

  • 200. 岛屿数量【模式：DFS/BFS；核心：原地修改标记（沉岛）实现 $O(1)$ 空间】
  • 305. 岛屿数量 II【模式：并查集 (Union-Find)；核心：动态维护连通分量，将”陆地化”转化为”集合合并”】
  • 130. 被围绕的区域【模式：逆向思维；从边界 'O' 开始标记，未被标记的内部 'O' 均需填充】
  • 133. 克隆图【模式：哈希表 + DFS/BFS；核心：利用 Map 存储 [原节点 -> 新节点] 防止死循环】
  • 399. 除法求值【模式：带权图搜索；将变量视为节点，比值视为边权，通过 DFS 或并查集求解】

C. 拓扑排序 (有向无环图 DAG)

D. 广度优先搜索进阶 (最短路径/步数)

  • 909. 蛇梯棋【模式：BFS；核心：一维坐标与二维矩阵的映射转换】
  • 433. 最小基因变化【模式：单向/双向 BFS；寻找状态空间的最短路径】
  • 127. 单词接龙【模式：双向 BFS；核心：利用中间态（如 h*t）优化状态转移搜索】

E. 最短路径算法 (Dijkstra/Floyd/Bellman)

F. 高级图论与连通性 (并查集/基环树/网络流)

7. 平衡二叉搜索树 (std::map/set)

8. 前缀和、后缀和与区间求和

9. 差分 (连续区间同时加上或者减去一个数，数组还原)

10. 树状数组 (Binary Indexed Tree)

11. 线段树 (Segment Tree - 区间修改与聚合查询)

12. 字典树 (Trie)

13. 字符串匹配 (KMP / AC 自动机)

14. 并查集 (Union Find)

15. 数据结构设计与实现 (Consolidated)

A. 基础结构实现

B. 缓存与高级哈希

C. 树与图的高级结构

16. 离线query

17. 优先队列与堆 (Priority Queue & Heap)

A. 基础堆应用 (Top K / 动态极值 / 中位数)

B. 反悔贪心 (Regret Greedy - 核心模式)

  • 630. 课程表 III【模式：大顶堆维护耗时；遇到冲突时“反悔”替换掉耗时最长的课程】
  • LCP 30. 魔塔游戏【模式：小顶堆维护负值；血量不足时“反悔”将之前扣血最多的移到最后】
  • 871. 最低加油次数【模式：大顶堆维护油量；油不够时“反悔”在之前经过的油量最大的站加油】
  • 502. IPO【模式：双堆；按资本排序 + 大顶堆选利润最大的项目】

C. 最短路径与图搜索 (Dijkstra 及其变体)

D. 区间与会议室 (扫描线 / 堆优化)

  • 253. 会议室 II【模式：小顶堆；堆顶存储最早结束的会议时间，判断是否需开新房】

基本算法

1. 滑动窗口/双指针 【left,right】

3. 排序算法/top k/select kth

4. 枚举

5. 模拟/分组/循环 (group/cycle arrray/模拟/易错)

6. 贪心算法 (Greedy Algorithm - 核心模式归类)

A. 基础贪心与排序 (利用排序消除维度影响)

B. 反悔贪心 (结合优先队列动态调整)

  • 630. 课程表 III【模式：反悔贪心；核心：先按截止时间排序，若当前无法加入则替换掉之前耗时最长的课程】
  • 502. IPO【模式：双堆/排序+大顶堆；核心：动态选择当前资金下利润最大的项目】
  • LCP 30. 魔塔游戏【模式：反悔贪心；核心：血量不足时将之前扣血最多的房间移到最后】
  • 871. 最低加油次数【模式：反悔贪心；核心：油不够时从经过的加油站中选油最多的加】

C. 贡献度法与数学贪心

D. 区间处理 (排序 + 边界维护)

E. 邻居约束与多遍遍历

F. 贪心 + 二分/DP 结合

7. 分治 (Divide and Conquer)

核心逻辑：

  1. **分解 (Divide)**：将原问题拆分为规模较小、相互独立的子问题（如左右子树、数组半区）。
  2. **解决 (Conquer)**：递归解决子问题，直到触及边界。
  3. **合并 (Combine)**：将子问题的解合并为原问题的解（如归并排序的 merge 或 LCA 的状态上传）。

数学 (Mathematics - 核心模式归类)

1. 数论基础 (Number Theory)

A. 质数、约数与筛选法

B. 最大公约数 (GCD) 与 最小公倍数 (LCM)

C. 数字处理与投票算法

  • 9. 回文数【模式：数学反转；核心：反转一半数字与前半部分比较，避免溢出】
  • 169. 多数元素【模式：Boyer-Moore 摩尔投票法；$O(n)$ 时间 $O(1)$ 空间找众数】
  • 229. 多数元素 II【模式：进阶摩尔投票；统计出现次数超过 $n/3$ 的元素】
  • 400. 第 N 位数字【模式：数学模拟；按位数区间（个位、十位…）定位数字】
  • 343. 整数拆分【模式：数学推导；核心：尽可能拆分成 3 以获得最大乘积】

2. 组合数学与概率 (Combinatorics & Probability)

A. 排列组合与大数取模

B. 模运算与乘法逆元

C. 随机采样 (Sampling)

3. 位运算 (Bit Manipulation)

A. 基础技巧与 Lowbit

  • 核心性质：n & (n-1) 消除最低位 1；n & -n 获取最低位 1 (lowbit)】
  • 191. 位 1 的个数【模式：__builtin_popcount 或 n & (n-1) 迭代】
  • 190. 颠倒二进制位【模式：位操作；逐位反转 ans = (ans << 1) | (n & 1) 或 分治法】
  • 231. 2 的幂【模式：n > 0 && (n & (n-1)) == 0】
  • 201. 数字范围按位与【模式：公共前缀；寻找 left 和 right 的二进制公共前缀】

B. 异或 (XOR) 专项

4. 快速幂与几何 (Fast Power & Geometry)

搜索问题核心分类与总结 (Search Strategies)

2. DFS 与回溯：全量枚举与约束满足 (DFS & Backtracking)

💡 回溯四阶梯与去重口诀

| 阶梯 | 核心场景 | 去重/控制逻辑 | 关键代码 |
| :--- | :--- | :--- | :--- |
| **1. 基础回溯** | 简单组合 (17题) | 递归深度控制索引 | `dfs(i + 1)` |
| **2. 组合去重** | 选 k 个数 (77题) | `start` 索引控制单向搜索 | `for (int i = start; ...)` |
| **3. 状态压缩** | 全排列 (46题) | `Bitmask` 替代 `visited` 数组 | `if (!(mask & (1 << j)))` |
| **4. 排列去重** | 有重全排列 (47题) | **排序 + 相邻状态校验** | `if (j > 0 && nums[j] == nums[j-1] && !used[j-1])` |
| **5. 复杂约束** | 棋盘/皇后 (52题) | **空间换时间 (哈希标记)** | `if (!cols[c] && !diag[r+c])` |
| **6. 余额控制** | 括号生成 (22题) | **动态维护待匹配余额** | `if (remain > 0) dfs(..., remain-1)` |
| **7. 矩阵回溯** | 单词搜索 (79题) | **原地标记 + 字符还原** | `board[r][c] = '#'; dfs(); board[r][c] = tmp;` |

去重口诀：

  • 组合靠 start：不回头看，一路向右。
  • 排列靠 used：全员参与，位掩码标记。
  • 重复靠排序：前人未用，后人莫入（!used[i-1]）。
  • 棋盘靠标记：列号、和、差，三位一体定乾坤。
  • 括号看余额：左括号不超标，右括号不透支。
  • 矩阵靠沉岛：先占位再递归，事后记得还原。

组合、排列与路径

DP 问题 (Dynamic Programming - 核心模式归类)

DP 类问题处理五部曲总结

步骤 核心任务 (Key Action) 你的代码体现 (Example) 空间优化思路 (Space Optimization)
1. 状态定义 明确 dp 数组各维度的物理含义（是长度、最值还是布尔值？对应什么区间？） dp[i][j] 表示到达坐标 (i,j) 的最小路径和 维度压缩：若当前状态只依赖前一状态，可将二维数组降为一维（或常数个变量）。
2. 转移方程 逻辑推导过程，包括不同条件下的决策 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 原地修改：如果输入数组（如 grid）后续不再使用，可以直接在原数组上操作实现 $O(1)$ 额外空间。
3. 初始边界 算法开始的基石（如单字符情况、空串情况），确定无需推导的“种子”值 初始化 dp[0][0]，并单独处理首行 dp[0][i] 和首列 dp[i][0] 虚拟边界：有时可以多申请一行/一列（如 dp[m+1][n+1]）并填入占位值，从而统一循环内的逻辑。
4. 计算顺序 确定循环的方向（Top-down vs Bottom-up），由状态依赖关系决定 使用双重 for 循环，从左到右、从上到下遍历 倒序遍历：在 0/1 背包等问题中，通过倒序遍历一维 DP 数组，可以防止当前层的计算污染待使用的旧数据。
5. 最终结果 确定答案在 dp 表中的存储位置 返回 dp[m-1][n-1] 状态追踪：如果不仅要结果还要路径，通常需要额外的 parent 数组记录来源，空间优化此时会受限。
6. 复杂度分析 分析时间与空间开销 时间 $O(M \times N)$，空间 $O(M \times N)$ 时空权衡：有时为了降低时间复杂度（如利用前缀和优化转移），可能会增加空间复杂度。

1. 基础线性 DP (1D/2D 填表)

最基础的递推，dp[i] 只依赖于前面几个状态

A. 斐波那契/爬楼梯模型

B. 网格路径模型 (Grid)

C. 简单一维推导

2. 状态机 DP (State Machine)

核心在于定义“持有”、“冷冻”、“卖出”等有限状态，画状态转移图

A. 股票系列

B. 其他状态机

C. 打家劫舍系列汇总 (House Robber)

3. 序列 DP (双串/单串)

处理字符串或数组子序列问题，核心是 LCS/LIS 模型

A. 单串 LIS 模型 ($O(n^2)$ 或 $O(n \log n)$)

B. 双串 LCS 模型 (二维表,m + 1,n + 1 处理空串的情况)

  • 1143. 最长公共子序列【模式：双串 DP；dp[i][j] = s1[i]==s2[j] ? dp[i-1][j-1]+1 : max(左, 上)；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 72. 编辑距离【模式：增删改三选一；dp[i][j] = min(插入, 删除, 替换) + 1；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 97. 交错字符串【模式：双串 DP；dp[i][j] 表示 s1[0..i] 和 s2[0..j] 能否交错组成 s3[0..i+j]；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 583. 两个字符串的删除操作【模式：LCS 变体；结果为 m + n - 2 * LCS；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 1035. 不相交的线【模式：LCS 本质；完全等同于最长公共子序列；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 115. 不同的子序列【模式：计数 DP；s[i]==t[j] 时可选匹配或不匹配，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】

C. 回文串模型

4. 划分型 DP (Partition)

将数组/字符串切分为 k 段，求最优解

5. 背包 DP (Knapsack)

组合优化问题，关注容量与价值

A. 0/1 背包

B. 完全背包

C. 多重/分组背包

6. 区间 DP (Interval)

从小区间合并到大区间，枚举分割点 k

7. 树形 DP (Tree DP)

自底向上汇总信息，或换根 DP

A. 子树贡献/直径

B. 换根 DP

8. 状压 DP (Bitmask)

数据范围 n < 20，用二进制表示集合

9. 数位 DP (Digit DP)

按位填数，通常配合记忆化搜索

10. 其他/高级 DP

工程小技巧 (Engineering Tips)

1. 数组快速清零

在 C++ 中，局部变量（栈上分配）默认包含随机垃圾值。使用以下语法可实现极致高效的清零：

1
2
int arr[9][9] = {0}; // 显式初始化第一个元素为 0，其余元素自动补零
int arr[9][9] = {};  // C++11 简写，全员清零
  • 注意：如果不加 {0}，数组内容将不可预测，这是初学者最常见的 Bug 来源。
  • 性能：编译器通常会将其优化为内联的 memset 或专门的 CPU 指令，比手动 for 循环快得多。

2. 字符串单词拆分 (stringstream)

在处理以空格分隔的字符串（如“hello world”）时，手动控制指针解析既繁琐又容易出错（需考虑首尾空格、多空格等情况）。

1
2
3
4
5
6
7
#include <sstream>
string s = "  hello   world  ";
stringstream ss(s);
string word;
while (ss >> word) {
    // 自动跳过所有空格，依次提取出 "hello" 和 "world"
}

3. 搜索策略选择指南

在算法竞赛或面试中，面对复杂的搜索问题，快速判断技术路线是节省时间的关键：

  • 求最短路径 / 最小步数：首选 BFS（利用其层级遍历的天然最短性）。
  • 求所有方案 / 排列组合：首选 DFS + 回溯（全量枚举状态空间）。
  • 在单调 / 有序空间找最优值：首选 二分答案（将最优化问题转化为判定问题 check(mid)）。
  • 状态空间爆炸：优先考虑 双向 BFS（极大减小搜索树规模）或 记忆化搜索（DFS + Memo，避免重复计算）。

C++ 字符处理函数速查

函数名 检查内容 说明
isdigit(c) 是否为数字 (0-9) 数字字符
isalpha(c) 是否为字母 (a-z, A-Z) 纯字符/字母
isalnum(c) 是否为字母或数字 字母数字混合
tolower(c) 转换为小写 字符转换
toupper(c) 转换为大写 字符转换

参考