LeetCode Hot 100 算法清单

本清单对应 LeetCode Hot 100, 共 100 题. 题目和官方列表会随时间调整, 本章按面试复习需要重新分组, 内容截至 2026-08-06.

针对你的定位 (中级 Android 应用方向): Android 算法面试以中等题为主. 下方每个分类标注了 ⭐(高频必刷) 和 △(偏难 / 低频, 可缓刷), 按优先级投入精力.

内容边界

本章列出 Hot 100 学习清单并提供高频母题 / 模板, 不是 100 题逐题完整题解, 也不承诺每个代码块可独立运行. 手册统一使用 C++ 主要是为了突出算法结构, 减少 Android API 干扰, 与作者的 NDK/C++ 背景一致; Android 面试仍应能用岗位要求的 Kotlin/Java 写出数组, 链表, 队列, 堆, DFS/BFS 和动态规划基础模板.

如何使用

第一轮: 只刷 ⭐ 高频题, 建立每类的解题模板 (约 40 题), 覆盖大部分中小厂.
第二轮: 补齐其余中等题, 冲大厂.
第三轮:△ 难题 (困难 / 低频) 按目标公司选刷.
每类先吃透 1-2 道 “母题” 模板, 其余是变体. 重在模板内化而非数量.

进度自测

勾选格式 - [x].⭐= 高频必刷,△= 可缓刷.

哈希表 (3)

⭐ 1. 两数之和 (简单)
49. 字母异位词分组 (中等)
128. 最长连续序列 (中等)

双指针 (4)

⭐ 283. 移动零
⭐ 11. 盛最多水的容器
⭐ 15. 三数之和
△ 42. 接雨水 (困难)

滑动窗口 / 前缀和 (5)

⭐ 3. 无重复字符的最长子串
438. 找到字符串中所有字母异位词
⭐ 560. 和为 K 的子数组
△ 239. 滑动窗口最大值 (困难)
△ 76. 最小覆盖子串 (困难)

普通数组 (5)

⭐ 53. 最大子数组和
⭐ 56. 合并区间
⭐ 189. 轮转数组
238. 除自身以外数组的乘积
△ 41. 缺失的第一个正数 (困难)

矩阵 (4)

73. 矩阵置零
⭐ 54. 螺旋矩阵
48. 旋转图像
240. 搜索二维矩阵 II

链表 (14)

⭐ 160. 相交链表
⭐ 206. 反转链表
234. 回文链表
⭐ 141. 环形链表
⭐ 142. 环形链表 II
⭐ 21. 合并两个有序链表
2. 两数相加
⭐ 19. 删除链表的倒数第 N 个结点
24. 两两交换链表中的节点
△ 25. K 个一组翻转链表 (困难)
138. 随机链表的复制
148. 排序链表
△ 23. 合并 K 个升序链表 (困难)
⭐ 146. LRU 缓存

二叉树 (15)

⭐ 94. 二叉树的中序遍历
⭐ 104. 二叉树的最大深度
⭐ 226. 翻转二叉树
⭐ 101. 对称二叉树
543. 二叉树的直径
⭐ 102. 二叉树的层序遍历
108. 将有序数组转换为二叉搜索树
⭐ 98. 验证二叉搜索树
230. 二叉搜索树中第 K 小的元素
199. 二叉树的右视图
114. 二叉树展开为链表
105. 从前序与中序遍历序列构造二叉树
437. 路径总和 III
⭐ 236. 二叉树的最近公共祖先
△ 124. 二叉树中的最大路径和 (困难)

图论 (4)

⭐ 200. 岛屿数量
994. 腐烂的橘子
⭐ 207. 课程表
208. 实现 Trie (前缀树)

回溯 (8)

⭐ 46. 全排列
⭐ 78. 子集
17. 电话号码的字母组合
39. 组合总和
22. 括号生成
79. 单词搜索
131. 分割回文串
△ 51. N 皇后 (困难)

二分查找 (6)

⭐ 35. 搜索插入位置
74. 搜索二维矩阵
⭐ 34. 在排序数组中查找元素的第一个和最后一个位置
⭐ 33. 搜索旋转排序数组
153. 寻找旋转排序数组中的最小值
△ 4. 寻找两个正序数组的中位数 (困难)

栈 (5)

⭐ 20. 有效的括号
⭐ 155. 最小栈
394. 字符串解码
⭐ 739. 每日温度
△ 84. 柱状图中最大的矩形 (困难)

堆 (3)

⭐ 215. 数组中的第 K 个最大元素
⭐ 347. 前 K 个高频元素
△ 295. 数据流的中位数 (困难)

贪心 (4)

⭐ 121. 买卖股票的最佳时机
⭐ 55. 跳跃游戏
45. 跳跃游戏 II
763. 划分字母区间

动态规划 - 单维 (10)

⭐ 70. 爬楼梯
118. 杨辉三角
⭐ 198. 打家劫舍
279. 完全平方数
⭐ 322. 零钱兑换
139. 单词拆分
⭐ 300. 最长递增子序列
152. 乘积最大子数组
416. 分割等和子集
△ 32. 最长有效括号 (困难)

动态规划 - 多维 (5)

⭐ 62. 不同路径
64. 最小路径和
⭐ 5. 最长回文子串
⭐ 1143. 最长公共子序列
△ 72. 编辑距离

技巧题 (5)

⭐ 136. 只出现一次的数字
⭐ 169. 多数元素
75. 颜色分类
31. 下一个排列
287. 寻找重复数

知识点解析

