HHot 100C++ 图解

套路速查

十七类题,各自的那几行心法

摘自每个分类源文件开头的总结。做完一类题再回来读一遍,比单题刷十遍更管用。

01

哈希

Hash

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

【本类题的通用思路】 哈希表的本质是「用 O(n) 空间,把一次线性扫描变成 O(1) 查询」。 凡是看到「是否存在配对 / 出现过几次 / 属于同一组」,先想哈希。 三个高频坑: 1) 边查边存 —— 避免同一个元素和自己配对(Q1 的 [3,3]) 2) unordered_map 的 key 可以是 string / 数组签名,但不能直接用 vector<int> 3) 判断「连续」时要先去重,否则 1,1,1,2 会算错长度(Q128)
02

双指针

Two Pointers

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

【套路】 1) 对撞指针:有序 / 能判断「往哪边走更优」时,l 与 r 相向而行,O(n)。 2) 快慢指针:原地搬运元素(去重、移动零)或找环。 3) 双指针去重:排序后在同一层跳过重复值。以 Q15 为例: 外层 if (i > 0 && nums[i] == nums[i - 1]) continue; 内层 while (l < r && nums[l] == nums[l + 1]) ++l; 这是所有「返回所有不重复组合」题的通用手法。
03

滑动窗口

Sliding Window

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

【窗口三问】写滑动窗口前先答清楚: 1. 右边界进来时,窗口被破坏的条件是什么?(更新状态) 2. 什么时候必须收缩左边界?(while 条件) 3. 答案在收缩前更新还是收缩后更新?(取值时机) 定长窗口(Q438)用 if 每步弹出一个;变长窗口有两种写法: while 逐步缩到合法(Q76),或直接把 left 跳到破坏点之后(Q3 的「跳跃式」)。
04

子串 / 前缀和

Substring & Prefix Sum

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

【两个新工具】 1) 前缀和 + 哈希:区间和 = pre[r] - pre[l-1]。要「和为 K 的子数组个数」, 就是对每个 r 数有多少个 l 满足 pre[l] = pre[r] - K —— 计数查表 O(n)。 注意:有负数时滑动窗口失效(窗口和不单调),只能用前缀和。 2) 单调队列 / 单调栈:维护一个「候选最优」的递减(递增)序列, 队首始终是当前窗口最值 —— 每个元素进出队各一次,均摊 O(1)。
05

普通数组

Array

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

【本组的思维母题】 · 一维 DP 入门:Q53 的「以 i 结尾的最大和」是最大子数组问题的原型。 · 排序 + 扫描:区间题几乎都是「按左端点排序后线性合并」。 · 原地 O(1) 空间:数组下标本身就是哈希表(Q41 索引标记、Q189 三次反转)。
06

矩阵

Matrix

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

【套路】 1) 边界收缩法:用 top/bottom/left/right 四个变量描述尚未走完的矩形, 每走完一条边就收缩一次 —— 螺旋类题目的万能模板,比「方向数组 + 转向」少想很多。 2) 借用第一行/第一列当标记位,把 O(m+n) 额外空间压成 O(1); 但要单独记住「第一行/第一列本身是否要置零」,否则会互相污染。 3) 阶梯查找:矩阵行列双有序时,从右上角出发,比目标小就下移、大就左移, O(m+n)。左下角同理。绝不能用普通二分(整体不是单调的)。
07

链表

Linked List

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

【链表通用心法】 1) 哨兵结点 dummy:凡是「头结点可能被删/被换」的题,一律从 dummy 出发, 最后 return dummy.next。能消掉 90% 的头结点特判。 2) 快慢指针三件套:找中点、找倒数第 k、判环。 3) 反转是基本功:prev / cur / nxt 三个指针,先存 nxt 再改链。 4) 判环的数学:设 head→入口 = a,入口→相遇点 = b,相遇点→入口 = c,环长 L = b + c。 相遇时 slow 走了 a+b,fast 走了 a+b+kL,而 fast = 2·slow ⇒ a+b 是 L 的整数倍, 所以 a ≡ c (mod L) —— 一个指针回到 head、两个各走 1 步,必在入口相遇(推导见 Q142)。 5) 测试里造过环的链表不好统一释放,本文件部分用例故意让进程退出时回收。
08

二叉树

