如果你正在准备技术面试应该对 LeetCode Top 100 这个清单不陌生。我从头到尾刷过两遍最大的感受是Top 100 的前 40 题基本就决定了你面试的“下限”。尤其是第 21-40 题这组恰好把栈、链表、二分、回溯、线性动态规划这些最高频的考点浓缩在了一起几乎每一道都能在真实面试中找到变体。这篇文章不打算罗列题号让读者自行消化而是把这 20 道题打散重组按“思路内核”重新归堆。你先搞清楚每类题到底在考什么再去看题解、写代码、复盘效率会高很多。如果你正在刷 LeetCode 热门 100 题这一组刷透之后再去碰 Hot 100 里后面的题目会顺不少。文章里会给出每类题型的核心原理、关键代码片段以及我实际刷题踩过的坑方便你直接参考。1. 第21-40题到底长什么样——先看清这20题的分布1.1 这20题的主题地图我不太建议完全按照题单顺序从头刷到尾因为编号顺序打乱了题目难度和类型的节奏。我自己梳理了一份“第21-40题”的版本把常见的 20 道高频题归成了六组。主题分组典型题目核心考察点栈与连续匹配有效的括号、最长有效括号栈的进出时机、索引记录链表重排合并两个有序链表、合并K个升序链表、两两交换链表节点、K个一组翻转链表指针操作、递归拆分、虚拟头节点二分边界搜索旋转排序数组、在排序数组中查找元素的第一个和最后一个位置有序区间的判断、边界收敛回溯搜索括号生成、组合总和、全排列选择-递归-撤销、剪枝动态规划与贪心最大子数组和、跳跃游戏、不同路径状态定义、局部最优到全局最优区间与矩阵合并区间、旋转图像排序后合并、坐标变换这个分组不是随意的。你会发现有效的括号和最长有效括号之间只差了一层“连续区间”的思维K个一组翻转链表就是“反转链表”的升级版搜索旋转排序数组和普通二分查找之间的差异仅仅是多了一个“哪半段有序”的判断。面试官想要考察的其实就是这些底层能力的迁移。1.2 面试官为什么偏爱这一组题原因很简单这 20 道题最适合在 45 分钟以内的面试中考察候选人的算法基本功。它们不像博弈类或后缀数组那种难题需要知识储备几乎不依赖刁钻的数据结构但又能把边界处理、时间复杂度分析、代码简洁度全部暴露出来。比如“有效的括号”看起来很简单但很多候选人会在“是否需要用栈存索引”上犯迷糊。如果是“有效的括号”只需要存字符到了“最长有效括号”就必须保存左括号的下标因为你要计算连续有效长度。同一个场景难度可以立刻翻倍。面试官非常喜欢这种“从基础题到变式题”的追问节奏所以这一组题值得你花时间把每个小题都吃透。另外这组题里有很多“模板型题目”。回溯的“路径-选择-撤销”模板、链表的“虚拟头节点”模板、二分的“区间收缩”模板几乎可以套用到后面更多题目。先把模板刻进肌肉记忆后面刷 Hot 100 会越刷越快。2. 核心题型逐个拆——栈、链表、二分到底在考什么2.1 栈类从“匹配”到“连续区间”先聊聊栈。有效的括号这道题几乎是所有面试准备者的第一道栈题。我见过很多人的第一反应是用计数器遇到左括号加一遇到右括号减一最后判断是不是零。这个思路在处理只有一种括号时是成立的但一旦出现三种括号同时存在计数器就完全失效因为(]这样的组合也会被误判为合法。正确的做法是遍历字符串遇到左括号就入栈遇到右括号时弹出栈顶看能不能匹配。不能匹配或者栈已经空了就直接返回 False。这里有一个容易忽略的点遍历结束后栈必须为空否则说明存在没有配对完的左括号。真正的难点在于“最长有效括号”。这道题可以说是第 21-40 题里栈类题型的天花板。核心技巧是用栈保存左括号的下标而不是左括号本身同时在栈底预置一个 -1 作为“最后一个未匹配位置”的哨兵。def longestValidParentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans为什么栈底要放 -1因为当栈里只剩下这个哨兵时说明前一段有效匹配已经结束可以用当前右括号的下标作为新的哨兵。这就像在一段连续的空地上划线每次出现无法匹配的右括号就重新画一条分界线有效长度就是两条分界线之间的距离。顺着这个思路你还可以继续挑战基本计算器类的题目因为它们同样依赖栈来维护运算优先级。2.2 链表类别只会反转关键是“接回去”链表题的核心不是“会遍历”而是“操作之后还能接回去”。我刷下来发现第 21-40 题里的链表题可以分成三个层次。第一层是“合并两个有序链表”。这道题的答案非常模式化用一个虚拟头节点 dummy 指向结果链表的尾部两个指针分别遍历两个链表谁小就接谁最后把剩余的链表整体接到尾部。虚拟头节点的作用是省掉对“结果链表是否为空”的特判让代码更统一。第二层是“合并K个升序链表”。最稳妥的思路是优先队列。把每个链表当前的头节点丢进小顶堆每次弹出最小的节点接上它之后再把它的下一个节点放进堆里。这里有个细节我踩过坑Python 的 heapq 在堆元素是元组时如果两个节点的 val 相同它会继续比较第二个元素也就是节点对象但 ListNode 对象不支持“小于”比较程序会直接报错。解决办法是往堆里存(val, index, node)用 index 打破平局。import heapq def mergeKLists(lists): heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy ListNode(0) cur dummy while heap: val, i, node heapq.heappop(heap) cur.next node cur cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next第三层是“K个一组翻转链表”。这道题最容易卡住的地方是“翻转完之后怎么接回去”。我的经验是先数一数剩余节点是否够 k 个不够就直接返回够的话就翻转当前小组然后递归处理下一组并把当前小组的尾节点指向下一组翻转后的头节点。翻转时一定要先用 next 指针保存下一个节点否则一旦修改了当前节点的 next后面节点就找不到了。这也是链表题里最常见的断链原因。2.3 二分在一个“近似有序”的世界里排除另一半二分查找看起来简单真正写对的人其实不多。第 21-40 题里的“搜索旋转排序数组”就是很好的试金石。所谓旋转排序数组就是原本递增的数组在某个点被转动了一次比如[0,1,2,4,5,6,7]变成[4,5,6,7,0,1,2]。它整体不是有序的但你总是可以找到某一边是有序的。每次二分取到中间值 mid 后比较nums[left]和nums[mid]。如果左边这段有序就看 target 是否落在nums[left]到nums[mid]之间如果右边这段有序就看 target 是否落在nums[mid]到nums[right]之间。判断完直接收缩区间。我写的代码如下def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1注意判断左边有序时用的是nums[left] nums[mid]这里等于号不能丢。比如[3, 1]这种只有两个元素的场景left 等于 mid不带上等于号会把左边误判成无序。“在排序数组中查找元素的第一个和最后一个位置”是二分的另一个变体本质是 lower_bound 和 upper_bound。你不需要真的实现两个完全不同的函数核心想法是找左边界时遇到target nums[mid]就收缩右边界找右边界时遇到target nums[mid]就扩大左边界。多想想“等于 target 的元素应该向左还是向右靠近”就不会记混。如果这一组题刷完还有余力我建议顺手做做爱吃香蕉的狒狒这类“二分答案”题目它用的虽然不是标准数组二分但内核完全一致在一个单调区间内逼近最优解。2.4 回溯与动态规划模板之外更重要的是剪枝回溯题在 Hot 100 里占比不低。第 21-40 题里的“全排列”“组合总和”“括号生成”都是同一套模板。回溯的通用框架很固定def dfs(路径, 选择列表): if 满足结束条件: 记录路径 return for 选择 in 选择列表: 做出选择 dfs(路径, 新的选择列表) 撤销选择拿“组合总和”来说题目允许同一个数字无限次重复使用但又要求组合不能重复。很多人会写出很多重复组合原因是他们每一层递归都把候选数组从头开始遍历。解决办法是给递归函数加一个 start 参数表示当前层只从 start 下标开始选择。这样[2, 3]和[3, 2]这种顺序不同的组合就不会同时出现了。def combinationSum(candidates, target): candidates.sort() res [] def dfs(start, path, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: break path.append(candidates[i]) dfs(i, path, remain - candidates[i]) path.pop() dfs(0, [], target) return res排序加break是剪枝的关键因为数组有序之后一旦当前数字已经大于剩余目标后面的数只会更大没必要继续循环。动态规划类的题在面试中同样高频。“最大子数组和”是入门级 DAG 思维题但很多人在处理负数时会出错。核心状态是dp[i]表示以第 i 个元素结尾的最大子数组和。转移只有两种选择要么把当前元素接到前面的子数组后面要么从当前元素重新开始。写成滚动变量就是cur max_sum nums[0] for v in nums[1:]: cur max(v, cur v) max_sum max(max_sum, cur)“跳跃游戏”则更像贪心。你只需要一个变量 far 记录当前能到达的最远下标遍历数组时不断更新 far一旦发现某个下标 i 大于 far说明这里根本到不了直接返回 False。这个题目很多人一上来就想 DP其实贪心思维更直接也更容易讲清楚。3. 实操阶段按这个顺序刷效率高很多3.1 我推荐的分组刷题顺序如果你准备在两周内拿下这 20 题我不建议一天刷 5 道、每道只过一遍题解。更推荐按下面这种方式分四轮第一轮只做“栈 链表”。共 6 道题重点把虚拟头节点、栈存索引、递归返回头的写法练熟。第二轮只做“二分 区间”。共 5 道题重点练二分边界和区间合并排序技巧。第三轮只做“回溯 动态规划 贪心”。共 7 道题重点把模板默写出来。第四轮把 20 道题全部重新写一遍要求每道题 20 分钟内完成。我第一轮刷的时候犯过一个大错误每道题看一遍题解然后照着题解默写一遍写完就觉得自己会了。结果一周后再做“搜索旋转排序数组”还是卡在边界判断上。后来我强制自己先看题解理思路然后把题解关掉凭记忆在白板上独立写。哪怕写不出来也要先写一个暴力版本再对比题解优化。这个过程痛苦但效果立竿见影。3.2 关键题目的可复用代码这里收录几个我认为最值得反复写的代码片段面试前最好能默写出来。第一个是链表常用的“虚拟头节点 尾插法”几乎所有链表拼接题都能用。第二个是“括号生成”的回溯解法它比组合总和更简单但更容易暴露对左右括号数量限制的理解。def generateParenthesis(n): res [] def dfs(left, right, path): if left 0 and right 0: res.append(path) return if left 0: dfs(left - 1, right, path () if right left: dfs(left, right - 1, path )) dfs(n, n, ) return res这里关键的一行是if right left它保证当前路径中右括号数量永远不会超过左括号数量。很多人的版本写的是if right 0这会导致生成)(这种非法括号因为右括号在左括号还没出现时就被放进了路径。第三个推荐默写的是“合并区间”。这道题不涉及复杂算法但非常考代码组织能力。排序后遍历判断当前区间的左端点是否大于合并结果最后一个区间的右端点如果大于就新开区间否则就更新最后一个区间的右端点。它的代码很短却是后面“插入区间”“会议室”等题目的基础。def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return merged3.3 复杂度对照表写代码前先想清楚面试时面试官几乎一定会问“时间复杂度是多少”。我建议你在写题时就把每一道题的复杂度顺手记录在一个地方至少要在脑子里过一遍。下面是我整理的第 21-40 题里高频题目的复杂度一览题目时间复杂度空间复杂度有效的括号O(n)O(n)最长有效括号O(n)O(n)合并两个有序链表O(n m)O(1)合并K个升序链表O(n log k)O(k)K个一组翻转链表O(n)O(1) 或 O(n/k)搜索旋转排序数组O(log n)O(1)在排序数组中查找元素范围O(log n)O(1)组合总和指数级O(n)全排列O(n * n!)O(n)最大子数组和O(n)O(1)跳跃游戏O(n)O(1)合并区间O(n log n)O(log n)特别注意K个一组翻转链表如果使用递归空间复杂度不是 O(1)而是 O(n/k) 的栈空间。面试时面试官可能追问“能不能改成迭代”这时候你需要掌握用迭代 虚拟头节点的做法避免递归版本带来的空间开销。4. 刷题现场最常踩的坑——问题排查实录4.1 链表题断链、丢头、边界不清链表题的报错通常是“运行时错误空指针”。最常见的原因是操作节点时没有先保存next指针。比如两两交换链表中的节点很多新手会写出first.next second.next然后打算second.next first但这时候second.next已经被改过了链表就断了。正确顺序是先把next存下来再把second接到first之前。我刷这些题的时候习惯用画图辅助把每个步骤用箭头画出来画对了再写代码能省下一大堆试错时间。另一个易错点是“K个一组翻转链表”里翻转完当前小组后新的头尾节点很容易搞混。我自己的技巧是用pre表示上一个小组翻转后的尾节点cur表示当前小组第一个节点。翻转 k 个节点后cur变成当前小组的尾节点pre.next指向新头然后更新pre cur。这个指针流转过程画一遍比看十遍题解都管用。4.2 二分题死循环和区间开闭二分题最经典的报错就是提交后超时原因是 while 条件写错导致死循环。我的经验是统一使用while left right每次更新时用left mid 1或right mid - 1这样区间长度一定会减少不会出现left right时的死循环。千万不要写成left mid或right mid除非你知道自己在做什么边界题。“搜索旋转排序数组”还有一个隐蔽的坑判断左边是否有序时必须用nums[left] nums[mid]。但如果你只在nums[left] nums[mid]时判断左边有序那么在数组只有两个元素时比如[3, 1]left 和 mid 相同nums[left] nums[mid]此时会被误判为右边有序从而错误地收缩区间。这个等号问题在面试现场很容易漏掉。还有一个小技巧排查二分错误时不要只盯逻辑可以打印每一次 mid、left、right 的值。我实际操作中发现很多问题不是“有没有 sorted”的问题而是“你访问的区间是否仍然有效”。比如 left 更新超过 right 后循环退出但代码里可能还会访问 nums[mid]这就是越界。写上if 0 mid len(nums)作为防御性检查可以帮助快速定位。4.3 回溯题重复组合是怎么产生的回溯题里最常见的错误是输出结果重复。比如“组合总和”不排序直接递归会导致[2, 3, 2]和[2, 2, 3]同时出现在结果里。解决办法就是给递归增加 start 参数保证每次选择只从当前下标或之后进行。另一个容易忽略的问题是结果去重。很多人会在最后用set去重但回溯题的正确做法是在生成过程中就剪枝。用集合去重不仅浪费时间还会让面试官觉得你没有理解回溯的本质。我在刷全排列时遇到类似问题全排列要求所有顺序都算不同组合所以不需要 start 参数而是要用used数组记录哪些元素已经用过。两种场景要分清。4.4 动态规划与贪心状态定义错了一切白搭动态规划题写不出来十有八九是状态定义没想清楚。拿“最大子数组和”来说如果你把 dp[i] 定义为“前 i 个元素的最大子数组和”那转移非常难写因为你无法判断这个最大子数组是否包含第 i 个元素。但如果定义为“以第 i 个元素结尾的最大子数组和”转移就非常简单了。这也是我反复提醒自己的状态定义一定要保证“无后效性”也就是说当前决策只依赖前一个状态不依赖更早状态的选择。贪心题相对容易出错的点是贪心策略不正确。以“跳跃游戏”为例有段时间我总想从后往前推从倒数第二个位置开始看能否跳到末尾不行就继续往前看。这个思路虽然也能解但实现起来更绕。后来改用维护最远可达距离的办法反而清晰了。所以如果你发现自己的贪心策略越写越复杂大概率是没找到更直接的那个“贪心指标”。5. 我刷完这一组后的个人体会第 21-40 题这一组表面上看是 20 道题实际上浓缩了 4 类核心能力栈的“状态记忆”、链表的“指针操作”、二分的“区间收缩”、回溯和 DP 的“状态转移”。我在实际刷题中体会到刷这一组题最有效的方式不是按照编号顺序刷而是按类型突破。每类题集中刷 3 到 5 道反复比较它们的异同比每天刷一道不同主题的题更能形成“题感”。如果你现在正卡在某道题上比如最长有效括号或者 K 个一组翻转链表我的建议是先别硬啃换一道同主题的基础题写一遍比如先写有效的括号再回来写最长有效括号先写反转链表再回来写 K 个一组翻转链表。很多时候你觉得自己不会只是因为你对底层的那个小模板还不够熟悉。最后分享一个小技巧这 20 道题里相当一部分题解都有“官方标准写法”和“个人顺手写法”。我建议你以官方题解为准但如果某种写法你反复写错不要硬憋换一种能讲清楚逻辑的写法只要能保证正确性和复杂度面试官不会因为你没按标准模板写而扣分。最重要的是代码写完一定要在草稿纸上跑一遍例子这比任何背诵都管用。
LeetCode Hot 100第21-40题精讲：栈、链表、二分、回溯与DP一次吃透
如果你正在准备技术面试应该对 LeetCode Top 100 这个清单不陌生。我从头到尾刷过两遍最大的感受是Top 100 的前 40 题基本就决定了你面试的“下限”。尤其是第 21-40 题这组恰好把栈、链表、二分、回溯、线性动态规划这些最高频的考点浓缩在了一起几乎每一道都能在真实面试中找到变体。这篇文章不打算罗列题号让读者自行消化而是把这 20 道题打散重组按“思路内核”重新归堆。你先搞清楚每类题到底在考什么再去看题解、写代码、复盘效率会高很多。如果你正在刷 LeetCode 热门 100 题这一组刷透之后再去碰 Hot 100 里后面的题目会顺不少。文章里会给出每类题型的核心原理、关键代码片段以及我实际刷题踩过的坑方便你直接参考。1. 第21-40题到底长什么样——先看清这20题的分布1.1 这20题的主题地图我不太建议完全按照题单顺序从头刷到尾因为编号顺序打乱了题目难度和类型的节奏。我自己梳理了一份“第21-40题”的版本把常见的 20 道高频题归成了六组。主题分组典型题目核心考察点栈与连续匹配有效的括号、最长有效括号栈的进出时机、索引记录链表重排合并两个有序链表、合并K个升序链表、两两交换链表节点、K个一组翻转链表指针操作、递归拆分、虚拟头节点二分边界搜索旋转排序数组、在排序数组中查找元素的第一个和最后一个位置有序区间的判断、边界收敛回溯搜索括号生成、组合总和、全排列选择-递归-撤销、剪枝动态规划与贪心最大子数组和、跳跃游戏、不同路径状态定义、局部最优到全局最优区间与矩阵合并区间、旋转图像排序后合并、坐标变换这个分组不是随意的。你会发现有效的括号和最长有效括号之间只差了一层“连续区间”的思维K个一组翻转链表就是“反转链表”的升级版搜索旋转排序数组和普通二分查找之间的差异仅仅是多了一个“哪半段有序”的判断。面试官想要考察的其实就是这些底层能力的迁移。1.2 面试官为什么偏爱这一组题原因很简单这 20 道题最适合在 45 分钟以内的面试中考察候选人的算法基本功。它们不像博弈类或后缀数组那种难题需要知识储备几乎不依赖刁钻的数据结构但又能把边界处理、时间复杂度分析、代码简洁度全部暴露出来。比如“有效的括号”看起来很简单但很多候选人会在“是否需要用栈存索引”上犯迷糊。如果是“有效的括号”只需要存字符到了“最长有效括号”就必须保存左括号的下标因为你要计算连续有效长度。同一个场景难度可以立刻翻倍。面试官非常喜欢这种“从基础题到变式题”的追问节奏所以这一组题值得你花时间把每个小题都吃透。另外这组题里有很多“模板型题目”。回溯的“路径-选择-撤销”模板、链表的“虚拟头节点”模板、二分的“区间收缩”模板几乎可以套用到后面更多题目。先把模板刻进肌肉记忆后面刷 Hot 100 会越刷越快。2. 核心题型逐个拆——栈、链表、二分到底在考什么2.1 栈类从“匹配”到“连续区间”先聊聊栈。有效的括号这道题几乎是所有面试准备者的第一道栈题。我见过很多人的第一反应是用计数器遇到左括号加一遇到右括号减一最后判断是不是零。这个思路在处理只有一种括号时是成立的但一旦出现三种括号同时存在计数器就完全失效因为(]这样的组合也会被误判为合法。正确的做法是遍历字符串遇到左括号就入栈遇到右括号时弹出栈顶看能不能匹配。不能匹配或者栈已经空了就直接返回 False。这里有一个容易忽略的点遍历结束后栈必须为空否则说明存在没有配对完的左括号。真正的难点在于“最长有效括号”。这道题可以说是第 21-40 题里栈类题型的天花板。核心技巧是用栈保存左括号的下标而不是左括号本身同时在栈底预置一个 -1 作为“最后一个未匹配位置”的哨兵。def longestValidParentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans为什么栈底要放 -1因为当栈里只剩下这个哨兵时说明前一段有效匹配已经结束可以用当前右括号的下标作为新的哨兵。这就像在一段连续的空地上划线每次出现无法匹配的右括号就重新画一条分界线有效长度就是两条分界线之间的距离。顺着这个思路你还可以继续挑战基本计算器类的题目因为它们同样依赖栈来维护运算优先级。2.2 链表类别只会反转关键是“接回去”链表题的核心不是“会遍历”而是“操作之后还能接回去”。我刷下来发现第 21-40 题里的链表题可以分成三个层次。第一层是“合并两个有序链表”。这道题的答案非常模式化用一个虚拟头节点 dummy 指向结果链表的尾部两个指针分别遍历两个链表谁小就接谁最后把剩余的链表整体接到尾部。虚拟头节点的作用是省掉对“结果链表是否为空”的特判让代码更统一。第二层是“合并K个升序链表”。最稳妥的思路是优先队列。把每个链表当前的头节点丢进小顶堆每次弹出最小的节点接上它之后再把它的下一个节点放进堆里。这里有个细节我踩过坑Python 的 heapq 在堆元素是元组时如果两个节点的 val 相同它会继续比较第二个元素也就是节点对象但 ListNode 对象不支持“小于”比较程序会直接报错。解决办法是往堆里存(val, index, node)用 index 打破平局。import heapq def mergeKLists(lists): heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy ListNode(0) cur dummy while heap: val, i, node heapq.heappop(heap) cur.next node cur cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next第三层是“K个一组翻转链表”。这道题最容易卡住的地方是“翻转完之后怎么接回去”。我的经验是先数一数剩余节点是否够 k 个不够就直接返回够的话就翻转当前小组然后递归处理下一组并把当前小组的尾节点指向下一组翻转后的头节点。翻转时一定要先用 next 指针保存下一个节点否则一旦修改了当前节点的 next后面节点就找不到了。这也是链表题里最常见的断链原因。2.3 二分在一个“近似有序”的世界里排除另一半二分查找看起来简单真正写对的人其实不多。第 21-40 题里的“搜索旋转排序数组”就是很好的试金石。所谓旋转排序数组就是原本递增的数组在某个点被转动了一次比如[0,1,2,4,5,6,7]变成[4,5,6,7,0,1,2]。它整体不是有序的但你总是可以找到某一边是有序的。每次二分取到中间值 mid 后比较nums[left]和nums[mid]。如果左边这段有序就看 target 是否落在nums[left]到nums[mid]之间如果右边这段有序就看 target 是否落在nums[mid]到nums[right]之间。判断完直接收缩区间。我写的代码如下def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1注意判断左边有序时用的是nums[left] nums[mid]这里等于号不能丢。比如[3, 1]这种只有两个元素的场景left 等于 mid不带上等于号会把左边误判成无序。“在排序数组中查找元素的第一个和最后一个位置”是二分的另一个变体本质是 lower_bound 和 upper_bound。你不需要真的实现两个完全不同的函数核心想法是找左边界时遇到target nums[mid]就收缩右边界找右边界时遇到target nums[mid]就扩大左边界。多想想“等于 target 的元素应该向左还是向右靠近”就不会记混。如果这一组题刷完还有余力我建议顺手做做爱吃香蕉的狒狒这类“二分答案”题目它用的虽然不是标准数组二分但内核完全一致在一个单调区间内逼近最优解。2.4 回溯与动态规划模板之外更重要的是剪枝回溯题在 Hot 100 里占比不低。第 21-40 题里的“全排列”“组合总和”“括号生成”都是同一套模板。回溯的通用框架很固定def dfs(路径, 选择列表): if 满足结束条件: 记录路径 return for 选择 in 选择列表: 做出选择 dfs(路径, 新的选择列表) 撤销选择拿“组合总和”来说题目允许同一个数字无限次重复使用但又要求组合不能重复。很多人会写出很多重复组合原因是他们每一层递归都把候选数组从头开始遍历。解决办法是给递归函数加一个 start 参数表示当前层只从 start 下标开始选择。这样[2, 3]和[3, 2]这种顺序不同的组合就不会同时出现了。def combinationSum(candidates, target): candidates.sort() res [] def dfs(start, path, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: break path.append(candidates[i]) dfs(i, path, remain - candidates[i]) path.pop() dfs(0, [], target) return res排序加break是剪枝的关键因为数组有序之后一旦当前数字已经大于剩余目标后面的数只会更大没必要继续循环。动态规划类的题在面试中同样高频。“最大子数组和”是入门级 DAG 思维题但很多人在处理负数时会出错。核心状态是dp[i]表示以第 i 个元素结尾的最大子数组和。转移只有两种选择要么把当前元素接到前面的子数组后面要么从当前元素重新开始。写成滚动变量就是cur max_sum nums[0] for v in nums[1:]: cur max(v, cur v) max_sum max(max_sum, cur)“跳跃游戏”则更像贪心。你只需要一个变量 far 记录当前能到达的最远下标遍历数组时不断更新 far一旦发现某个下标 i 大于 far说明这里根本到不了直接返回 False。这个题目很多人一上来就想 DP其实贪心思维更直接也更容易讲清楚。3. 实操阶段按这个顺序刷效率高很多3.1 我推荐的分组刷题顺序如果你准备在两周内拿下这 20 题我不建议一天刷 5 道、每道只过一遍题解。更推荐按下面这种方式分四轮第一轮只做“栈 链表”。共 6 道题重点把虚拟头节点、栈存索引、递归返回头的写法练熟。第二轮只做“二分 区间”。共 5 道题重点练二分边界和区间合并排序技巧。第三轮只做“回溯 动态规划 贪心”。共 7 道题重点把模板默写出来。第四轮把 20 道题全部重新写一遍要求每道题 20 分钟内完成。我第一轮刷的时候犯过一个大错误每道题看一遍题解然后照着题解默写一遍写完就觉得自己会了。结果一周后再做“搜索旋转排序数组”还是卡在边界判断上。后来我强制自己先看题解理思路然后把题解关掉凭记忆在白板上独立写。哪怕写不出来也要先写一个暴力版本再对比题解优化。这个过程痛苦但效果立竿见影。3.2 关键题目的可复用代码这里收录几个我认为最值得反复写的代码片段面试前最好能默写出来。第一个是链表常用的“虚拟头节点 尾插法”几乎所有链表拼接题都能用。第二个是“括号生成”的回溯解法它比组合总和更简单但更容易暴露对左右括号数量限制的理解。def generateParenthesis(n): res [] def dfs(left, right, path): if left 0 and right 0: res.append(path) return if left 0: dfs(left - 1, right, path () if right left: dfs(left, right - 1, path )) dfs(n, n, ) return res这里关键的一行是if right left它保证当前路径中右括号数量永远不会超过左括号数量。很多人的版本写的是if right 0这会导致生成)(这种非法括号因为右括号在左括号还没出现时就被放进了路径。第三个推荐默写的是“合并区间”。这道题不涉及复杂算法但非常考代码组织能力。排序后遍历判断当前区间的左端点是否大于合并结果最后一个区间的右端点如果大于就新开区间否则就更新最后一个区间的右端点。它的代码很短却是后面“插入区间”“会议室”等题目的基础。def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return merged3.3 复杂度对照表写代码前先想清楚面试时面试官几乎一定会问“时间复杂度是多少”。我建议你在写题时就把每一道题的复杂度顺手记录在一个地方至少要在脑子里过一遍。下面是我整理的第 21-40 题里高频题目的复杂度一览题目时间复杂度空间复杂度有效的括号O(n)O(n)最长有效括号O(n)O(n)合并两个有序链表O(n m)O(1)合并K个升序链表O(n log k)O(k)K个一组翻转链表O(n)O(1) 或 O(n/k)搜索旋转排序数组O(log n)O(1)在排序数组中查找元素范围O(log n)O(1)组合总和指数级O(n)全排列O(n * n!)O(n)最大子数组和O(n)O(1)跳跃游戏O(n)O(1)合并区间O(n log n)O(log n)特别注意K个一组翻转链表如果使用递归空间复杂度不是 O(1)而是 O(n/k) 的栈空间。面试时面试官可能追问“能不能改成迭代”这时候你需要掌握用迭代 虚拟头节点的做法避免递归版本带来的空间开销。4. 刷题现场最常踩的坑——问题排查实录4.1 链表题断链、丢头、边界不清链表题的报错通常是“运行时错误空指针”。最常见的原因是操作节点时没有先保存next指针。比如两两交换链表中的节点很多新手会写出first.next second.next然后打算second.next first但这时候second.next已经被改过了链表就断了。正确顺序是先把next存下来再把second接到first之前。我刷这些题的时候习惯用画图辅助把每个步骤用箭头画出来画对了再写代码能省下一大堆试错时间。另一个易错点是“K个一组翻转链表”里翻转完当前小组后新的头尾节点很容易搞混。我自己的技巧是用pre表示上一个小组翻转后的尾节点cur表示当前小组第一个节点。翻转 k 个节点后cur变成当前小组的尾节点pre.next指向新头然后更新pre cur。这个指针流转过程画一遍比看十遍题解都管用。4.2 二分题死循环和区间开闭二分题最经典的报错就是提交后超时原因是 while 条件写错导致死循环。我的经验是统一使用while left right每次更新时用left mid 1或right mid - 1这样区间长度一定会减少不会出现left right时的死循环。千万不要写成left mid或right mid除非你知道自己在做什么边界题。“搜索旋转排序数组”还有一个隐蔽的坑判断左边是否有序时必须用nums[left] nums[mid]。但如果你只在nums[left] nums[mid]时判断左边有序那么在数组只有两个元素时比如[3, 1]left 和 mid 相同nums[left] nums[mid]此时会被误判为右边有序从而错误地收缩区间。这个等号问题在面试现场很容易漏掉。还有一个小技巧排查二分错误时不要只盯逻辑可以打印每一次 mid、left、right 的值。我实际操作中发现很多问题不是“有没有 sorted”的问题而是“你访问的区间是否仍然有效”。比如 left 更新超过 right 后循环退出但代码里可能还会访问 nums[mid]这就是越界。写上if 0 mid len(nums)作为防御性检查可以帮助快速定位。4.3 回溯题重复组合是怎么产生的回溯题里最常见的错误是输出结果重复。比如“组合总和”不排序直接递归会导致[2, 3, 2]和[2, 2, 3]同时出现在结果里。解决办法就是给递归增加 start 参数保证每次选择只从当前下标或之后进行。另一个容易忽略的问题是结果去重。很多人会在最后用set去重但回溯题的正确做法是在生成过程中就剪枝。用集合去重不仅浪费时间还会让面试官觉得你没有理解回溯的本质。我在刷全排列时遇到类似问题全排列要求所有顺序都算不同组合所以不需要 start 参数而是要用used数组记录哪些元素已经用过。两种场景要分清。4.4 动态规划与贪心状态定义错了一切白搭动态规划题写不出来十有八九是状态定义没想清楚。拿“最大子数组和”来说如果你把 dp[i] 定义为“前 i 个元素的最大子数组和”那转移非常难写因为你无法判断这个最大子数组是否包含第 i 个元素。但如果定义为“以第 i 个元素结尾的最大子数组和”转移就非常简单了。这也是我反复提醒自己的状态定义一定要保证“无后效性”也就是说当前决策只依赖前一个状态不依赖更早状态的选择。贪心题相对容易出错的点是贪心策略不正确。以“跳跃游戏”为例有段时间我总想从后往前推从倒数第二个位置开始看能否跳到末尾不行就继续往前看。这个思路虽然也能解但实现起来更绕。后来改用维护最远可达距离的办法反而清晰了。所以如果你发现自己的贪心策略越写越复杂大概率是没找到更直接的那个“贪心指标”。5. 我刷完这一组后的个人体会第 21-40 题这一组表面上看是 20 道题实际上浓缩了 4 类核心能力栈的“状态记忆”、链表的“指针操作”、二分的“区间收缩”、回溯和 DP 的“状态转移”。我在实际刷题中体会到刷这一组题最有效的方式不是按照编号顺序刷而是按类型突破。每类题集中刷 3 到 5 道反复比较它们的异同比每天刷一道不同主题的题更能形成“题感”。如果你现在正卡在某道题上比如最长有效括号或者 K 个一组翻转链表我的建议是先别硬啃换一道同主题的基础题写一遍比如先写有效的括号再回来写最长有效括号先写反转链表再回来写 K 个一组翻转链表。很多时候你觉得自己不会只是因为你对底层的那个小模板还不够熟悉。最后分享一个小技巧这 20 道题里相当一部分题解都有“官方标准写法”和“个人顺手写法”。我建议你以官方题解为准但如果某种写法你反复写错不要硬憋换一种能讲清楚逻辑的写法只要能保证正确性和复杂度面试官不会因为你没按标准模板写而扣分。最重要的是代码写完一定要在草稿纸上跑一遍例子这比任何背诵都管用。