这一章不要把 Hot 100 当成 “100 道孤立的题”.真正要学的是: 读题时识别题型 → 选算法 → 套模板 → 解释复杂度. 下面按算法分类讲: 如何理解题目, 为什么选这个算法, 核心思想, 常用写法和易错点. 代码以 C++ 为主; 链表小节并列给出 Java 模板, 面试时应按岗位要求改写其他模板.

代码上下文: 示例使用 C++17, 省略重复的标准库头文件和 using namespace std;. 除非示例显式处理空输入, 否则默认遵循对应 LeetCode 题目的输入约束. 复制到独立文件时, 需要补齐该片段使用的标准库头文件.

先学会读题: 怎么从题目判断算法

读题时先问 5 个问题:

输入规模多大?
- n <= 100: O (n²) 甚至回溯也可能可以.
- n <= 10^5: 通常要 O (n), O (n log n), 不能双重循环.
- n <= 10^9: 通常不能遍历, 要数学, 二分, 位运算.
有没有 “有序” 条件?
- 数组有序: 优先想二分, 双指针.
- 矩阵行列有序: 想右上角 / 左下角搜索, 或二分.
题目问的是子数组/子串/连续区间吗?
- 固定长度或可伸缩窗口: 滑动窗口.
- 任意区间和: 前缀和.
- 有负数的 “和为 K”:不能随便滑窗, 要前缀和 + 哈希表.
题目要求 “所有方案/所有排列/所有组合” 吗?
- 通常是回溯. 关键词: 所有, 任意一种路径, 组合, 排列, 切分, 棋盘.
题目是否有 “最优值/计数/能否完成”?
- 有重叠子问题: 动态规划.
- 每步局部最优能保证全局: 贪心.
- 连通性/分组/合并集合: 并查集或图遍历.

面试回答顺序建议固定为:

我先看题目特征:[题目特征].暴力做法是 [暴力方案], 复杂度为 [暴力复杂度], 输入规模不允许. 所以我选 [算法名称], 核心是 [核心性质], 实现上维护 [关键状态], 最终复杂度为 [目标复杂度].

1. 哈希表

如何理解题目

只要题目需要 “快速判断一个东西是否出现过 / 出现了几次 / 某个配对值是否存在”, 就优先想哈希表. 暴力查找是 O (n), 哈希查找平均 O (1).

典型信号:

“两数之和”, “是否存在另一个数”.
“分组”, “频次”, “出现次数”.
“最长连续序列” 这种需要快速判断相邻值是否存在.

为什么选哈希表

哈希表本质是用空间换时间. 你多开一个 unordered_map 或 unordered_set, 把 “查找” 从线性扫描降到平均 O (1).

核心思想和用法

unordered_map<Key, Value>: 需要保存 “值 → 下标” 或 “元素 → 次数”.
unordered_set<T>: 只关心存在性.
频次统计: 遍历一遍, cnt[x]++.
配对查找: 当前是 x, 就查需要的另一个值 target - x 是否已经出现.

母题: 1 两数之和

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> pos; // value -> index
    for (int i = 0; i < nums.size(); ++i) {
        int need = target - nums[i];
        if (pos.count(need)) return {pos[need], i};
        pos[nums[i]] = i;
    }
    return {};
}

理解重点: 不要先把所有数放进去再找, 否则容易把同一个元素用两次. 边遍历边查, 保证查到的是之前的元素.

题目映射

49 字母异位词分组: 同一组字符串排序后相同, 排序串作 key; 或用 26 个字符计数作 key.
128 最长连续序列: 把所有数放进 set, 只从 x - 1 不存在的起点开始向后数, 这样每个数最多被访问一次.

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int ans = 0;
    for (int x : s) {
        if (s.count(x - 1)) continue; // 不是序列起点,跳过
        int cur = x;
        while (s.count(cur)) cur++;
        ans = max(ans, cur - x);
    }
    return ans;
}

易错点

unordered_map 平均 O (1), 最坏可能退化, 但面试按平均复杂度说即可.
128 题如果每个数都向后扩展, 会退化成 O (n²); 必须只从起点扩展.
频次 key 如果是数组, 要转换成字符串或固定格式, 否则不能直接当哈希 key.

2. 双指针

如何理解题目

双指针适合 “两个位置一起移动” 的题. 常见三类:

左右对撞: 数组有序, 找两数, 容器, 接雨水.
快慢指针: 链表找环, 删除倒数第 N 个, 原地压缩数组.
同向指针: 滑动窗口的基础版.

为什么选双指针

暴力通常枚举两个位置 O (n²).如果能根据条件移动某一个指针, 就可以把复杂度降到 O (n).

母题: 11 盛最多水的容器

int maxArea(vector<int>& height) {
    int l = 0, r = (int)height.size() - 1;
    int ans = 0;
    while (l < r) {
        ans = max(ans, min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;
        else r--;
    }
    return ans;
}

核心理解: 面积由短板决定. 移动长板, 短板不变, 宽度变小, 面积不可能更大; 所以只能移动短板寻找更高的板.

题目映射

283 移动零: 慢指针表示下一个非零应该放的位置, 快指针扫描.
15 三数之和: 排序后固定第一个数, 剩下两个数用左右指针找和.
42 接雨水: 左右指针维护 leftMax/rightMax, 谁小先处理谁.

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            long long sum = static_cast<long long>(nums[i]) + nums[l] + nums[r];
            if (sum == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l + 1]) l++;
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}

易错点

三数之和必须排序, 并且 i, l, r 三处都要去重.
双指针不是 “两个变量” 就行, 关键是要有单调移动理由.
接雨水要理解 “较小一侧的最大值已经能确定当前水量”.