Binary Tree

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

【递归的两种姿势 —— 想清楚这个,二叉树题就通了】 A. 「自顶向下」:参数里带上下文(路径和、上下界、前缀和表), 像前序遍历,进入结点时先处理携带的信息。例:Q113 路径总和、Q437。 B. 「自底向上」:返回值里带信息(高度、链贡献、最大贡献), 像后序遍历,用左右子树的返回值算出本结点的答案。例:Q104、Q543、Q124。 另外两条主线: · BFS + 分层 for 循环 = 所有「按层」问题(Q102 层序、Q199 右视图、Q103 锯齿)。 · BST 的中序遍历严格递增 —— Q98 / Q230 / Q538 / Q700 都靠这一句话。
09

图论

Graph

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

【网格就是图】 m×n 的网格里每个格子是结点,上下左右(有时含对角)是边。于是: · 求连通块个数 -> DFS/BFS 把访问过的「沉掉」(Q200) · 多源最短步数 -> 把所有源点同时入队做 BFS(Q994、Q127、Q130) · 判有没有环 -> 拓扑排序:能出完 n 个点就无环(Q207) 注意 DFS 递归深度 = 连通块大小,300×300 全 1 的网格会到 9 万层, 真实工程里应改 BFS 或手写栈;面试口头说明这点即可。
10

回溯

Backtracking

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

【回溯 = 在决策树上做 DFS】 模板永远是这三行: 选择 -> 递归下一层 -> 撤销选择 写之前先回答三个问题: 1. 决策树的「一层」是什么?(选一个元素 / 放一行皇后 / 加一个括号) 2. 何时算到达路径终点、可以收集答案?(长度够了 / 和等于 target / 无更多可选) 3. 剪枝条件是什么?(越界、重复、数量不合法、和已经超过 target) start 参数的三种形态,正是「排列 / 组合 / 子集」的区别: · 组合、子集:下一层传 i+1(不回头,天然无序,避免 {1,2} 与 {2,1} 重复) · 可重复使用的组合(Q39):下一层传 i(允许再选自己) · 排列:不用 start,每层从 0 扫,靠 used[] 排除已在路径里的元素
12

栈

Stack

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

【单调栈:一类题一个模板】 求「左边/右边第一个更大/更小的元素」,全都用单调栈: for each x: while (栈顶破坏了单调性) { 弹出并结算 } 此刻栈顶就是 x 要找的那个「第一个更大/更小者」 x 入栈 栈内维持什么,取决于你要找什么: · 找「右边第一个更大」-> 栈递减(Q739 每日温度) · 找「左右第一个更小」-> 栈递增(Q84 柱状图) 为什么是 O(n):每个下标最多入栈一次、出栈一次。 另一个大类:括号匹配 / 嵌套结构 -> 普通栈(Q20、Q394、Q150、Q224)。 顺带一提:Q42 接雨水也能用单调栈(按「凹槽」逐层结算),和双指针法互为验证。
13

堆

Heap / Priority Queue

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

【三件套】 1. 「第 K / 前 K」问题 -> 维护大小为 K 的堆,比全排序 O(n log n) 优: · 求第 K 大:用小顶堆装 K 个最大的(堆顶是这 K 个里最小的 = 答案) · 求前 K 高频:小顶堆按频次淘汰,或桶排序做到 O(n) 记忆口诀:第 K 大用小顶堆,第 K 小用大顶堆(堆顶是「守门员」)。 2. 「流式 / 动态求中位数、第 K 小」-> 对顶堆: 大顶堆装较小的一半,小顶堆装较大的一半,保持两堆 size 差 <= 1, 中位数就在两个堆顶之间(Q295、Q480、Q502 都能套)。 3. C++ 的 priority_queue 默认是「大顶堆」! 小顶堆要显式写:priority_queue<int, vector<int>, greater<int>> 自定义比较时注意:comp(a,b)==true 表示 a 的优先级低于 b(跟 sort 相反方向)。
14

贪心

Greedy

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

