LeetCode Hot 100 刷到第55~61题这一段恰好是七道风格完全不同的题区间合并、跳跃游戏、螺旋矩阵、旋转链表、字符串处理、排列序列全凑在一起了。这个位置很有意思不像前半段那样大量堆叠同类型题目而是每道题背后都是一种独立的解题范式。如果你正在按 Hot 100 题单稳步推进这七题是一个非常不错的换挡区间既能巩固前面的排序、双指针、动态规划基础又能提前接触数学模拟和链表操作的套路。我刷这一段的时候有一个明显感受这几道题单独拎出任何一道都不算难难度评级基本都在中等偏下但把它们放在一起很容易暴露同一个问题——边界条件处理粗心。合并区间漏了 max、插入区间忘了收尾、旋转链表 k 没取模、螺旋矩阵奇数中心多填一次。这些错误不涉及算法思想纯粹是代码细节但恰恰是面试中挂人的重灾区。这篇文章就把七道题整体过一遍重点放在最容易写错的地方和我实测下来最稳的写法上适合正在刷题、准备二刷、或者面试前快速热身的读者。1. 区间类双题合并区间与插入区间的快速打法1.1 合并区间排序之后只扫一遍题目会给一个二维数组 intervals每个元素是一个 [start, end] 的区间让你把所有重叠区间合并最后返回合并后的不重叠区间列表。这是面试高频题也是几乎所有区间类问题的起点。核心思路很简单先把所有区间按左端点从小到大排序排序之后能合并的区间一定是连续的一段。为什么因为只要左端点有序从左往右扫的时候当前区间 [l, r] 如果和上一个合并后的区间重叠那它一定紧挨着上一个区间不可能隔着别的区间。这是区间类问题最常用的一条定理——所有需要判断重叠/覆盖的题只要区间是无序的第一反应永远是先 sort。然后合并的逻辑就是维护一个当前结果列表 res。先把第一个区间放进去然后从第二个区间开始遍历。如果当前区间的左端点 l res[-1][1]说明有重叠这时候把 res[-1][1] 更新成它和当前右端点 r 的较大值否则当前区间整体在 res[-1] 的右边直接加入 res。代码贴一下def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [intervals[0][:]] for l, r in intervals[1:]: if l res[-1][1]: res[-1][1] max(res[-1][1], r) else: res.append([l, r]) return res我在第一次写这道题的时候犯过一个典型错误更新区间时写成res[-1][1] r而不是取 max。当时想的是既然重叠了新区间的右端点肯定更大但忽略了 [1, 10] 合并 [2, 3] 这种情况——被合并的区间完全被包在旧区间里面直接覆盖会丢数据。这个细节面试官特别爱挖建议有条件的话把 max 这一步用注释标出来。复杂度和边界条件也要聊两句。排序 O(n log n)一次扫描 O(n)总体 O(n log n)。空间上如果不考虑排序占用的额外栈空间就是 O(n)。这题没什么优化空间唯一要小心的是输入的 intervals 可能为空所以我在开头加了空值判断。题目里还有一个隐藏考点是原地修改还是新建数组我习惯新建 res这样逻辑更清晰代码审阅也更友好。1.2 插入区间三阶段遍历别漏了最后一段插入区间是合并区间的直接变体。这次题目给你一个已经按左端点排好序、且自身没有重叠的区间列表再给你一个新区间 newInterval让你插进去并合并返回结果。因为有原区间有序且无重叠这个前提这题甚至不用排序一次线性扫描就够了。我习惯把遍历分成三个阶段来写第一阶段当前区间完全在 newInterval 的左边。判断条件是 intervals[i][1] newInterval[0]此时没有交集直接把当前区间放入答案指针继续往后。第二阶段当前区间和 newInterval 有重叠。条件是 intervals[i][0] newInterval[1]此时把 newInterval 和当前区间合并具体做法就是左端点取 min右端点取 max指针继续往后。第三阶段当前区间完全在 newInterval 的右边。判断条件是 intervals[i][0] newInterval[1]此时 newInterval 已经不可能再跟后面的区间重叠了先把它加入答案然后把剩余所有区间原样加入答案直接 break。代码我一般这么写def insert(intervals, newInterval): res [] i, n 0, len(intervals) while i n and intervals[i][1] newInterval[0]: res.append(intervals[i]) i 1 while i n and intervals[i][0] newInterval[1]: newInterval[0] min(newInterval[0], intervals[i][0]) newInterval[1] max(newInterval[1], intervals[i][1]) i 1 res.append(newInterval) while i n: res.append(intervals[i]) i 1 return res这个写法最容易被漏的部分在第一个 while 结束后、第二个 while 开始前。如果你的代码里不是直接修改 newInterval而是单独用一个 cur 变量记录合并结果那遍历完之后一定别忘了把 cur 追加进 res。我见过不少同学在第二个 while 里直接修改了 newInterval但最后忘了 append导致结果差一个区间。还有一个让人容易绕晕的地方第二个 while 的判断条件是intervals[i][0] newInterval[1]不是。为什么是 ≤因为两个区间只要左端点小于等于右端点中间就算有贴边比如 [1,2] 和 [3,4] 加上新区间 [2,3]2 和 3 是重合的必须合并成一个区间 [1,4]。这种贴边边界面试里经常设陷阱。这题的时间复杂度是 O(n)因为只需要一次完整遍历空间 O(n)。合并区间和插入区间这两道题建议放在一起刷。合并区间练的是排序扫描这套模板插入区间练的是有序条件下的三段式合并两道题吃透之后后面遇到会议室 II、无重叠区间这类变体都会轻松很多。我在实际刷题中感受到区间类题目最核心的心态是不要慌先想清楚状态怎么划分。插入区间只要划分出左边、重叠、右边三个状态代码自然就出来了。2. 跳跃游戏从 DP 到贪心的进阶之路2.1 先把 DP 写出来感受复杂度跳跃游戏是 Hot 100 里非常有代表性的一道题。题目给你一个非负整数数组 nums你从下标 0 出发每个位置上的值表示你从这儿最多能往后跳多远问你能不能到达最后一个下标。注意你可能不直接跳到最后一个位置只要最终能踩到最后一个下标就算成功。我最初拿到这道题直觉是用动态规划。定义 dp[i] 表示从起点能否到达 i初始化 dp[0] True。然后从前往后遍历只要当前位置 dp[i] 是可达的就把 i 后面 nums[i] 范围内的所有位置都标记为可达。代码如下def canJump_dp(nums): n len(nums) dp [False] * n dp[0] True for i in range(n): if not dp[i]: continue for j in range(i 1, min(n - 1, i nums[i]) 1): dp[j] True if dp[n - 1]: return True return dp[n - 1]这个解法很容易理解但有个明显的性能问题最坏情况下如果数组里全是很大的数每个位置都要往外扩展一大段距离会出现大量重复标记。比如 nums [5,5,5,...]i0 时把 1 到 5 都标了i1 时又把 2 到 6 标了一遍重复计算毫无意义。最坏复杂度能到 O(n²)虽然数据量不大也能过但面试官一定会追问能不能更好。这里我提一个直觉动态规划很多时候是反着推或者枚举状态但跳跃游戏的状态转移其实非常像扩散。如果你把 dp 数组想象成一排开关每次在某位置按下开关能点亮后面一串灯这种层层点亮的方式显然有大量冗余。实际上一个位置一旦被点亮之后就再也不会熄灭所以只需要记录当前最远能点亮的灯的编号不需要记录每个位置到底怎么被点亮的。如果你对 DP 比较敏感可以优化成前缀可达的思路维护一个从起点开始能连续覆盖的范围这种方法其实已经是在往贪心靠了。所以与其在 DP 的优化版本里绕弯不如直接切换到贪心的视角理解这道题这也是 Hot 100 里少数几道DP 能做但贪心更优的题。2.2 换贪心思路问题秒变简单贪心解法只需要维护一个变量 furthest表示从起点出发当前能到达的最远下标。每次遍历位置 i如果 i 已经超过了 furthest说明前面断了直接返回 False否则用 i nums[i] 尝试更新 furthest。def canJump(nums): n len(nums) furthest 0 for i in range(n): if i furthest: return False furthest max(furthest, i nums[i]) if furthest n - 1: return True return True为什么这个贪心是正确的我当时的理解方式是从起点出发能到达的所有位置一定是连续的。你想如果位置 i 可达那么 0 到 i 之间的所有位置必然都可达因为你要想到达 i就必须经过中间的每一个位置。所以只要记录连续可达范围的最右端就能判断全局。这是一种典型的维护可达区间右端的思想跳着扫是不行的必须逐个位置推进。这里有个细节值得注意循环里我用了if furthest n - 1: return True这个提前返回能省不少时间尤其是 n 很大的时候。另外如果 n 1循环第一次就返回 True不需要特殊处理。真正容易写错的地方反而是循环中忘了判断i furthest这样如果中间出现断档furthest 没更新但循环还在继续最后误判成可达。我在刷题时见过好几个版本都栽在这个坑上。复杂度上贪心是 O(n) 时间、O(1) 空间这是最优解。之后刷跳跃游戏 II求最少跳跃次数时你会发现核心也是维护最远覆盖距离只是多记录一个跳跃次数和当前可达边界本质上是一套思路。用生活化的话说这就像你徒步穿越一条路线只要记录到现在为止脚能踩到的最远点一旦某个点根本踩不到就说明路线断了。把这个思维模型记住贪心类题目会顺手很多。我在二刷这道题时还故意把 DP 版本和贪心版本放在一起跑了几组数据对比虽然 n 小的时候看不出差距但 n 到 10 万时差别非常明显这种体感会帮你在面试时更坚定地选择最优解。3. 矩阵与链表螺旋矩阵 II 和旋转链表的边界艺术3.1 螺旋矩阵 II四边收缩法螺旋矩阵系列有两道经典题一道是螺旋矩阵 I按顺时针遍历矩阵一道是螺旋矩阵 II按顺时针把 1 到 n² 填进 n x n 矩阵。Hot 100 里的 NO.59 是后一道本质上是一个模拟题。既然是模拟最怕的就是边界条件写成一团乱麻所以一定要选一个清晰的控制结构。模拟的写法有很多种我比较推荐四边收缩法。维护 top、bottom、left、right 四个边界变量每次先从左到右填上边填完 top 加 1再从上到下填右边填完 right 减 1然后从右到左填下边填完 bottom 减 1最后从下到上填左边填完 left 加 1。如此循环直到所有位置被填满。def generateMatrix(n): matrix [[0] * n for _ in range(n)] top, bottom, left, right 0, n - 1, 0, n - 1 num 1 while top bottom and left right: for j in range(left, right 1): matrix[top][j] num num 1 top 1 for i in range(top, bottom 1): matrix[i][right] num num 1 right - 1 if top bottom: for j in range(right, left - 1, -1): matrix[bottom][j] num num 1 bottom - 1 if left right: for i in range(bottom, top - 1, -1): matrix[i][left] num num 1 left 1 return matrix我没少在这个代码上翻车主要原因有两点。第一点也是最常见的下边和左边两个方向的遍历必须加 if 判断。如果 n 是奇数比如 n3每轮循环上下左右各填一次最后一轮实际上是中间只剩一个格子这时候如果单独填下边或者左边就会把已经填好的格子覆盖一遍。我最早是用while num n * n来控制循环的结果填到最后总是多填一次后来改成用四个边界的包含关系才彻底搞清楚问题出在哪儿。第二点每次填完一个边就立即更新对应的边界指针。如果你把四个边都填完再统一更新边界第二轮循环就会越界。这个填一步、缩一步的节奏是四边收缩法的灵魂。我还遇到过一种风格是用方向数组 visited 记录的通法相比四边收缩法更通用可以套用到螺旋矩阵 I、螺旋输出链表等场景。我在面试时更偏向四边收缩法因为代码行数少边界逻辑写清楚了几乎不用调试。如果你追求稳可以两个版本在纸上各写一遍体会下差异。这里我想强调一个刷题技巧模拟题的复杂度通常是 O(n²)因为要填充 n² 个格子这个复杂度没法降低所以面试官更看重的是你代码里的边界判断是否完备。写完这种题我习惯自己跑三个用例n1、n2、n3。n1 查单格子n2 查一圈完整旋转n3 查奇数矩阵的中心格子是否被重复填写。这三次测试过了基本就不会出错。3.2 旋转链表先成环再断开旋转链表的要求是给定一个链表的头节点 head 和一个整数 k把链表每个节点向右移动 k 个位置。第一次做这道题的时候我把它想复杂了甚至一度想用快慢指针去找位置但实际上最优解只需要四步求长度、取模、成环、找断点。求长度就是遍历一遍链表同时记录尾节点。然后把尾节点 next 指向 head让链表成环。接着因为向右移动 k 位等价于把链表从倒数第 k 个位置断开。所以新的头节点就是第 len - k 个节点从第 0 个开始算断开位置在这个新头节点的前一个节点把它的 next 置空返回新头就行。def rotateRight(head, k): if not head or not head.next or k 0: return head length 1 tail head while tail.next: tail tail.next length 1 k % length if k 0: return head tail.next head steps length - k new_tail head for _ in range(steps - 1): new_tail new_tail.next new_head new_tail.next new_tail.next None return new_head这里几个细节一定要记住。第一k 必须取模。k 可能很大甚至大于链表长度如果直接当成向右移动 k 个节点循环次数会爆炸而且结果也错。k % length 之后k 为 0 的情况可以直接返回 head因为旋转一整圈等于没转。第二steps 的计算不要搞混。向右移动 k 位意思是新的头节点是倒数第 k 个节点也就是正数第 length - k 个节点下标从 0 开始。要让 new_tail 指向这个新头的前一个节点需要移动 length - k - 1 步。我在代码里写成range(steps - 1)这里的 steps length - k非常容易错建议在纸上画一个 5 个节点的链表设 k2手动推一遍下标。比如 1-2-3-4-5k2旋转后应该是 4-5-1-2-3新头是第 3 个节点下标从 0 算也就是 steps3new_tail 移动 2 步从 1 到 3然后 new_head 是 4把 3.next 置空正好。第三断链的顺序。先让 tail.next head 成环再找 new_tail最后把 new_tail.next 置空。如果你先断开了 tail.next链表就断了后面找不到完整链。链表题整体难度不大但胜在逻辑链长。旋转链表这道题把成环再断开这个技巧练熟以后环形链表 II、链表中环的入口这类问题理解起来也会快很多。我在实际刷题中把成环思路想通以后感觉整个人的链表题水平都提升了一截因为很多链表旋转、重排的题本质上都是先改变指针指向再找到合适的切断点。4. 特殊技巧题最后一个单词的长度与排列序列4.1 最后一个单词的长度倒着扫才是正解第58题最后一个单词的长度在 Hot 100 里算很简单的一题给一个字符串 s由若干单词和空格组成返回最后一个单词的长度。这个题考的是边界处理而不是算法。很多人的第一反应是s.split()[-1]一行搞定。但我建议你还是亲手写一下从后往前的扫描版本因为这道题放在 Hot 100 里不是为了让你刷熟练度而是为了培养从结果出发反向思考的习惯。题目要最后一个单词那直接从末尾往前找就行不用管前面的内容。代码可以这样写def lengthOfLastWord(s): i len(s) - 1 while i 0 and s[i] : i - 1 length 0 while i 0 and s[i] ! : length 1 i - 1 return length这题主要的坑在末尾可能有多余空格。比如 s Hello World 如果一上来就统计字符第一次遇到空格就停了结果是 0 或是错误值。所以代码里第一个 while 是专门跳过尾部空格的第二个 while 才真正统计单词长度。整个过程 O(n) 时间、O(1) 额外空间。我建议不要一上来就split还有另一个原因很多场景下你面对的字符串可能是流式输入或者非常大split 会把整个字符串切成很多子串内存开销是 O(n) 且常数不小。从后往前扫则完全不关心前面的内容省内存又直观。另外还有一种思路是正向扫描用两个变量 last_word_len 和 current_word_len遇到空格就把 current_word_len 清零遇到非空格就累加最后返回 current_word_len 或记录的上一个非空单词长度。这种写法适合在不能从后访问数据结构的时候用比如流式读取。面试时如果能主动说出从后往前扫和正向流式扫两种方案会显得你对边界情况的考虑更全面。别看这题简单我见过不少同学在面试时因为过于轻敌紧张之下把 i 的初始值写成 len(s)然后直接越界。还有一种错误是把两个 while 循环合在一起导致空格也算进去了。这些错误在简单题上出现反而比难题挂得更容易让人惋惜。4.2 排列序列用阶乘给每一位定位第60题排列序列是一个数学味道很浓的题给定 n 和 k返回 1 到 n 组成的所有排列中字典序第 k 个排列。注意 k 是从 1 开始计的不是从 0 开始。很多第一次做这道题的同学会直接想到回溯生成所有排列但当 n 到 9 的时候已经有 36 万多个排列生成全部再取第 k 个显然不是最优。正确思路是利用阶乘的性质逐位确定每一位上的数字。以 n4, k9 为例1 到 4 的所有排列共有 4! 24 个每个首位数字对应 3! 6 个排列。9 - 1 88 // 6 1说明第 9 个排列的首位数字是候选数字列表中的第 1 个下标从 0 计也就是数字 2。确定首位后k 更新为 8 % 6 2进入下一位继续在剩下的数字里用同样方式定位。代码可以这样写def getPermutation(n, k): fact [1] * n for i in range(1, n): fact[i] fact[i - 1] * i nums list(range(1, n 1)) k - 1 res [] for i in range(n - 1, -1, -1): index k // fact[i] k % fact[i] res.append(str(nums.pop(index))) return .join(res)这里有几个容易写错的地方。第一k 必须先减 1。因为题目给的 k 是 1-based而我们用的 index 是 0-based。不减 1 的话在整除边界时结果会整体错一位。第二fact 数组要预处理好。fact[i] 表示 i 的阶乘我习惯从 fact[0]1 开始然后循环乘到 n-1。循环里我用 fact[i] 时第一轮 in-1对应的是 (n-1)!刚好是固定第一位后剩下数字的排列总数。第三nums.pop(index) 这一步会让后续候选数字列表变短。虽然 pop 是 O(n) 操作导致总复杂度是 O(n²)但 n 最大也就是 9 左右完全无所谓。如果你用双向链表或者有序集合来优化 pop代码反而变复杂没必要。这题本质上就是康托展开的逆过程。你要是对数学公式不熟可以先用回溯感受一下排列生成的过程再对比数学解法会发现数学解法等于把哪一位选哪个数直接算出来而回溯是一路试错。面试中如果能讲清楚这个递推关系会很加分。这里有一个我总结的小技巧一旦题目里出现返回第 k 个排列、第 k 大的组合这类描述并且 n 的范围不大通常 1 到 9 左右你就要立刻想到乘阶乘定位别再傻乎乎地全量枚举。阶乘的增长速度远超想象回溯在 n 达到 10 时就开始吃力而数学解法几乎无压力。5. 七道题的高频失误点与二刷建议5.1 高频失误点速查表七道题刷完我把最常踩的坑整理成一张速查表二刷或者面试前扫一眼比重新翻代码高效得多。题号核心考点最高频失误点推荐解法55跳跃游戏i furthest 判断缺失没处理 n1贪心维护可达最远下标56合并区间更新右端点时没取 max排序 一次扫描57插入区间遍历结束后忘 append 新区间三段式线性扫描58最后一个单词长度末尾空格没跳过从后往前扫59螺旋矩阵 II奇数 n 中心多填一次四边收缩 边界判断60排列序列k 忘记减 1候选列表删除后索引错位阶乘分组定位61旋转链表k 没取模断点位置算错成环后断开这些坑有一个共同特点都不是思路上的问题而是实现时手滑。我在给朋友讲这几道题的时候经常强调算法面试挂人最多的不是想不出来而是想出来了但写挂。所以刷题的时候对自己狠一点每道题写完先故意跑一跑边界用例比如空输入、单元素、最大 k、全是相同数字的数组把这些用例变成肌肉记忆。另外我建议每道题在 AC 之后再回头看一遍代码把容易出错的那一行用注释标出来。比如合并区间的max(res[-1][1], r)、插入区间的res.append(newInterval)、螺旋矩阵的if top bottom、排列序列的k - 1。这些标记会像减速带一样提醒你下次写同类代码时自然就能避开。5.2 七题串联复习建议最后分享一个我自己的二刷方法。我不按题号顺序刷而是把这七道题按考点簇重新分组区间簇56 合并区间 57 插入区间练排序和扫描的顺序感覆盖簇55 跳跃游戏练维护可达区间右端的贪心顺带复习跳跃游戏 II方向模拟簇59 螺旋矩阵 II练边界收缩可延伸到螺旋矩阵 I、螺旋遍历二叉树如果有兴趣链表操作簇61 旋转链表练成环 找断点可延伸到环形链表系列字符串与数学簇58 最后一个单词长度 60 排列序列练边界处理和数学定位。我第一次刷 Hot 100 的时候是按照题单顺序一道一道硬啃刷到 55 到 61 这一段明显感觉到节奏变化因为题目类型跨度大很考验状态切换能力。后来二刷时我改用这种分组方式一周内集中把同类题全部过一遍效率高很多。对于这段题我的建议是不要只满足于AC 了每道题都追问一句这题的最优解是什么我当前做法的复杂度是多少如果面试官让我优化我能往哪个方向想把这几个问题在脑子里过一遍比多刷十道简单题有用得多。我自己刷题有个习惯每过一周会把做过的题重新看一遍题号先把思路在脑子里过一遍然后再打开代码。七道题如果能在五分钟内把思路和易错点全部说出来才算真正掌握了。第55到61这段题非常适合用来做这种口述复习的练习因为它们涉及的知识点跨度大能把贪心、排序、模拟、链表、数学、字符串全部串一遍。希望这篇文章能帮你在刷这一段的时候少踩几个坑。