3. 滑动窗口

如何理解题目

看到 “连续子串 / 连续子数组 / 最长 / 最短 / 满足条件的窗口”, 先想滑动窗口.

但注意: 滑动窗口要求窗口变化有单调性. 比如全是正数时, 右边加入会让和变大, 左边移出会让和变小; 有负数时这个性质消失.

为什么选滑动窗口

暴力枚举所有子串是 O (n²).滑动窗口中每个元素最多进窗口一次, 出窗口一次, 所以 O (n).

核心模板

int lengthOfLongestSubstring(string s) {
    vector<int> cnt(128, 0);
    int left = 0, ans = 0;
    for (int right = 0; right < s.size(); ++right) {
        cnt[s[right]]++;
        while (cnt[s[right]] > 1) {
            cnt[s[left]]--;
            left++;
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

模板理解:

right 负责扩张, 把新字符放进窗口.
如果窗口不合法, 就不断移动 left 缩小.
每次窗口合法后更新答案.

题目映射

3 无重复字符最长子串: 窗口内每个字符最多出现一次.
438 找到字符串中所有字母异位词: 固定长度窗口 + 频次比较.
76 最小覆盖子串: 可变窗口, 窗口满足条件后尽量左缩.
560 和为 K 的子数组: 不是滑窗, 因为数组可能有负数, 要用前缀和 + 哈希表.
239 滑动窗口最大值: 不是普通窗口统计, 要用单调队列.

易错点

“最长” 通常是在窗口合法时更新;“最短” 通常是在窗口满足条件后边缩边更新.
有负数的和问题不要套滑窗.
字符集大小明确时用数组比哈希表简单.

4. 普通数组: 前缀, 原地, 边界

如何理解题目

数组题看似杂, 其实先问:

是否要原地修改? 如果要求 O (1) 额外空间, 通常要交换, 反转, 原地哈希.
是否频繁查询区间? 用前缀和.
是否求连续最优? 可能是 Kadane 或 DP.
是否跟区间重叠有关? 排序后合并.

母题: 53 最大子数组和

int maxSubArray(vector<int>& nums) {
    int cur = nums[0], ans = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        cur = max(nums[i], cur + nums[i]);
        ans = max(ans, cur);
    }
    return ans;
}

理解重点: cur 表示 “必须以当前位置结尾的最大子数组和”.如果前面的和是负担, 就从当前重新开始.

题目映射

56 合并区间: 先按左端点排序, 再维护当前合并区间.
189 轮转数组: 三次反转, 避免额外数组.
238 除自身以外数组的乘积: 左边乘积 × 右边乘积, 不能用除法.
41 缺失的第一个正数: 把值 x 放到下标 x - 1, 用数组本身当哈希表.

void rotate(vector<int>& nums, int k) {
    if (nums.empty()) return;
    int n = nums.size();
    k %= n;
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}

易错点

189 的 k 要先 % n.
238 要先从左到右存前缀积, 再从右到左乘后缀积.
41 原地置换时要用 while, 不是 if, 因为换来的数可能还要继续归位.

5. 矩阵

如何理解题目

矩阵题本质是二维数组坐标控制. 先判断是哪类:

遍历顺序: 螺旋矩阵.
原地变换: 旋转图像.
标记行列: 矩阵置零.
行列有序: 从右上角或左下角搜索.

核心思想和用法

矩阵题最重要的是边界: top/bottom/left/right 或 i/j 的范围. 不要凭感觉写, 先在纸上画 3x3, 1x4, 4x1 三种边界.

母题: 48 旋转图像

void rotate(vector<vector<int>>& m) {
    int n = m.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            swap(m[i][j], m[j][i]); // 主对角线转置
        }
    }
    for (int i = 0; i < n; ++i) {
        reverse(m[i].begin(), m[i].end()); // 每行翻转
    }
}

理解重点: 顺时针 90° = 先转置, 再每行左右翻转.

题目映射

73 矩阵置零: 简单版用两个 set; 进阶用第一行第一列作标记.
54 螺旋矩阵: 维护四条边, 每走完一条就收缩边界.
240 搜索二维矩阵 II: 从右上角开始, 当前值大就左移, 小就下移.

易错点

螺旋矩阵每次移动后要检查 top <= bottom, left <= right.
矩阵置零如果用第一行第一列作标记, 要额外记录第一行 / 第一列原本是否有 0.

6. 链表

如何理解题目

链表题考的是指针, 不是复杂算法. 先问:

会不会改到头节点? 会, 就加 dummy.
要不要找中点, 倒数, 环? 用快慢指针.
要不要反转一段? 先保存 next, 防止链断掉.

为什么选这些技巧

链表不能 O (1) 随机访问, 只能顺着 next 走. 所以数组里的下标技巧, 在链表里要改成指针技巧.

母题: 206 反转链表

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

理解重点: 每次只改变一条边: cur->next = prev. 改之前必须保存 nxt, 否则后半段链表丢失.

Java 单链表模板

下列是与上方 C++ 模板对应的 Java 上下文片段. dummy 统一处理删头和空链表; 反转前保存 next; 快慢指针循环条件先保护 fast 与 fast.next. 涉及局部反转或重连后, 从哨兵节点遍历并检查尾节点是否正确断链, 防止旧 next 形成环或丢失后缀.

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

