HHot 100C++ 图解

LeetCode 热题 100 · C++17 · 中文讲解

把一百道题,
读成十七个套路。

每题配原题描述、分步思路、复杂度与易错点、可运行的 C++17 题解和单元测试;78 道题能一帧一帧看算法怎么走。

题目
100
分类
17
算法动画
78
单元测试
100
01

哈希

把「查找另一个值」从重复扫描变成常数时间查询。

0/3
  1. 1 两数之和哈希存「值→下标」,查 target-x 简单
  2. 49 字母异位词分组排序后的串当分组 key 中等
  3. 128 最长连续序列set + 只在连续段起点向右扩 中等
02

双指针

利用有序性或两端信息,让两个指针只朝答案收缩。

0/4
  1. 283 移动零快慢指针:非零元素往前搬 简单
  2. 11 盛最多水的容器对撞指针,每次移动较矮的一侧 中等
  3. 15 三数之和排序 + 固定一个数 + 双指针,逐位去重 中等
  4. 42 接雨水双指针维护 leftMax / rightMax 困难
03

滑动窗口

维护一个始终满足约束的连续区间,避免重复计算。

0/2
  1. 3 无重复字符的最长子串右扩,撞重复把 left 跳到重复位之后 中等
  2. 438 找到字符串中所有字母异位词定长窗口 + 计数比较,进出各 O(1) 中等
04

子串 / 前缀和

用前缀信息或窗口把连续区间问题拆成可复用的状态。

0/3
  1. 560 和为 K 的子数组前缀和 + 哈希计数(有负数不能用滑窗) 中等
  2. 239 滑动窗口最大值单调递减双端队列,队头即窗口最大值 困难
  3. 76 最小覆盖子串滑窗 + need/window 计数,先扩后缩 困难
05

普通数组

围绕下标、原地状态和局部不变量组织一次或有限次扫描。

0/5
  1. 53 最大子数组和Kadane:cur 变负就从下一位重启 中等
  2. 56 合并区间按左端排序 + 合并相交区间 中等
  3. 189 轮转数组整体反转 + 两段各自反转 中等
  4. 238 除自身以外数组的乘积左右两遍前缀积,不用除法 中等
  5. 41 缺失的第一个正数下标即哈希桶:用正负号标记谁出现过 困难
06

矩阵

把二维坐标关系转成有边界的行列遍历或原地标记。

0/4
  1. 73 矩阵置零借第一行第一列当标记位,O(1) 空间 中等
  2. 54 螺旋矩阵四条边界收缩,走完一条砍一条 中等
  3. 48 旋转图像顺时针 = 转置 + 每行左右翻转 中等
  4. 240 搜索二维矩阵 II从右上角出发,大了左移、小了下移 中等
07

链表

指针不能丢:先保存 next,再改变连接关系。

0/14
  1. 160 相交链表先对齐起点:长链表多走差值步 简单
  2. 206 反转链表三指针迭代反转 / 递归版 简单
  3. 234 回文链表快慢找中 + 反转后半 + 逐一比对 简单
  4. 21 合并两个有序链表哨兵头结点 + 逐一接较小者 简单
  5. 2 两数相加逐位相加,哨兵结点简化尾插 中等
  6. 19 删除链表的倒数第 N 个结点快指针先走 n 步,再同步走到尾部 中等
  7. 24 两两交换链表中的节点dummy + 每次交换相邻一对 中等
  8. 25 K 个一组翻转链表数够 k 个就整组反转,再串接 困难
  9. 138 随机链表的复制原地把 next 指向克隆结点,再拆两条链 中等
  10. 148 排序链表归并:快慢找中 + 递归 + 合并两链 中等
  11. 23 合并 K 个升序链表小顶堆按值合并 k 路 / 分治 困难
  12. 146 LRU 缓存哈希表 + 双向链表,get/put 都 O(1) 中等
  13. 141 环形链表Floyd 快慢指针,相遇即有环 简单
  14. 142 环形链表 IIa=(k-1)(b+c)+c → 从头与从相遇点同速 中等
08

二叉树

每个节点都问同一个递归问题,再把左右子树答案合并。

0/15
  1. 94 二叉树的中序遍历迭代栈 / Morris;递归就是左根右 简单
  2. 104 二叉树的最大深度递归 max(左高,右高)+1 简单
  3. 226 翻转二叉树递归交换左右孩子 简单
  4. 101 对称二叉树递归比较(左左,右右)与(左右,右左) 简单
  5. 543 二叉树的直径后序:过每个结点的直径=左高+右高 简单
  6. 102 二叉树的层序遍历BFS 按层出队,用 size 定层宽 中等
  7. 108 将有序数组转换为二叉搜索树取中点做根,左右两半递归 简单
  8. 98 验证二叉搜索树上下界区间收缩(只比父子会错) 中等
  9. 230 二叉搜索树中第 K 小的元素中序遍历第 k 个 / BST 迭代器 中等
  10. 199 二叉树的右视图BFS 每层最后一个结点 中等
  11. 114 二叉树展开为链表先序展开:左子树右端接右子树 中等
  12. 105 从前序与中序遍历序列构造二叉树前序定根 + 中序切两半(下标哈希加速) 中等
  13. 437 路径总和 III树上前缀和 + 哈希(Q560 的树版) 中等
  14. 236 二叉树的最近公共祖先后序:两侧都有即答案,否则返回非空那侧 中等
  15. 124 二叉树中的最大路径和DFS 只返回「单边贡献」,答案全局取 max 困难
