LeetCode Hot 100 算法清单

本清单即 LeetCode 热题 HOT 100,共 100 题,业界公认的标准刷题集。分类与顺序合理:按「数据结构由易到难 + 算法思想递进」组织。

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

如何使用

• 第一轮:只刷 ⭐ 高频题,建立每类的解题模板(约 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。

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

读题时先问 5 个问题：

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

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

我先看题目特征：xxx。暴力会是 O(…)，输入规模不允许。所以我选 xxx 算法。核心是 xxx。实现上维护 xxx，最后复杂度是 xxx。

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. 双指针

如何理解题目

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

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

为什么选双指针

暴力通常枚举两个位置 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 sum = (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) {
    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，否则后半段链表丢失。

题目映射

• 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 (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();
    }
};

易错点

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

7. 二叉树

如何理解题目

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

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

递归怎么想

不要一上来想整棵树。只问当前节点：

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

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

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) {
    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. 回溯

如何理解题目

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

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

核心思想

回溯模板只有三步：

1. 做选择。
2. 递归进入下一层。
3. 撤销选择。

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

母题：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) {
    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 题按五步：

1. 状态定义：dp[i] 或 dp[i][j] 表示什么？
2. 转移方程：当前状态从哪些旧状态来？
3. 初始化：空串、0 金额、第一行第一列是什么？
4. 遍历顺序：从前往后、从后往前、外层物品还是容量？
5. 答案位置：返回 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 不允许修改数组时，不能排序、不能原地哈希。

刷题策略总结

高频母题(背到能默写)

反转链表、二叉树三种遍历 + 层序、二分模板、回溯模板、滑动窗口模板、01 背包 / 完全背包 / LCS。这些模板覆盖了 Hot 100 的大多数题。

针对中级 Android 的优先级

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

学习方法

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