ListNode removeNthFromEnd(ListNode head, int n) {
    if (n <= 0) throw new IllegalArgumentException("n must be positive");
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    for (int i = 0; i <= n; i++) {
        if (fast == null) throw new IllegalArgumentException("n exceeds list length");
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    ListNode removed = slow.next;
    slow.next = removed.next;
    removed.next = null; // 断开被删除节点,便于复用或调试时检查
    return dummy.next;
}

// 示意/练习检查: 从哨兵的 next 遍历,确认剩余链表无环且未丢失节点.
void assertListShapeFromSentinel(ListNode sentinel, int expectedNodeCount) {
    if (sentinel == null || expectedNodeCount < 0) {
        throw new IllegalArgumentException("invalid list expectation");
    }
    if (hasCycle(sentinel.next)) throw new IllegalStateException("cycle detected");

    int actualNodeCount = 0;
    ListNode tail = null;
    for (ListNode current = sentinel.next; current != null; current = current.next) {
        tail = current;
        actualNodeCount++;
    }
    if (actualNodeCount != expectedNodeCount) {
        throw new IllegalStateException("unexpected reachable node count");
    }
    if (tail != null && tail.next != null) {
        throw new IllegalStateException("tail must terminate with null");
    }
}

例如, 已知原链表有 size 个节点时, 调用方先接收返回的新头节点, 再构造测试哨兵并检查形状:

ListNode newHead = removeNthFromEnd(head, n);
ListNode sentinel = new ListNode(0);
sentinel.next = newHead;
assertListShapeFromSentinel(sentinel, size - 1);

removed.next = null 的断链语义仍应覆盖: 若要验证它, 应在 removeNthFromEnd 方法内部断言, 或让测试专用的结果类型显式暴露 removed; 保持当前标准 ListNode removeNthFromEnd(ListNode head, int n) 签名时, 调用方无法访问该局部节点, 不应伪装成可检查. 上述形状检查用于面试练习或单元测试, 不是生产热路径代码. 空链表反转返回 null, 空链表的环检测返回 false; 删除倒数第 n 个节点会显式拒绝 n <= 0 和超过链表长度的 n. 本模板是面试手写骨架, 生产代码还应按所有权, 并发和非法输入约定完善.

题目映射

160 相交链表: 两个指针分别走 A+B 和 B+A, 长度差被抵消.
141/142 环形链表: 快慢指针; 相遇后一个回头, 两个每次走一步, 再次相遇是入环点.
19 删除倒数第 N 个: 快指针先走 n 步, 再一起走.
21 合并有序链表: dummy + tail.
24/25 翻转节点: 本质是局部反转, 边界最容易错.
138 随机链表复制: 哈希表 old -> new, 或原地穿插复制.
148 排序链表: 归并排序最适合链表.
146 LRU 缓存: 哈希表 + 双向链表.

LRU 的算法理解

题目要求 get/put 都 O (1).单独用数组或链表查找不是 O (1), 单独用哈希表又无法知道谁最久未使用. 所以要组合:

哈希表: key → 链表节点, 负责 O (1) 定位.
双向链表: 维护访问顺序, 头部最新, 尾部最旧.

#include <list>
#include <unordered_map>

class LRUCache {
    int cap;
    list<pair<int, int>> cache; // front = most recent, back = least recent
    unordered_map<int, list<pair<int, int>>::iterator> pos;
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (!pos.count(key)) return -1;
        cache.splice(cache.begin(), cache, pos[key]); // 移到头部
        return pos[key]->second;
    }

    void put(int key, int value) {
        if (cap <= 0) return;
        if (pos.count(key)) {
            pos[key]->second = value;
            cache.splice(cache.begin(), cache, pos[key]);
            return;
        }
        if (cache.size() == cap) {
            int oldKey = cache.back().first;
            pos.erase(oldKey);
            cache.pop_back();
        }
        cache.push_front({key, value});
        pos[key] = cache.begin();
    }
};

面试手写 Java 版见 53 算法补充专题.

易错点

删除, 插入, 合并题优先写 dummy.
反转链表一定先保存 next.
LRU 必须同步更新 map 和 list; 删除尾节点时别忘 map erase.

7. 二叉树

如何理解题目

二叉树题先判断遍历顺序:

前序: 根 → 左 → 右, 适合复制/序列化/展开.
中序: 左 → 根 → 右, BST 中序是升序.
后序: 左 → 右 → 根, 适合从子树收集信息, 如高度, 直径, 最大路径.
层序: BFS, 适合每层, 右视图, 最短距离.

递归怎么想

不要一上来想整棵树. 只问当前节点:

空节点返回什么?
左右子树分别能给我什么信息?
我用这些信息算出什么并返回给父节点?

母题: 中序遍历 + 层序遍历

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

题目映射

104 最大深度: 后序, 深度 = max (左, 右) + 1.
226 翻转二叉树: 交换左右子树.
101 对称二叉树: 比较左子树的左/右和右子树的右/左.
543 直径: 每个节点尝试 leftDepth + rightDepth 更新答案.
98 验证 BST: 不能只比较父子, 要用上下界或中序递增.
230 第 K 小: BST 中序第 k 个.
236 最近公共祖先: 左右子树分别找 p/q, 左右都非空则当前是 LCA.
437 路径总和 III: 路径不一定从根开始, 用前缀和.
124 最大路径和: 后序返回 “向父节点贡献的最大单边路径”.

易错点

BST 验证要考虑整棵子树范围.
直径 / 最大路径和这类题通常有 “全局答案” 和 “返回给父节点的值”, 二者不是同一个东西.
层序遍历必须先固定当前层 size, 否则会把下一层混进来.

8. 图论

如何理解题目

图论不一定直接给你 “图”.矩阵, 课程依赖, 单词转换, 岛屿都可以抽象成图.