09

图论

把「连通、依赖、扩散」转成 DFS、BFS 或拓扑序。

0/4
  1. 200 岛屿数量网格 DFS 洪水填充沉岛 中等
  2. 994 腐烂的橘子多源 BFS 按层扩散 + fresh 计数收尾 中等
  3. 207 课程表拓扑排序判环(Kahn / DFS 三色) 中等
  4. 208 实现 Trie(前缀树)26 叉树 + isEnd 区分词与前缀 中等
10

回溯

选择、递归、撤销选择,枚举搜索树并尽早剪枝。

0/8
  1. 46 全排列used[] 标记,选满 n 个即收集 中等
  2. 78 子集每个结点都是答案;传 start 防重复 中等
  3. 17 电话号码的字母组合多叉树按数字逐层展开 中等
  4. 39 组合总和组合回溯,递归传 i 允许重复选 中等
  5. 22 括号生成open<n 才能加左,close<open 才能加右 中等
  6. 79 单词搜索网格 DFS + 占位符标记,回溯时还原 中等
  7. 131 分割回文串区间 DP 预处理回文表 + 切分回溯 中等
  8. 51 N 皇后逐行放皇后,cols / 两条 diag 三个标记 困难
12

栈

栈保存「最近还没解决」的状态,适合嵌套和单调关系。

0/5
  1. 20 有效的括号左括号入栈,右括号配栈顶 + 结束判空 简单
  2. 155 最小栈辅助最小栈同步压入/弹出 中等
  3. 394 字符串解码双栈处理嵌套:数字栈 + 字符串栈 中等
  4. 739 每日温度单调递减栈求右向第一个更大 中等
  5. 84 柱状图中最大的矩形单调递增栈 + 首尾 0 哨兵结算宽度 困难
13

堆

只维护当前最需要的少量候选,不必全排序。

0/3
  1. 215 数组中的第 K 个最大元素K 个小顶堆 / 随机化快速选择 中等
  2. 347 前 K 个高频元素按频次桶排序(值域有界比堆更快) 中等
  3. 295 数据流的中位数对顶堆:大顶装小半、小顶装大半 困难
14

贪心

每一步做可证明的局部最优,把全局问题逐步缩小。

0/4
  1. 121 买卖股票的最佳时机边走边记历史最低价,当天价减它取最大 简单
  2. 55 跳跃游戏贪心维护最远可达 reach,不可达即失败 中等
  3. 45 跳跃游戏 IIBFS 分层视角:走到边界才 +1 步 中等
  4. 763 划分字母区间记录每个字母末次位置 + 区间合并 中等
15

动态规划(一维)

把大问题写成状态,让每个状态只算一次。

0/10
  1. 70 爬楼梯dp[i]=dp[i-1]+dp[i-2],滚动两变量 简单
  2. 118 杨辉三角tri[i][j]=上一行相邻两数之和 简单
  3. 198 打家劫舍偷/不偷:max(prev1, prev2+x) 中等
  4. 279 完全平方数完全背包求最少平方数个数 中等
  5. 322 零钱兑换完全背包求最少硬币(贪心必错) 中等
  6. 139 单词拆分dp[i]=前 i 个能否拆成词典词(布尔背包) 中等
  7. 300 最长递增子序列tails[k]=长度 k 的最小结尾 + lower_bound 中等
  8. 152 乘积最大子数组同时维护最大积与最小积,遇负交换 中等
  9. 416 分割等和子集0-1 背包判定,一维数组必须逆序 中等
  10. 32 最长有效括号栈底存最后一个破坏位 / 也可区间 DP 困难
16

多维动态规划

明确 dp[i][j] 的含义,再按依赖方向填表。

0/5
  1. 62 不同路径dp[j]+=dp[j-1] 滚动一行;等价 C(m+n-2,m-1) 中等
  2. 64 最小路径和格值 + min(上,左),首行首列单独初始化 中等
  3. 5 最长回文子串枚举 2n-1 个中心向两边扩(奇偶都要) 中等
  4. 1143 最长公共子序列相等取对角+1,不等取 max(上,左) 中等
  5. 72 编辑距离替换/删除/插入三格取最小 +1 中等
17

技巧

借助位运算、数学规律或原地映射压缩空间。

0/5
  1. 136 只出现一次的数字全体异或,成对的自动抵消 简单
  2. 169 多数元素摩尔投票,O(1) 空间 简单
  3. 75 颜色分类荷兰国旗三向切分;遇 2 交换后 i 不动 中等
  4. 31 下一个排列找下降位→换「刚好更大」的→反转后缀 中等
  5. 287 寻找重复数值当下一跳构成链表 → Floyd 找环入口 中等

↑↓ 选择↵ 打开/ 随时唤起