【贪心能不能用,看两件事】 1. 贪心选择性质:局部最优选择不会影响后续的可解性(能证明「exchange argument」: 把任一最优解的第一步换成我的贪心选择,解不会变差)。 2. 最优子结构:剩下的子问题的最优解 + 我的选择 = 全局最优。 不满足就必须上 DP。经典反例:零钱兑换用「每次取最大面额」是错的 (coins=[1,3,4], amount=6:贪心得 4+1+1 三张,最优是 3+3 两张 —— 见 Q322)。 跳跃类题目的统一视角:把「能到达的最远处」当成贪心状态, 能到 i 才能从 i 出发(Q55 判可达、Q45 数步数、Q1306/Q1345 同理)。
15

动态规划(一维)

Dynamic Programming

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

【写 DP 的固定五问】 1. 状态怎么定义?(dp[i] 表示「以 i 结尾」还是「前 i 个」?这一步错了后面全错) 2. 转移方程是什么?(dp[i] 由哪些更小的状态算出 —— 就是「最后一步有几种走法」) 3. 边界/初始化?(dp[0] 表示空;「凑不出」一般设成 +INF/-1 之类的哨兵) 4. 遍历顺序?(依赖前一个 -> 正序;0-1 背包用一维时必须逆序,见 Q416) 5. 返回值在哪?(不一定在 dp[n],Q300/Q152 要取 max(dp[i])) 【三类一维 DP 的识别信号】 · 线性递推(爬楼梯、打家劫舍):只依赖前 1~2 项 -> 两个变量滚动,空间 O(1)。 · 背包(零钱、完全平方、等和子集):dp[容量], 完全背包(可重复选)内层正序;0-1 背包(每个只能用一次)内层逆序。 · 「以 i 结尾」型(LIS、最大子数组积):dp[i] 只表示「必须选 i」的最优, 答案要全局取 max —— 这类最容易只返回 dp[n-1] 而写错。
16

多维动态规划

2D DP

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

【什么时候开二维数组】 · 网格型:位置由 (i,j) 决定 -> dp[i][j](Q62/Q64/Q79 计数版)。 · 双串型:状态是「A 的前 i 个 vs B 的前 j 个」-> dp[i][j](LCS、编辑距离、 Q10 正则匹配、Q97 交错字符串)。这类题的通用写法就是三格转移: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) · 区间型:状态是「子串 s[i..j]」-> dp[i][j],枚举区间长度 + 断点 k (Q5 回文判定、Q131/Q132 分割、Q312 戳气球)。遍历顺序必须 保证 dp[i+1][...] 先算:常见是 i 从大到小、j 从小到大,或按长度枚举。 【降维规则】当 dp[i][j] 只依赖第 i-1 行时,可以压成一行; 但如果同时还依赖「本行的 dp[i][j-1]」,压一维时要小心更新顺序 (从左往右扫正好利用了新值;需要 dp[i-1][j-1] 时要额外存一个变量)。
17

技巧

Techs

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

【五个必背技巧】 1. 位运算异或:a^a=0、a^0=a、满足交换律结合律 -> 「只出现一次」类题目的标准解(Q136);推广到「出现 3 次」见 Q137, 用「统计每一位上 1 的个数 mod 3」或两个掩码状态机。 2. 摩尔投票(Boyer-Moore):维护 candidate + count,相同 +1、不同 -1、归零换人。 原理:把「一对不同的元素」互相抵消,出现 > n/2 的元素一定有剩。 注意:它只保证「如果存在多数元素,则一定是这个 candidate」; 题目没保证存在时,必须再扫一遍验证(Q169 不需要,Q229 的 1/3 版本要)。 3. 荷兰国旗三向切分:p0 / i / p2 三个指针把数组切成 <1 / ==1 / >1 三段(即 0 | 1 | 2),一趟排完。 这就是快速排序的三路划分,也是「Dutch national flag problem」。 4. 下一个排列(Q31):从右往左找第一个下降位 -> 与右边「刚好比它大」的数交换 -> 反转后缀。C++ 有 std::next_permutation,但必须会手写(Q556/Q670 同款)。 5. 值域下标当链表用(Q287/Q41/Q442/Q645):数组元素落在 [1,n] 时, nums[i] 天然构成 i -> nums[i] 的函数图,重复元素 => 图上一定有环 => 用 Floyd 龟兔赛跑找环入口。另一路是「把 nums[x] 对应位置取负」当 visited。 两者都是 O(1) 额外空间,且都要求数组可(临时)修改或至少能构造慢指针。

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