网格: 每个格子是节点, 上下左右是边.
课程表: 课程是节点, 先修关系是有向边.
腐烂橘子: 多个起点同时扩散, 是多源 BFS.

DFS / BFS 怎么选

DFS: 适合 “把一整块连通区域全部访问掉”, 如岛屿数量.
BFS: 适合 “最短步数 / 按层扩散”, 如腐烂橘子.
拓扑排序: 适合 “有依赖关系, 问能不能完成”.

母题: 200 岛屿数量

void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
    grid[i][j] = '0'; // 标记访问过,等价于把岛淹掉
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int ans = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                ans++;
                dfs(grid, i, j);
            }
        }
    }
    return ans;
}

课程表: 拓扑排序

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indeg(numCourses, 0);
    for (auto& p : prerequisites) {
        int a = p[0], b = p[1]; // 学 a 前要先学 b: b -> a
        graph[b].push_back(a);
        indeg[a]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i)
        if (indeg[i] == 0) q.push(i);

    int learned = 0;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        learned++;
        for (int next : graph[cur]) {
            if (--indeg[next] == 0) q.push(next);
        }
    }
    return learned == numCourses;
}

易错点

DFS 网格访问要标记, 否则死循环.
994 腐烂橘子要把所有初始腐烂橘子同时入队, 不是一个一个单独 BFS.
207 课程表本质是有向图判环.

9. 回溯

如何理解题目

回溯就是 “带撤销的穷举”.看到这些词优先想回溯:

所有排列, 所有组合, 所有子集.
棋盘摆放, 路径搜索.
字符串切分成所有可能.

核心思想

回溯模板只有三步:

做选择.
递归进入下一层.
撤销选择.

这对应一棵决策树. 每一层决定一个位置选什么.

母题: 46 全排列

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used,
               vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, path, used, res);
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    backtrack(nums, path, used, res);
    return res;
}

排列, 组合, 子集怎么区分

排列: 顺序不同算不同, 需要 used, 每层都从 0 开始枚举.
组合 / 子集: 顺序不同不算不同, 用 start 控制只能往后选.
可重复选择: 递归传 i.
不可重复选择: 递归传 i + 1.

题目映射

78 子集: 每个元素选或不选, 也可以用 start 枚举.
39 组合总和: 可以重复选, 下一层仍传 i.
22 括号生成: 左括号数量 < n 可放左; 右括号数量 < left 可放右.
79 单词搜索: 网格回溯, 访问过的格子要临时标记再恢复.
131 分割回文串: 枚举切割点, 只有当前段是回文才递归.
51 N 皇后: 逐行放皇后, 列, 主对角线, 副对角线不能冲突.

易错点

保存结果时要拷贝当前 path, C++ 的 res.push_back(path) 会拷贝, 没问题.
撤销必须和选择严格对称.
组合题如果忘了 start, 会出现重复答案甚至死循环.

10. 二分查找

如何理解题目

二分不是只用于 “在有序数组里找数”.只要答案空间有单调性, 也可以二分答案.

常见信号:

有序数组找目标, 找边界.
旋转有序数组.
“最小的最大值”, “最大的最小值” 这类答案单调问题.

为什么选二分

每次排除一半搜索空间, 复杂度 O (log n).二分真正难点不是思想, 而是边界写法要稳定.

推荐闭区间模板

int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1; // [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

找左边界模板

int lowerBound(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size(); // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

题目映射

35 搜索插入位置: 返回第一个 >= target 的位置.
34 首尾位置: 左边界是 lower_bound(target), 右边界可用 lower_bound(target + 1) - 1.
33 搜索旋转排序数组: 每次判断哪一半有序, 再决定去哪边.
153 寻找旋转数组最小值: 和右端比较, 决定最小值在哪半边.
74 搜索二维矩阵: 把矩阵下标映射成一维.
4 两正序数组中位数: 困难题, 核心是二分切分两个数组, 使左半都小于右半.

易错点

mid = lo + (hi - lo) / 2 防溢出.
不要混用闭区间和左闭右开模板.
旋转数组要先判断有序半区, 不能直接和普通二分一样写.

11. 栈与单调栈

如何理解题目

普通栈用于 “最近的未匹配项”.单调栈用于 “找左边 / 右边第一个更大或更小的元素”.

典型信号:

括号匹配, 表达式解析, 字符串解码: 普通栈.
每日温度, 柱状图最大矩形, 下一个更大元素: 单调栈.

母题: 20 有效括号

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return st.empty();
}

母题: 739 每日温度

