Cao NoteLeetCode 分类题解
刷题最大的浪费是「做完一道只会一道」。这一页按套路分类 —— 看到题先问「它属于哪一类」，再套模板。 每类给：识别特征 → 模板 → 5 道代表题（题号 + 一句话思路）。
用法
- 先看「识别特征」，确认这类题长什么样。
- 背模板（只有几行），然后去做代表题。
- 做不出来不要立刻看答案，先问自己「卡在识别还是卡在实现」。
一、双指针
特征：数组有序、要求「两个数/三段区间」、原地修改、去重。
java
// 对撞双指针：两数之和（有序）
int l = 0, r = n - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return new int[]{l, r};
if (sum < target) l++; else r--;
}// 对撞双指针：两数之和（有序）
int l = 0, r = n - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return new int[]{l, r};
if (sum < target) l++; else r--;
}| 题号 | 题 | 思路 |
|---|---|---|
| 167 | 两数之和 II | 上面模板 |
| 15 | 三数之和 | 排序 + 固定一个 + 对撞，注意去重 |
| 11 | 盛最多水的容器 | 移动矮的那边 |
| 283 | 移动零 | 快慢指针，把非零往前挤 |
| 42 | 接雨水 | 双指针维护左右最大值 |
易错点：三数之和的去重是 nums[i] == nums[i-1] 而不是 nums[i] == nums[i+1]。
二、滑动窗口
特征：「最长/最短的连续子串/子数组」+ 一个可维护的条件。
java
int left = 0, ans = 0;
Map<Character, Integer> win = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
// 1. 右指针进窗
win.merge(s.charAt(right), 1, Integer::sum);
// 2. 窗口不合法就收缩左边界
while (/* 不合法 */) {
win.merge(s.charAt(left), -1, Integer::sum);
left++;
}
// 3. 更新答案
ans = Math.max(ans, right - left + 1);
}int left = 0, ans = 0;
Map<Character, Integer> win = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
// 1. 右指针进窗
win.merge(s.charAt(right), 1, Integer::sum);
// 2. 窗口不合法就收缩左边界
while (/* 不合法 */) {
win.merge(s.charAt(left), -1, Integer::sum);
left++;
}
// 3. 更新答案
ans = Math.max(ans, right - left + 1);
}| 题号 | 题 | 思路 |
|---|---|---|
| 3 | 无重复字符最长子串 | 窗口内字符不重复 |
| 76 | 最小覆盖子串 | 窗口需覆盖 t 的所有字符，收缩条件是「已覆盖」 |
| 438 | 找所有字母异位词 | 固定长度窗口 + 计数数组比较 |
| 209 | 长度最小子数组 | 和 >= target 就收缩 |
| 239 | 滑动窗口最大值 | 单调队列（见「栈」一节） |
易错点：先 while 收缩再更新答案 —— 顺序反了答案就偏大。
三、哈希与计数
特征：查「出现过没有」「出现几次」「两数配对」。
| 题号 | 题 | 思路 |
|---|---|---|
| 1 | 两数之和 | 边遍历边存 target - x |
| 49 | 字母异位词分组 | 排序后的串 / 26 位计数当 key |
| 128 | 最长连续序列 | 只从「没有前驱」的数开始数 |
| 560 | 和为 K 的子数组 | 前缀和 + 哈希计数 |
| 347 | 前 K 个高频元素 | 计数 + 小顶堆 / 桶排序 |
模板（前缀和 + 哈希）：
java
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1); // 关键：空前缀
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += cnt.getOrDefault(sum - k, 0);
cnt.merge(sum, 1, Integer::sum);
}Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1); // 关键：空前缀
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += cnt.getOrDefault(sum - k, 0);
cnt.merge(sum, 1, Integer::sum);
}四、链表
特征：改指针、找环、合并、删除倒数第 N 个。
java
// 必备：哑结点（dummy）能省掉所有头节点特判
ListNode dummy = new ListNode(0, head), prev = dummy;
// 必备：快慢指针找中点 / 判环
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }// 必备：哑结点（dummy）能省掉所有头节点特判
ListNode dummy = new ListNode(0, head), prev = dummy;
// 必备：快慢指针找中点 / 判环
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }| 题号 | 题 | 思路 |
|---|---|---|
| 206 | 反转链表 | 三指针（见手写题清单） |
| 25 | K 个一组翻转 | 分组 + 组内反转 + 拼接 |
| 141 / 142 | 环形链表 | 快慢指针相遇后，一个回头，再走相遇即入口 |
| 21 | 合并两个有序链表 | 哑结点 + 双指针 |
| 146 | LRU 缓存 | HashMap + 双向链表（见手写题清单） |
易错点：反转后忘记把尾节点的 next 置空，导致新链表带环。
五、二叉树
特征：「前中后序」「层序」「路径」「最近公共祖先」。
java
// 递归三要素：出口、当前层做什么、返回什么
int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left), right = dfs(node.right);
return Math.max(left, right) + 1; // 例：求深度
}
// 层序：队列 + 每层 size
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
TreeNode n = q.poll();
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
}// 递归三要素：出口、当前层做什么、返回什么
int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left), right = dfs(node.right);
return Math.max(left, right) + 1; // 例：求深度
}
// 层序：队列 + 每层 size
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
TreeNode n = q.poll();
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
}| 题号 | 题 | 思路 |
|---|---|---|
| 94 / 144 / 145 | 三种遍历 | 递归；迭代版用栈 |
| 102 | 层序遍历 | 上面模板 |
| 236 | 最近公共祖先 | 左右各找到就返回当前节点 |
| 124 | 最大路径和 | 后序，返回单边最大，全局答案取两边和 |
| 105 | 前序+中序重建 | 前序首元素切中序 |
易错点：124 这类题要区分「返回给父节点的值」和「更新全局答案的值」。
六、图与搜索
特征：网格、连通块、最短路（无权）、拓扑排序。
java
// 网格 BFS（最短路模板）
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sr, sc});
boolean[][] seen = new boolean[m][n];
seen[sr][sc] = true;
int step = 0;
while (!q.isEmpty()) {
for (int i = q.size(); i > 0; i--) {
int[] cur = q.poll();
if (cur[0] == tr && cur[1] == tc) return step;
for (int[] d : dirs) {
int x = cur[0] + d[0], y = cur[1] + d[1];
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (seen[x][y] || grid[x][y] == 1) continue;
seen[x][y] = true;
q.offer(new int[]{x, y});
}
}
step++;
}// 网格 BFS（最短路模板）
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sr, sc});
boolean[][] seen = new boolean[m][n];
seen[sr][sc] = true;
int step = 0;
while (!q.isEmpty()) {
for (int i = q.size(); i > 0; i--) {
int[] cur = q.poll();
if (cur[0] == tr && cur[1] == tc) return step;
for (int[] d : dirs) {
int x = cur[0] + d[0], y = cur[1] + d[1];
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (seen[x][y] || grid[x][y] == 1) continue;
seen[x][y] = true;
q.offer(new int[]{x, y});
}
}
step++;
}| 题号 | 题 | 思路 |
|---|---|---|
| 200 | 岛屿数量 | DFS/BFS 染色，数连通块 |
| 207 | 课程表 | 拓扑排序（入度 + 队列） |
| 994 | 腐烂的橘子 | 多源 BFS，答案是层数 |
| 1091 | 二进制矩阵最短路 | 八方向 BFS |
| 547 | 省份数量 | 并查集 / DFS |
易错点：多源 BFS 的起点要一次全入队，不能一个个来。
七、回溯
特征：「所有组合 / 排列 / 子集 / 分割」，且要求列出全部方案。
java
void backtrack(int start, List<Integer> path) {
res.add(new ArrayList<>(path)); // 1. 收集（这里是无条件收集子集）
for (int i = start; i < n; i++) {
if (i > start && a[i] == a[i - 1]) continue; // 2. 同层去重
path.add(a[i]); // 3. 做选择
backtrack(i + 1, path); // 4. 递归（组合用 i+1，排列用 visited）
path.remove(path.size() - 1); // 5. 撤销
}
}void backtrack(int start, List<Integer> path) {
res.add(new ArrayList<>(path)); // 1. 收集（这里是无条件收集子集）
for (int i = start; i < n; i++) {
if (i > start && a[i] == a[i - 1]) continue; // 2. 同层去重
path.add(a[i]); // 3. 做选择
backtrack(i + 1, path); // 4. 递归（组合用 i+1，排列用 visited）
path.remove(path.size() - 1); // 5. 撤销
}
}| 题号 | 题 | 思路 |
|---|---|---|
| 78 | 子集 | 上面模板（无条件收集） |
| 46 | 全排列 | 用 visited[] 而不是 start |
| 39 / 40 | 组合总和 | 可重复传 i，不可重复传 i+1 |
| 51 | N 皇后 | 列/主对角/副对角三个集合剪枝 |
| 131 | 分割回文串 | 切分点做选择 + 回文预判 |
易错点：去重必须先排序，且判重是「同一层跳过」而不是「整棵树跳过」。
八、动态规划
特征：求「最值 / 方案数」，且当前状态只依赖更小的子问题。
java
// 四步：定义状态 -> 转移 -> 初始化 -> 遍历顺序
int[] dp = new int[n + 1];
dp[0] = 1; // 初始化（空串/空背包通常为 1）
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (/* 可转移 */) dp[i] += dp[j];
}
}// 四步：定义状态 -> 转移 -> 初始化 -> 遍历顺序
int[] dp = new int[n + 1];
dp[0] = 1; // 初始化（空串/空背包通常为 1）
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (/* 可转移 */) dp[i] += dp[j];
}
}| 题号 | 题 | 状态定义 |
|---|---|---|
| 70 | 爬楼梯 | dp[i] 到第 i 阶的方案数 |
| 198 | 打家劫舍 | dp[i] 前 i 间最高金额 |
| 322 | 零钱兑换 | dp[amount] 凑出该金额的最少硬币 |
| 300 | 最长递增子序列 | dp[i] 以 i 结尾的 LIS 长度（可优化到 O(n log n)） |
| 72 | 编辑距离 | dp[i][j] 前 i 与前 j 的编辑距离 |
易错点：遍历顺序 —— 01 背包容量倒序，完全背包正序；二维 DP 先想清楚行列代表什么。
九、栈与单调栈
特征：「下一个更大/更小」「括号匹配」「表达式求值」。
java
// 下一个更大元素（单调递减栈）
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> st = new ArrayDeque<>(); // 存下标
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && nums[i] > nums[st.peek()]) res[st.pop()] = nums[i];
st.push(i);
}
return res;
}// 下一个更大元素（单调递减栈）
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> st = new ArrayDeque<>(); // 存下标
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && nums[i] > nums[st.peek()]) res[st.pop()] = nums[i];
st.push(i);
}
return res;
}| 题号 | 题 | 思路 |
|---|---|---|
| 20 | 有效括号 | 左括号入栈，右括号比对 |
| 155 | 最小栈 | 辅助栈存当前最小值 |
| 84 | 柱状图最大矩形 | 单调递增栈 + 哨兵 |
| 739 | 每日温度 | 上面模板 |
| 239 | 滑动窗口最大值 | 单调递减队列 |
易错点：栈里存下标而不是值，否则算不出宽度。
十、位运算与数学
特征：「只出现一次」「不用额外空间」「2 的幂」。
| 题号 | 题 | 技巧 |
|---|---|---|
| 136 | 只出现一次的数字 | 全部异或，成对消掉 |
| 137 | 只出现一次 II | 按位统计 mod 3 |
| 260 | 只出现两个一次 | 异或后取最低位的 1 分组 |
| 191 | 1 的个数 | n &= n - 1 每次消掉最低位的 1 |
| 231 | 2 的幂 | n > 0 && (n & (n-1)) == 0 |
刷题节奏建议
| 阶段 | 做法 |
|---|---|
| 第 1 遍 | 按分类刷，每类 5 题，只求能套模板 |
| 第 2 遍 | 打乱顺序刷，练习「识别属于哪类」 |
| 第 3 遍 | 只刷错题，限时 20 分钟/题 |
别做的事：一天刷 20 道新题然后全忘；背题解但讲不出为什么。