vector<int> dailyTemperatures(vector<int>& t) {
    vector<int> ans(t.size(), 0);
    stack<int> st; // 存下标,栈内温度单调递减
    for (int i = 0; i < t.size(); ++i) {
        while (!st.empty() && t[i] > t[st.top()]) {
            int j = st.top(); st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

理解重点: 栈里放的是 “还没等到更高温度的日子”.当前温度更高时, 就能结算栈顶.

题目映射

155 最小栈: 一个数据栈 + 一个最小值栈.
394 字符串解码: 遇到 [ 保存当前数字和字符串, 遇到 ] 弹出组合.
84 柱状图最大矩形: 单调递增栈, 出栈时确定当前柱子的左右边界.

易错点

单调栈通常存下标, 不只存值, 因为答案常需要距离或宽度.
84 柱状图常在两端加哨兵 0, 简化清栈边界.

12. 堆 / 优先队列

如何理解题目

堆适合动态维护最大值或最小值. 看到 Top K, 数据流, 中位数, 频率排名, 就想堆.

为什么选堆

排序是 O (n log n).如果只要 K 个元素, 用大小为 K 的堆可以做到 O (n log K).

母题: 215 数组中的第 K 个最大元素

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
    for (int x : nums) {
        pq.push(x);
        if (pq.size() > k) pq.pop(); // 弹出最小,留下 K 个最大
    }
    return pq.top();
}

理解重点: 求第 K 大, 用小顶堆维护 K 个最大值. 堆顶是这 K 个最大值里最小的, 也就是全局第 K 大.

题目映射

347 前 K 高频元素: 先哈希计数, 再按频率建堆.
295 数据流中位数: 左边大顶堆, 右边小顶堆, 维护两边大小差不超过 1.
23 合并 K 个有序链表: 小顶堆每次取当前最小节点.

易错点

C++ 默认 priority_queue<int> 是大顶堆; 小顶堆要写 greater<int>.
Top K 大用小顶堆, Top K 小用大顶堆.
数据流中位数要同时维护大小平衡和左右大小关系.

13. 贪心

如何理解题目

贪心是 “每一步做当前看起来最好的选择”.但不是所有最优问题都能贪心. 你要能解释为什么局部最优不会破坏全局最优.

典型信号:

只需要一次扫描维护某个最优状态.
区间切分, 跳跃覆盖, 买卖股票一次交易.
每一步选择有明确不可逆优势.

母题: 121 买卖股票的最佳时机

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    int minPrice = prices[0], ans = 0;
    for (int p : prices) {
        minPrice = min(minPrice, p);
        ans = max(ans, p - minPrice);
    }
    return ans;
}

理解重点: 如果今天卖出, 要让利润最大, 就应该在今天之前最低价买入. 所以扫描时维护历史最低价.

母题: 55 跳跃游戏

bool canJump(vector<int>& nums) {
    int farthest = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > farthest) return false;
        farthest = max(farthest, i + nums[i]);
    }
    return true;
}

核心思想: 不关心具体怎么跳, 只关心目前能覆盖到的最远位置.

题目映射

45 跳跃游戏 II: 在当前步数能覆盖的范围内, 选择下一步能到的最远位置.
763 划分字母区间: 每段必须覆盖段内所有字符的最后出现位置.

易错点

贪心需要证明, 不能看到 “最大 / 最小” 就硬贪.
55 问能不能到, 45 问最少几步, 状态变量不同.

14. 动态规划

如何理解题目

动态规划适合 “最优值 / 方案数 / 可行性”, 并且问题能拆成重复子问题.

读 DP 题按五步:

状态定义: dp[i] 或 dp[i][j] 表示什么?
转移方程: 当前状态从哪些旧状态来?
初始化: 空串, 0 金额, 第一行第一列是什么?
遍历顺序: 从前往后, 从后往前, 外层物品还是容量?
答案位置: 返回 dp[n], max(dp) 还是别的?

单维 DP 母题: 70 爬楼梯

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

理解重点: 到第 i 阶只有两种来源: 从 i-1 走一步, 或从 i-2 走两步.

背包母题: 322 零钱兑换

int coinChange(vector<int>& coins, int amount) {
    const int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int c : coins) {
            if (i >= c) dp[i] = min(dp[i], dp[i - c] + 1);
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

理解重点: dp[i] 表示凑出金额 i 的最少硬币数. 最后一枚硬币如果是 c, 那么前面要先凑出 i - c.

多维 DP 母题: 1143 最长公共子序列

int longestCommonSubsequence(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

理解重点: dp[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符的 LCS 长度. 数组开 m+1/n+1 是为了表示空串.

题目映射

198 打家劫舍: 当前位置偷或不偷.
279 完全平方数: 类似零钱兑换.
139 单词拆分: dp[i] 表示前 i 个字符能否拆分.
300 LIS: dp[i] 表示以 i 结尾的最长递增子序列; 进阶用贪心 + 二分.
152 乘积最大子数组: 负数会让最大最小互换, 所以同时维护 max/min.
416 分割等和子集: 转成 01 背包, 能否凑出 sum/2.
62/64 网格路径: 状态来自上方和左方.
5 最长回文子串: 中心扩展更直观; DP 也可.
72 编辑距离: 增, 删, 改三种操作取最小.

易错点

DP 最大难点不是代码, 是状态定义. 状态定义错, 后面全错.
01 背包一维优化容量要倒序; 完全背包容量通常正序.
初始化经常决定成败, 比如 dp[0] = 0, 空串状态, 第一行第一列.

15. 技巧题

如何理解题目

技巧题通常有特殊限制: O (1) 空间, 不能修改数组, 线性时间, 数字出现次数有规律. 它们不像常规模板, 更像固定套路.

位运算: 136 只出现一次的数字

int singleNumber(vector<int>& nums) {
    int x = 0;
    for (int n : nums) x ^= n;
    return x;
}

理解重点: a ^ a = 0, a ^ 0 = a, 所有成对数字抵消, 剩下单独的数.

摩尔投票: 169 多数元素

int majorityElement(vector<int>& nums) {
    int cand = 0, vote = 0;
    for (int x : nums) {
        if (vote == 0) cand = x;
        vote += (x == cand) ? 1 : -1;
    }
    return cand;
}

理解重点: 多数元素出现次数超过一半, 它和其他元素两两抵消后一定还能剩下.

题目映射

75 颜色分类: 三指针, 0 放左边, 2 放右边, 1 留中间.
31 下一个排列: 从右找第一个升序对, 交换后反转后缀.
287 寻找重复数: 把数组值当 next 指针, 转成链表找环.

易错点

技巧题要记 “触发条件”:看到成对抵消想异或, 看到超过一半想摩尔投票, 看到数组值指向下标想 Floyd 环.
287 不允许修改数组时, 不能排序, 不能原地哈希.

核心题完整教学单元

学习目标: 能为下列高频题从约束推导出算法, 手写代码, 并用复杂度和边界用例验证. 这里是题库中的具体题解; 排序, 并查集和二维前缀和等通用专题见算法补充专题, 内存放不下时的变体见海量数据处理. 以下均为遵守题目输入约束的 C++17 上下文片段.

142. 环形链表 II: 相遇不是入口, 第二次相遇才是

Floyd 快慢指针相遇时, 慢指针走了 a+b 步, 快指针走了 2(a+b) 步; 设环长为 L, 则 a+b 是 L 的倍数. 令一指针回头, 两者每次走一步, 回头指针走 a 步到入口, 另一指针也从相遇点走 a 步回到入口.

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    do {
        if (!fast || !fast->next) return nullptr;
        slow = slow->next;
        fast = fast->next->next;
    } while (slow != fast);
    ListNode* entry = head;
    while (entry != slow) { entry = entry->next; slow = slow->next; }
    return entry;
}

时间 O(n), 额外空间 O(1). 边界: 空链表, 单节点无环返回 nullptr; 单节点自环返回该节点. 不要在第一次相遇时直接返回.

98. 验证二叉搜索树: 约束来自全部祖先

只比较父子节点会漏掉 “根为 5, 右子树里有 4”.递归时携带开区间 (low, high); 当前值必须严格位于其中, 左右子树分别收紧上界或下界.

bool valid(TreeNode* node, long long low, long long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return valid(node->left, low, node->val) && valid(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) {
    return valid(root, LLONG_MIN, LLONG_MAX);
}

时间 O(n), 递归栈 O(h). 边界: 空树合法; 节点值为 INT_MIN/INT_MAX 时仍正确, 因为边界使用 long long; BST 不允许重复值 (本题约束).

236. 最近公共祖先: 子树报告 “找到谁”

后序递归的返回值不是 “祖先”, 而是 “ 当前子树找到的 p 或 q“.当前节点等于目标则向上报告; 左右各报告一个目标时, 当前节点首次汇合, 故为 LCA.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

时间 O(n), 栈 O(h). 边界: 一个目标是另一个目标祖先时返回祖先; 题目保证两个节点存在, 若业务代码不保证, 应先验证两个节点是否均被找到.

124. 二叉树最大路径和: 向上只能交出单边

一条路径在当前节点可以取 leftGain + value + rightGain, 但给父节点的路径不能分叉, 只能选较大的单边. 负贡献应丢弃为 0, 避免拖低路径.

int maxPathSum(TreeNode* root) {
    int answer = INT_MIN;
    function<int(TreeNode*)> gain = [&](TreeNode* node) {
        if (!node) return 0;
        int left = max(0, gain(node->left));
        int right = max(0, gain(node->right));
        answer = max(answer, node->val + left + right);
        return node->val + max(left, right);
    };
    gain(root);
    return answer;
}

时间 O(n), 栈 O(h). 边界: 全负树必须返回最大的那个节点, 故全局答案初始化为 INT_MIN, 不能初始化为 0.

33 与 34: 二分先固定区间语义

33 每轮至少一半严格有序, 先判有序半区, 再判断 target 是否落在该半区.34 则把 “找位置” 转成 “找第一个满足谓词的位置”.

int searchRotated(vector<int>& a, int target) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}
vector<int> searchRange(vector<int>& a, int target) {
    auto firstGE = [&](int x) {
        int lo = 0, hi = static_cast<int>(a.size());
        while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= x) hi = mid; else lo = mid + 1; }
        return lo;
    };
    int left = firstGE(target), right = firstGE(target + 1) - 1;
    return left < static_cast<int>(a.size()) && a[left] == target ? vector<int>{left, right} : vector<int>{-1, -1};
}

二者时间均为 O(log n), 空间 O(1). 33 的前提是元素互异; 34 要测试空数组, 目标在首 / 尾, 全数组相等. target + 1 只适用于本题值域不会使 int 溢出的约束; 通用代码应写 “ 第一个 > target“ 的谓词.

239. 滑动窗口最大值: 队首永远是候选最大值

双端队列存下标, 且对应值递减. 新值进入前, 尾部所有不大于它的元素以后不可能成为最大值, 全部删除; 队首过期 (下标 < i-k+1) 则删除.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q; vector<int> ans;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();
        while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
        q.push_back(i);
        if (i >= k - 1) ans.push_back(nums[q.front()]);
    }
    return ans;
}

时间 O(n)(每个下标最多进出一次), 空间 O(k). 边界: k=1 输出原数组; k=n 只输出一个最大值; 实际接口应拒绝 k<=0 或 k>n, LeetCode 输入保证合法.

287. 寻找重复数: 数组值构成链表

值域为 [1,n] 且数组长度 n+1, 因此从下标 0 沿 next=nums[index] 行走必进环; 重复值就是环入口. 不能排序或修改数组时, 这是 O(1) 空间解.

int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];
    do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
    int entry = nums[0];
    while (entry != slow) { entry = nums[entry]; slow = nums[slow]; }
    return entry;
}

时间 O(n), 空间 O(1). 边界: 重复值可以出现两次以上; 索引从 0 起但值从 1 起正是构图成立的条件, 业务数组不满足该值域时不可直接复用.

31, 41, 238: 原地不变量与双向前后缀

31 从右找第一个 a[i] < a[i+1] 的位置; 右侧已是最大降序后缀, 交换为刚好更大的值后反转后缀得到最小增序.41 仅关心 [1,n], 不断把 x 放在 a[x-1]. 238 先写每个位置左积, 再乘右积, 避开除法与零.

void nextPermutation(vector<int>& a) {
    int i = static_cast<int>(a.size()) - 2;
    while (i >= 0 && a[i] >= a[i + 1]) --i;
    if (i >= 0) { int j = static_cast<int>(a.size()) - 1; while (a[j] <= a[i]) --j; swap(a[i], a[j]); }
    reverse(a.begin() + i + 1, a.end());
}
int firstMissingPositive(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; ++i)
        while (a[i] >= 1 && a[i] <= n && a[a[i] - 1] != a[i]) swap(a[i], a[a[i] - 1]);
    for (int i = 0; i < n; ++i) if (a[i] != i + 1) return i + 1;
    return n + 1;
}
vector<int> productExceptSelf(vector<int>& a) {
    int n = a.size(); vector<int> ans(n, 1); int left = 1, right = 1;
    for (int i = 0; i < n; ++i) { ans[i] = left; left *= a[i]; }
    for (int i = n - 1; i >= 0; --i) { ans[i] *= right; right *= a[i]; }
    return ans;
}

三题均为时间 O(n); 31 额外空间 O(1), 41 O(1), 238 除输出数组外 O(1). 边界: 31 全降序如 [3,2,1] 变 [1,2,3]; 41 [1,1] 返回 2, 全负数返回 1; 238 含一个或多个 0 时仍由前后缀自然得到正确结果.

可复用模板: 窗口, 队列, BFS, 迭代树, 背包顺序

// 返回任一可达格子到最近源点的最大边数;无源点返回 -1,源点距离为 0.
int multiSourceBfsMaxDistance(vector<vector<int>>& grid, vector<pair<int, int>> sources) {
    if (sources.empty()) return -1;
    if (grid.empty() || grid[0].empty()) throw invalid_argument("sources require a non-empty grid");
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    for (const auto& row : grid) if (static_cast<int>(row.size()) != cols) {
        throw invalid_argument("grid must be rectangular");
    }

    queue<pair<int, int>> q;
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    for (auto [r, c] : sources) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) throw out_of_range("source out of bounds");
        if (!visited[r][c]) { visited[r][c] = true; q.push({r, c}); }
    }
    int distance = 0;
    constexpr int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        int levelSize = static_cast<int>(q.size());
        bool expandedNextLevel = false;
        while (levelSize-- > 0) {
            auto [r, c] = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) continue;
                visited[nr][nc] = true; // 入队时标记,避免重复入队.
                q.push({nr, nc});
                expandedNextLevel = true;
            }
        }
        if (expandedNextLevel) ++distance;
    }
    return distance;
}
vector<int> inorderIterative(TreeNode* root) {
    vector<int> out; stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) { st.push(root); root = root->left; }
        root = st.top(); st.pop(); out.push_back(root->val); root = root->right;
    }
    return out;
}

滑动窗口的不变量是 “扩张后, 持续左缩直到重新合法”; 单调队列的不变量是 “候选值单调且下标未过期”.上述 BFS 将全部格子视为可通行; 障碍格应在扩展前增加可通行判断. BFS 必须在入队时标记, 否则同一节点可能被重复入队; 空图和无源点分别按接口约定返回. 时间 O(rows*cols), 额外空间 O(rows*cols). 迭代中序对空树输出空数组, 时间 O(n), 栈 O(h).

01 背包的每件物品只能取一次, 所以容量必须倒序: for (c = cap; c >= w; --c), 否则当前物品刚写入的 dp[c-w] 会在同轮被再次使用. 完全背包允许重复取, 故容量正序: for (c = w; c <= cap; ++c). 练习边界: 容量小于全部重量应保持 dp[cap]=0; 重量为 0 的物品要单独按题意处理, 不能套上述循环.

主题练习与预期证据

手写 239, 输入 [1,3,-1,-3,5,3,6,7], k=3, 预期 [3,3,5,5,6,7], 并能解释每个下标为何只出队一次.
为 124 写全负树 [-3,-2,-1] 的测试, 预期 -1; 为 41 写 [3,4,-1,1], 预期 2.
不看答案说明 287 为什么不能使用 “值为 0” 或越界的业务数组. 预期证据是写出值域到有环映射的前提, 而不是只背 Floyd 名称.

第一梯队 (必刷, 中小厂够用): 本文 ⭐ 标记的题. 尤其 146 LRU, 链表全套, 二叉树遍历, 岛屿数量, 爬楼梯/打家劫舍/零钱兑换, 买卖股票, 20 有效括号.
第二梯队 (冲大厂): 其余中等题.
第三梯队 (△ 困难, 选刷): 42 接雨水, 4 中位数, 23 合并 K 个, 25 K 个一组, 84 柱状图, 124 最大路径和, 51 N 皇后, 72 编辑距离. 时间不够可以缓刷, 但要知道题型.

学习方法

先学模板再刷题: 不要一上来硬刷. 先把每类母题理解清楚.
每题都问 “为什么”: 为什么不是暴力? 为什么这个算法能降复杂度? 为什么边界这样写?
手写 + 口述复杂度: 面试时要边写边讲, 不能只会提交.
二刷三刷: 第一遍看题解理解, 第二遍独立写, 第三遍默写模板.
建立错题本: 记录卡在哪个判断, 哪个边界, 哪个数据结构.

Keyboard shortcuts

Android 中级面试复习手册