第二天打卡题号 85-90。说实话这一组题比想象中烧脑最大矩形和扰乱字符串都属于那种“一看就会一写就废”的类型。不过把六道题刷完再回头看看知识点其实很集中单调栈、链表切割、递归记忆化、双指针、位运算、回溯去重。这篇就是我的完整复盘已经把这几天踩过的坑、绕过的弯、以及面试时容易被追问的细节都整理出来给同样在刷题的朋友做个参考。先说清楚这篇内容适合谁如果你正在准备算法面试或者刚开始按题号顺序刷 LeetCode想看看 85-90 题怎么快速摸清套路可以参考我的思路。我尽量把代码和推理过程都写出来不搞“只贴答案不解释”那一套。1. Day 2 整体复盘这六道题到底在考什么1.1 为什么按题号顺序刷我的节奏安排很多朋友纠结刷题顺序到底是按标签分类刷还是按题号顺序刷我个人的习惯是按题号顺序每天固定量。原因很简单按标签刷容易陷入舒适区今天全是双指针明天全是二叉树练多了会产生“我会了”的错觉换到综合场景就抓瞎。按题号顺序刷每天跟开盲盒一样动态规划、链表、递归、位运算轮着来强迫你把每个模块的知识捡起来。Day 1 刷完前面的题之后Day 2 正好轮到 85-90。我的节奏是上午先不翻题解自己硬想 20 分钟没思路就标记一下然后看题解理解核心解法晚上再不看代码手写一遍。这么做的好处是白天想过的思路即使错了也能在脑子里留下痕迹晚上重写时记忆特别牢。1.2 六道题的知识点分布与难度评估先把这六道题的整体情况摆出来方便大家一眼看清今天要面对的是什么题号题目标题难度核心考点关联知识点85最大矩形困难单调栈 动态规划思想84 题柱状图中最大的矩形86分隔链表中等链表拆分与拼接哑节点技巧87扰乱字符串困难递归 记忆化搜索区间划分、剪枝优化88合并两个有序数组简单逆序双指针归并排序思想89格雷编码中等位运算 / 镜像生成二进制编码90子集 II中等回溯 去重78 题子集、40 题组合总和 II从难度分布就能看出来这六道题是“两难两中一简一易”的混合组合压力主要压在 85 和 87 上。但这两题恰恰是今天收获最大的地方因为它们不是单纯考你背模板而是考你怎么把一个陌生问题拆成已经做过的问题。2. 从暴力到优化逐题拆解 85-902.1 第85题 最大矩形单调栈才是分水岭题面很简单给定一个由 0 和 1 组成的二维矩阵找出只包含 1 的最大矩形面积。第一次看到这道题最自然想到的是暴力枚举所有矩形四个边界一确定再检查内部是否全 1复杂度直接爆炸O(m^3 * n^3) 级别的写完面试官肯定摇头。正确的打开方式是把它转换成“柱状图中的最大矩形”也就是之前刷过的第 84 题。具体做法是按行遍历把每一行看成直方图的底边heights[j]表示当前位置往上连续为 1 的高度。遍历到当前行时如果matrix[i][j] 1高度加一否则清零。然后对heights调用 84 题的单调栈方法算出以当前行为底的最大矩形面积逐行更新答案。def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) heights [0] * cols ans 0 for row in matrix: for j in range(cols): if row[j] 1: heights[j] 1 else: heights[j] 0 ans max(ans, self.largestRectangleArea(heights)) return ans def largestRectangleArea(self, heights: List[int]) - int: stack [-1] max_area 0 heights.append(0) for i, h in enumerate(heights): while heights[stack[-1]] h: idx stack.pop() height heights[idx] width i - stack[-1] - 1 max_area max(max_area, height * width) stack.append(i) return max_area单调栈的核心逻辑是遍历到当前柱子时把栈里所有比它高的柱子都弹出来计算面积因为对那一根柱子来说当前这个更矮的柱子就是它的右边界而它左边第一个比它矮的柱子就是左边界左边界还在栈里。利用栈维护的单调递增性质能在 O(n) 时间内求出每根柱子能扩展的最大宽度。这个过程我调试时踩了一个坑heights.append(0)不能漏。如果不加这个哨兵柱遍历结束后栈里剩下的柱子没人帮它们触发“出栈计算面积”会直接漏算。我第一次写就是漏了这行样例怎么跑都少答案排查了半天才发现是边界处理问题。这个教训不只是在 85 题有用凡是单调栈题都要记得在数组末尾补一个最小值来清空栈。这题的时间复杂度是 O(m * n)因为每行更新高度是 O(n)调用一次单调栈 O(n)m 行就是 O(m * n)空间 O(n)。2.2 第86题 分隔链表哑节点的妙用题目要求把链表中小于 x 的节点排在大于等于 x 的节点之前而且要保持节点之间的相对顺序不变。比如1-4-3-2-5-2x 3结果应该是1-2-2-4-3-5。难点在于“相对顺序不变”这意味着不能排序也不能随意交换节点。最干净的做法是创建两个哑节点一个用来串所有小于 x 的节点另一个用来串所有大于等于 x 的节点遍历一次原链表按值决定挂到哪条链上最后把两条链拼起来。def partition(self, head: ListNode, x: int) - ListNode: small_dummy ListNode(0) large_dummy ListNode(0) small, large small_dummy, large_dummy cur head while cur: nxt cur.next if cur.val x: small.next cur small small.next else: large.next cur large large.next cur.next None cur nxt small.next large_dummy.next return small_dummy.next这里有个特别容易忽略的细节cur.next None必须加。如果不把当前节点从原链表里摘出来最后拼接的时候两条链之间可能会出现环。因为节点在挂到 small 链后它的 next 还指向原来链表的下一个节点等 large 链也串起来万一二者指向同一个节点循环链表就出来了。我调试的时候真遇到过这个问题表现为程序直接死循环或者“Time Limit Exceeded”。另外就是large_dummy.next要提前保存因为large_dummy.next在拼接后会被写入 small 链的尾部但如果在拼接时访问large_dummy.next没有问题真正需要注意的是最后返回的是small_dummy.next不是small本身。因为 small 指针已经移动到链尾了small_dummy.next才是头节点。时间复杂度 O(n)空间 O(1)这里说的 O(1) 是不算新节点占用的空间哑节点只是固定两个非常漂亮。面试时这道题还有一个常见追问能不能用原地拆分答案就是上面这个做法因为我们是把原链表的节点拆下来再挂到新链上本身就是原地操作只是额外用了两个哑节点。2.3 第87题 扰乱字符串递归里藏着记忆化这题应该是今天最抽象的一道。题目本身描述很绕给定两个字符串 s1 和 s2判断 s2 是否是 s1 的扰乱字符串。所谓扰乱就是把字符串从任意位置分成两个非空子串然后可以选择交换这两个子串的位置再对子串递归地做同样的操作。换句话说一个字符串在“翻转”若干次之后能变成另一个字符串。第一次读题我脑子里全是浆糊后来画了个树才明白每次划分把字符串分成左右两半递归判断左右两半是否匹配关键是有两种匹配方式——不交换左对左、右对右或者交换左对右、右对左。from functools import lru_cache class Solution: def isScramble(self, s1: str, s2: str) - bool: lru_cache(None) def dfs(a: str, b: str) - bool: if a b: return True n len(a) # 剪枝1字符构成不一致直接返回 False if sorted(a) ! sorted(b): return False # 枚举所有可划分的位置 for i in range(1, n): # 不交换 if dfs(a[:i], b[:i]) and dfs(a[i:], b[i:]): return True # 交换 if dfs(a[:i], b[n-i:]) and dfs(a[i:], b[:n-i]): return True return False return dfs(s1, s2)关键点在于两个剪枝。第一个剪枝是a b直接返回 True因为同一段子串不需要再递归。第二个剪枝是字符计数必须相同如果两个子串的字符组成都不一样那无论怎么翻转都不可能相等直接返回 False。这两个剪枝能把原本指数级的递归空间大幅压缩再配合lru_cache做记忆化实际跑起来很快。这道题还有一个很有意思的视角它可以看成一个区间 DP 问题状态是(a 的起始位置, b 的起始位置, 长度)转移就是枚举划分点。从递归到区间 DP其实就是把递归过程中的状态显式记录下来面试时如果被追问“能不能改成动态规划”你可以沿着这个思路回答。但第一次做递归 记忆化是最好理解的先写对再谈优化。复杂度上记忆化之后每个状态只会被计算一次状态数是 O(n^3)枚举划分点又是 O(n)所以总复杂度 O(n^4)n 是字符串长度。看着吓人但实际因为剪枝很凶LeetCode 上的用例都能过。2.4 第88题 合并两个有序数组从后往前是精髓这题标签是“简单”但我觉得它是今天最容易翻车的题之一。题面两个有序数组 nums1 和 nums2把 nums2 合并到 nums1 中不返回新数组直接原地改。nums1 的长度是 m n前 m 个是实际元素后面 n 个补零正好用来放 nums2 的元素。如果按正向思维从头开始合并问题就来了把 nums2 的小元素插到 nums1 前面时会把 nums1 原有的元素往后挤需要移动大量数据。更严重的是可能覆盖还没处理的元素。所以标准解法是从后往前填比较两个数组的末尾元素谁大就放到 nums1 末尾这个位置一定已经空出来了不会覆盖任何有效元素。def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: i, j, k m - 1, n - 1, m n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1这个代码的精妙之处在于循环条件是while j 0意味着只要 nums2 还没处理完就继续如果 nums1 先处理完i 变成 -1那剩下的 nums2 元素直接按原顺序铺到 nums1 前面如果 nums2 先处理完循环结束nums1 剩余元素已经在正确位置不用动。这就是为什么不需要额外处理“nums1 有剩余”的情况。我写这题时犯过一个低级错误把while j 0写成while i 0 and j 0结果 nums1 先遍历完时nums2 还剩一堆元素没合并进去输出完全错乱。记住这题的主导者是 nums2只要 nums2 没清空就必须继续填。时间复杂度 O(m n)空间 O(1)这也是归并排序 merge 阶段的经典写法算是面试里最基础的一题但以后写归并排序会觉得格外顺手。2.5 第89题 格雷编码位运算的对称性之美格雷编码是指 n 位二进制数字的序列要求相邻两个数字的二进制表示恰好有 1 位不同包括首尾两个数字也只差 1 位。这道题要求输出以 0 开头的任意一个有效格雷编码序列。刚看到这个题最容易想到暴力回溯每一位试着变复杂度 2^n 乘以检查开销写着写着就发现回溯很难控制“首尾相接”这个条件。标准解法其实非常优雅格雷编码的第 i 个数字 i ^ (i 1)。一行公式搞定。def grayCode(self, n: int) - List[int]: res [] for i in range(1 n): res.append(i ^ (i 1)) return res以 n 2 为例i 从 0 到 3算出0 ^ 0 0、1 ^ 0 1、2 ^ 1 3、3 ^ 1 2序列是[0, 1, 3, 2]检查一下000和 101差 1 位101和 311差 1 位311和 210差 1 位210和 000差 1 位。为什么这个公式成立可以这样理解i 从 0 增加到 i1 时二进制最低连续几位会翻转比如从 01117变到 10008最低三位从 1 变 0最高位从 0 变 1。i ^ (i 1)恰好能把“变化的位置”编码为新的比特差异所以相邻 i 得到的格雷码彼此只差 1 位。不需要死记公式理解了这层就能迁移到别的编码问题。这题面试时可能追问另一种做法镜像生成。已知 n-1 位的格雷码序列把它倒序再在最高位补 1就能得到 n 位格雷码。两种做法等价公式法代码更短但镜像生成更直观。我建议两个都掌握面试官让解释原理的时候用镜像生成讲起来更形象。2.6 第90题 子集 II回溯去重的关键在排序子集 II 是 78 题“子集”的升级版区别在于数组里可能有重复元素要求返回所有不重复的子集。比如nums [1, 2, 2]如果按 78 题的无脑回溯会得到两个[2]、两个[1,2]必须去重。去重有两种思路。第一种是拿 set 去重简单粗暴但这不是面试官想听的而且空间复杂度高。第二种是回溯时跳过同一层的重复元素这是标准解法。前提是先排序让相同的元素紧挨在一起。def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] def backtrack(start: int, path: List[int]) - None: res.append(path[:]) for i in range(start, len(nums)): if i start and nums[i] nums[i - 1]: continue path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return res这里的判断条件是i start不是i 0这个细节非常关键。i start的含义是在“同一层”的枚举中跳过后面出现的重复元素但如果这个重复元素是作为下一层递归的第一个元素出现的它就可以用。举个例子[1, 2, 2]第一层枚举到第二个 2 时因为i 2 start 0且nums[2] nums[1]所以跳过这就避免了重复的子集[2]可是在递归进去之后start变成 1第二个 2 作为路径中的第二个元素是完全合法的比如[1, 2, 2]这个子集就依赖它。如果错误地写成i 0所有重复元素都会被砍掉连[1, 2, 2]本身都出不来那我就又踩坑了。回溯题的复杂度很难精确表示对于 n 个元素的数组子集个数最多是 2^n每次生成一个子集要复制 path所以最坏 O(2^n * n)空间上递归深度 O(n)。3. 刷题过程中的调试与环境经验3.1 我在哪里刷题本地环境与在线判题的选择写这几道题时我的习惯是先在本地的 VS Code 里跑再粘到在线判题环境提交。本地调试最大优势是能看到完整堆栈和print输出。像 85 题这种数组题我一般会在largestRectangleArea里临时打印每根柱子的左右边界86 题链表题我会写一个小函数把链表打印成数组一眼看出有没有成环。不要小看这些土办法。单调栈的边界、链表的指向、递归的调用顺序这些在脑子里跑一遍容易漏实际打印出来才直观。等本地跑通了再贴到在线判题确认能省不少罚时。不过也要提醒一句本地调试归调试最后提交前一定把多余的print删掉不然刷题记录里全是输出错误。我见过太多人交了带 print 的代码然后被网络判题误判超时。3.2 几个让我走了弯路的地方今天最大的弯路在 85 题我把heights数组放在largestRectangleArea里又重新初始化了一遍结果每行算出来的都是同一个东西debug 了半天才发现问题出在“行与行之间高度是累积的不是重置的”。“累计”这个特性是这道题能复用 84 题的核心没有它每行都是一个独立的直方图根本无法体现“从本行往上连续 1 的数量”。另一个弯路在 87 题。我第一次直接用sorted(a) ! sorted(b)做剪枝但忘了在dfs里先判断a b。结果递归到长度为 1 时sorted(a) sorted(a)成立但循环范围range(1, 1)为空函数返回 False导致两个完全相同的字符串都判不了 True。后来补上a b的早返回才跑通。这里能看出来递归题的“最小子问题出口”往往就是能不能跑通的命门。4. 常见问题与排查技巧速查4.1 这组题最常踩的坑我整理了一张速查表把今天遇到的问题和排查思路都列出来以后复习直接看这张表。现象可能原因解决办法85 题答案偏小单调栈遍历完没清空栈数组末尾补 0 哨兵强制弹出所有柱子85 题超时高度数组没有逐行累计重复扫描确保heights[j] 1不要每行重算整列86 题死循环节点挂到新链后没有断开原 next每处理一个节点先cur.next None87 题相同字符串返回 False缺少a b的最小子问题出口递归函数开头先判断相等88 题输出缺元素主循环条件写成i 0 and j 0循环条件只判断j 090 题漏掉含重复元素的合法子集去重条件写成i 0改成i start只跳过同一层的重复元素这些坑单独看都不严重但在面试高压环境下很容易犯。我的建议是每道题刷完后把踩过的坑浓缩成一句话写在题解旁边方便隔几天回看。4.2 面试官追问时怎么扩展刷题不只是为了 AC更要在面试时体现深度。以这组题为例常见追问包括85 题一定会被问到“你用的单调栈是干嘛的”给你一个最简单的一维数组让你现场把每根柱子的左右边界求出来。只要你把“右边界是第一个更矮的柱子左边界是栈里剩下的前一个元素”讲清楚这题就算过关。86 题追问经常是“如果要求保持稳定性怎么办”。因为单链表的拆分天然是稳定的按原链表顺序挂到两条链上不会打乱相对顺序所以直接说“我这个解法本身就是稳定的”。87 题追问多半是“复杂度能不能优化”。可以从递归记忆化讲到区间 DP转移方程用状态(i1, i2, len)表示“从 s1 的 i1 开始和 s2 的 i2 开始、长度为 len 的子串是否能扰乱匹配”把递归改成三重循环虽然思维量大但状态转移清晰。88 题追问是“为什么从后往前不会覆盖”。因为后往前填的位置是 m n - 1 到某个位置这些位置在合并前都未使用或已经处理过不可能覆盖 nums1 还没参与比较的元素。89 题追问通常是“解释一下i ^ (i 1)为什么正确”。建议用镜像生成的例子先讲清楚格雷码的构建规则再说明这个公式在计算上等价于镜像生成。90 题追问是“去重的本质是什么”。本质是保证重复元素在每一层只会被选中一次而不是在路径的不同位置反复使用。5. 复习策略与下一步计划5.1 当晚怎么消化这六道题刷完不等于会了我晚上会做三件事。第一不看代码把每道题的核心思路写成一页纸类似“85 逐行算高度 84单调栈”“90 排序 同层去重”用一两句话逼自己抓住本质。第二把当天写过的代码先全部藏起来给自己 15 分钟在白纸上重新实现一遍尤其是 85 和 87。第三用费曼的方式讲给自己听比如“让我解释一下为什么格雷编码公式相邻只差一位”讲不下去的地方就是下次复习的重点。这几件事看起来麻烦但效果比再刷十道新题还明显。因为刷题真正要练的是从“看懂题解”到“独立写出”之间的那段距离这个距离只能靠主动回忆来缩短。5.2 后续安排按我的计划接下来一天会刷 91-96覆盖解码方法、反转链表 II、二叉树中序遍历、不同的二叉搜索树 II、恢复二叉搜索树、不同的二叉搜索树。这个区间同样硬核既有动态规划又有树的 Morris 遍历。我会把今天踩过的坑比如heights.append(0)、cur.next None、i start这些细节写进错题本后面每周复习一次。建议你也准备一个类似的错题本不需要很复杂记一条坑、一行原因、一个解法就够了比收藏一堆题解有用得多。刷题这件事短期拼的是题量长期拼的是复盘质量。Day 2 这六道题能坚持下来强度不算低但收获确实实在在。继续保持这个节奏几天后回头再看你会发现自己看题的视角已经不一样了。
LeetCode 85-90题复盘：单调栈、链表与回溯去重的算法面试要点
第二天打卡题号 85-90。说实话这一组题比想象中烧脑最大矩形和扰乱字符串都属于那种“一看就会一写就废”的类型。不过把六道题刷完再回头看看知识点其实很集中单调栈、链表切割、递归记忆化、双指针、位运算、回溯去重。这篇就是我的完整复盘已经把这几天踩过的坑、绕过的弯、以及面试时容易被追问的细节都整理出来给同样在刷题的朋友做个参考。先说清楚这篇内容适合谁如果你正在准备算法面试或者刚开始按题号顺序刷 LeetCode想看看 85-90 题怎么快速摸清套路可以参考我的思路。我尽量把代码和推理过程都写出来不搞“只贴答案不解释”那一套。1. Day 2 整体复盘这六道题到底在考什么1.1 为什么按题号顺序刷我的节奏安排很多朋友纠结刷题顺序到底是按标签分类刷还是按题号顺序刷我个人的习惯是按题号顺序每天固定量。原因很简单按标签刷容易陷入舒适区今天全是双指针明天全是二叉树练多了会产生“我会了”的错觉换到综合场景就抓瞎。按题号顺序刷每天跟开盲盒一样动态规划、链表、递归、位运算轮着来强迫你把每个模块的知识捡起来。Day 1 刷完前面的题之后Day 2 正好轮到 85-90。我的节奏是上午先不翻题解自己硬想 20 分钟没思路就标记一下然后看题解理解核心解法晚上再不看代码手写一遍。这么做的好处是白天想过的思路即使错了也能在脑子里留下痕迹晚上重写时记忆特别牢。1.2 六道题的知识点分布与难度评估先把这六道题的整体情况摆出来方便大家一眼看清今天要面对的是什么题号题目标题难度核心考点关联知识点85最大矩形困难单调栈 动态规划思想84 题柱状图中最大的矩形86分隔链表中等链表拆分与拼接哑节点技巧87扰乱字符串困难递归 记忆化搜索区间划分、剪枝优化88合并两个有序数组简单逆序双指针归并排序思想89格雷编码中等位运算 / 镜像生成二进制编码90子集 II中等回溯 去重78 题子集、40 题组合总和 II从难度分布就能看出来这六道题是“两难两中一简一易”的混合组合压力主要压在 85 和 87 上。但这两题恰恰是今天收获最大的地方因为它们不是单纯考你背模板而是考你怎么把一个陌生问题拆成已经做过的问题。2. 从暴力到优化逐题拆解 85-902.1 第85题 最大矩形单调栈才是分水岭题面很简单给定一个由 0 和 1 组成的二维矩阵找出只包含 1 的最大矩形面积。第一次看到这道题最自然想到的是暴力枚举所有矩形四个边界一确定再检查内部是否全 1复杂度直接爆炸O(m^3 * n^3) 级别的写完面试官肯定摇头。正确的打开方式是把它转换成“柱状图中的最大矩形”也就是之前刷过的第 84 题。具体做法是按行遍历把每一行看成直方图的底边heights[j]表示当前位置往上连续为 1 的高度。遍历到当前行时如果matrix[i][j] 1高度加一否则清零。然后对heights调用 84 题的单调栈方法算出以当前行为底的最大矩形面积逐行更新答案。def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) heights [0] * cols ans 0 for row in matrix: for j in range(cols): if row[j] 1: heights[j] 1 else: heights[j] 0 ans max(ans, self.largestRectangleArea(heights)) return ans def largestRectangleArea(self, heights: List[int]) - int: stack [-1] max_area 0 heights.append(0) for i, h in enumerate(heights): while heights[stack[-1]] h: idx stack.pop() height heights[idx] width i - stack[-1] - 1 max_area max(max_area, height * width) stack.append(i) return max_area单调栈的核心逻辑是遍历到当前柱子时把栈里所有比它高的柱子都弹出来计算面积因为对那一根柱子来说当前这个更矮的柱子就是它的右边界而它左边第一个比它矮的柱子就是左边界左边界还在栈里。利用栈维护的单调递增性质能在 O(n) 时间内求出每根柱子能扩展的最大宽度。这个过程我调试时踩了一个坑heights.append(0)不能漏。如果不加这个哨兵柱遍历结束后栈里剩下的柱子没人帮它们触发“出栈计算面积”会直接漏算。我第一次写就是漏了这行样例怎么跑都少答案排查了半天才发现是边界处理问题。这个教训不只是在 85 题有用凡是单调栈题都要记得在数组末尾补一个最小值来清空栈。这题的时间复杂度是 O(m * n)因为每行更新高度是 O(n)调用一次单调栈 O(n)m 行就是 O(m * n)空间 O(n)。2.2 第86题 分隔链表哑节点的妙用题目要求把链表中小于 x 的节点排在大于等于 x 的节点之前而且要保持节点之间的相对顺序不变。比如1-4-3-2-5-2x 3结果应该是1-2-2-4-3-5。难点在于“相对顺序不变”这意味着不能排序也不能随意交换节点。最干净的做法是创建两个哑节点一个用来串所有小于 x 的节点另一个用来串所有大于等于 x 的节点遍历一次原链表按值决定挂到哪条链上最后把两条链拼起来。def partition(self, head: ListNode, x: int) - ListNode: small_dummy ListNode(0) large_dummy ListNode(0) small, large small_dummy, large_dummy cur head while cur: nxt cur.next if cur.val x: small.next cur small small.next else: large.next cur large large.next cur.next None cur nxt small.next large_dummy.next return small_dummy.next这里有个特别容易忽略的细节cur.next None必须加。如果不把当前节点从原链表里摘出来最后拼接的时候两条链之间可能会出现环。因为节点在挂到 small 链后它的 next 还指向原来链表的下一个节点等 large 链也串起来万一二者指向同一个节点循环链表就出来了。我调试的时候真遇到过这个问题表现为程序直接死循环或者“Time Limit Exceeded”。另外就是large_dummy.next要提前保存因为large_dummy.next在拼接后会被写入 small 链的尾部但如果在拼接时访问large_dummy.next没有问题真正需要注意的是最后返回的是small_dummy.next不是small本身。因为 small 指针已经移动到链尾了small_dummy.next才是头节点。时间复杂度 O(n)空间 O(1)这里说的 O(1) 是不算新节点占用的空间哑节点只是固定两个非常漂亮。面试时这道题还有一个常见追问能不能用原地拆分答案就是上面这个做法因为我们是把原链表的节点拆下来再挂到新链上本身就是原地操作只是额外用了两个哑节点。2.3 第87题 扰乱字符串递归里藏着记忆化这题应该是今天最抽象的一道。题目本身描述很绕给定两个字符串 s1 和 s2判断 s2 是否是 s1 的扰乱字符串。所谓扰乱就是把字符串从任意位置分成两个非空子串然后可以选择交换这两个子串的位置再对子串递归地做同样的操作。换句话说一个字符串在“翻转”若干次之后能变成另一个字符串。第一次读题我脑子里全是浆糊后来画了个树才明白每次划分把字符串分成左右两半递归判断左右两半是否匹配关键是有两种匹配方式——不交换左对左、右对右或者交换左对右、右对左。from functools import lru_cache class Solution: def isScramble(self, s1: str, s2: str) - bool: lru_cache(None) def dfs(a: str, b: str) - bool: if a b: return True n len(a) # 剪枝1字符构成不一致直接返回 False if sorted(a) ! sorted(b): return False # 枚举所有可划分的位置 for i in range(1, n): # 不交换 if dfs(a[:i], b[:i]) and dfs(a[i:], b[i:]): return True # 交换 if dfs(a[:i], b[n-i:]) and dfs(a[i:], b[:n-i]): return True return False return dfs(s1, s2)关键点在于两个剪枝。第一个剪枝是a b直接返回 True因为同一段子串不需要再递归。第二个剪枝是字符计数必须相同如果两个子串的字符组成都不一样那无论怎么翻转都不可能相等直接返回 False。这两个剪枝能把原本指数级的递归空间大幅压缩再配合lru_cache做记忆化实际跑起来很快。这道题还有一个很有意思的视角它可以看成一个区间 DP 问题状态是(a 的起始位置, b 的起始位置, 长度)转移就是枚举划分点。从递归到区间 DP其实就是把递归过程中的状态显式记录下来面试时如果被追问“能不能改成动态规划”你可以沿着这个思路回答。但第一次做递归 记忆化是最好理解的先写对再谈优化。复杂度上记忆化之后每个状态只会被计算一次状态数是 O(n^3)枚举划分点又是 O(n)所以总复杂度 O(n^4)n 是字符串长度。看着吓人但实际因为剪枝很凶LeetCode 上的用例都能过。2.4 第88题 合并两个有序数组从后往前是精髓这题标签是“简单”但我觉得它是今天最容易翻车的题之一。题面两个有序数组 nums1 和 nums2把 nums2 合并到 nums1 中不返回新数组直接原地改。nums1 的长度是 m n前 m 个是实际元素后面 n 个补零正好用来放 nums2 的元素。如果按正向思维从头开始合并问题就来了把 nums2 的小元素插到 nums1 前面时会把 nums1 原有的元素往后挤需要移动大量数据。更严重的是可能覆盖还没处理的元素。所以标准解法是从后往前填比较两个数组的末尾元素谁大就放到 nums1 末尾这个位置一定已经空出来了不会覆盖任何有效元素。def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: i, j, k m - 1, n - 1, m n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1这个代码的精妙之处在于循环条件是while j 0意味着只要 nums2 还没处理完就继续如果 nums1 先处理完i 变成 -1那剩下的 nums2 元素直接按原顺序铺到 nums1 前面如果 nums2 先处理完循环结束nums1 剩余元素已经在正确位置不用动。这就是为什么不需要额外处理“nums1 有剩余”的情况。我写这题时犯过一个低级错误把while j 0写成while i 0 and j 0结果 nums1 先遍历完时nums2 还剩一堆元素没合并进去输出完全错乱。记住这题的主导者是 nums2只要 nums2 没清空就必须继续填。时间复杂度 O(m n)空间 O(1)这也是归并排序 merge 阶段的经典写法算是面试里最基础的一题但以后写归并排序会觉得格外顺手。2.5 第89题 格雷编码位运算的对称性之美格雷编码是指 n 位二进制数字的序列要求相邻两个数字的二进制表示恰好有 1 位不同包括首尾两个数字也只差 1 位。这道题要求输出以 0 开头的任意一个有效格雷编码序列。刚看到这个题最容易想到暴力回溯每一位试着变复杂度 2^n 乘以检查开销写着写着就发现回溯很难控制“首尾相接”这个条件。标准解法其实非常优雅格雷编码的第 i 个数字 i ^ (i 1)。一行公式搞定。def grayCode(self, n: int) - List[int]: res [] for i in range(1 n): res.append(i ^ (i 1)) return res以 n 2 为例i 从 0 到 3算出0 ^ 0 0、1 ^ 0 1、2 ^ 1 3、3 ^ 1 2序列是[0, 1, 3, 2]检查一下000和 101差 1 位101和 311差 1 位311和 210差 1 位210和 000差 1 位。为什么这个公式成立可以这样理解i 从 0 增加到 i1 时二进制最低连续几位会翻转比如从 01117变到 10008最低三位从 1 变 0最高位从 0 变 1。i ^ (i 1)恰好能把“变化的位置”编码为新的比特差异所以相邻 i 得到的格雷码彼此只差 1 位。不需要死记公式理解了这层就能迁移到别的编码问题。这题面试时可能追问另一种做法镜像生成。已知 n-1 位的格雷码序列把它倒序再在最高位补 1就能得到 n 位格雷码。两种做法等价公式法代码更短但镜像生成更直观。我建议两个都掌握面试官让解释原理的时候用镜像生成讲起来更形象。2.6 第90题 子集 II回溯去重的关键在排序子集 II 是 78 题“子集”的升级版区别在于数组里可能有重复元素要求返回所有不重复的子集。比如nums [1, 2, 2]如果按 78 题的无脑回溯会得到两个[2]、两个[1,2]必须去重。去重有两种思路。第一种是拿 set 去重简单粗暴但这不是面试官想听的而且空间复杂度高。第二种是回溯时跳过同一层的重复元素这是标准解法。前提是先排序让相同的元素紧挨在一起。def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] def backtrack(start: int, path: List[int]) - None: res.append(path[:]) for i in range(start, len(nums)): if i start and nums[i] nums[i - 1]: continue path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return res这里的判断条件是i start不是i 0这个细节非常关键。i start的含义是在“同一层”的枚举中跳过后面出现的重复元素但如果这个重复元素是作为下一层递归的第一个元素出现的它就可以用。举个例子[1, 2, 2]第一层枚举到第二个 2 时因为i 2 start 0且nums[2] nums[1]所以跳过这就避免了重复的子集[2]可是在递归进去之后start变成 1第二个 2 作为路径中的第二个元素是完全合法的比如[1, 2, 2]这个子集就依赖它。如果错误地写成i 0所有重复元素都会被砍掉连[1, 2, 2]本身都出不来那我就又踩坑了。回溯题的复杂度很难精确表示对于 n 个元素的数组子集个数最多是 2^n每次生成一个子集要复制 path所以最坏 O(2^n * n)空间上递归深度 O(n)。3. 刷题过程中的调试与环境经验3.1 我在哪里刷题本地环境与在线判题的选择写这几道题时我的习惯是先在本地的 VS Code 里跑再粘到在线判题环境提交。本地调试最大优势是能看到完整堆栈和print输出。像 85 题这种数组题我一般会在largestRectangleArea里临时打印每根柱子的左右边界86 题链表题我会写一个小函数把链表打印成数组一眼看出有没有成环。不要小看这些土办法。单调栈的边界、链表的指向、递归的调用顺序这些在脑子里跑一遍容易漏实际打印出来才直观。等本地跑通了再贴到在线判题确认能省不少罚时。不过也要提醒一句本地调试归调试最后提交前一定把多余的print删掉不然刷题记录里全是输出错误。我见过太多人交了带 print 的代码然后被网络判题误判超时。3.2 几个让我走了弯路的地方今天最大的弯路在 85 题我把heights数组放在largestRectangleArea里又重新初始化了一遍结果每行算出来的都是同一个东西debug 了半天才发现问题出在“行与行之间高度是累积的不是重置的”。“累计”这个特性是这道题能复用 84 题的核心没有它每行都是一个独立的直方图根本无法体现“从本行往上连续 1 的数量”。另一个弯路在 87 题。我第一次直接用sorted(a) ! sorted(b)做剪枝但忘了在dfs里先判断a b。结果递归到长度为 1 时sorted(a) sorted(a)成立但循环范围range(1, 1)为空函数返回 False导致两个完全相同的字符串都判不了 True。后来补上a b的早返回才跑通。这里能看出来递归题的“最小子问题出口”往往就是能不能跑通的命门。4. 常见问题与排查技巧速查4.1 这组题最常踩的坑我整理了一张速查表把今天遇到的问题和排查思路都列出来以后复习直接看这张表。现象可能原因解决办法85 题答案偏小单调栈遍历完没清空栈数组末尾补 0 哨兵强制弹出所有柱子85 题超时高度数组没有逐行累计重复扫描确保heights[j] 1不要每行重算整列86 题死循环节点挂到新链后没有断开原 next每处理一个节点先cur.next None87 题相同字符串返回 False缺少a b的最小子问题出口递归函数开头先判断相等88 题输出缺元素主循环条件写成i 0 and j 0循环条件只判断j 090 题漏掉含重复元素的合法子集去重条件写成i 0改成i start只跳过同一层的重复元素这些坑单独看都不严重但在面试高压环境下很容易犯。我的建议是每道题刷完后把踩过的坑浓缩成一句话写在题解旁边方便隔几天回看。4.2 面试官追问时怎么扩展刷题不只是为了 AC更要在面试时体现深度。以这组题为例常见追问包括85 题一定会被问到“你用的单调栈是干嘛的”给你一个最简单的一维数组让你现场把每根柱子的左右边界求出来。只要你把“右边界是第一个更矮的柱子左边界是栈里剩下的前一个元素”讲清楚这题就算过关。86 题追问经常是“如果要求保持稳定性怎么办”。因为单链表的拆分天然是稳定的按原链表顺序挂到两条链上不会打乱相对顺序所以直接说“我这个解法本身就是稳定的”。87 题追问多半是“复杂度能不能优化”。可以从递归记忆化讲到区间 DP转移方程用状态(i1, i2, len)表示“从 s1 的 i1 开始和 s2 的 i2 开始、长度为 len 的子串是否能扰乱匹配”把递归改成三重循环虽然思维量大但状态转移清晰。88 题追问是“为什么从后往前不会覆盖”。因为后往前填的位置是 m n - 1 到某个位置这些位置在合并前都未使用或已经处理过不可能覆盖 nums1 还没参与比较的元素。89 题追问通常是“解释一下i ^ (i 1)为什么正确”。建议用镜像生成的例子先讲清楚格雷码的构建规则再说明这个公式在计算上等价于镜像生成。90 题追问是“去重的本质是什么”。本质是保证重复元素在每一层只会被选中一次而不是在路径的不同位置反复使用。5. 复习策略与下一步计划5.1 当晚怎么消化这六道题刷完不等于会了我晚上会做三件事。第一不看代码把每道题的核心思路写成一页纸类似“85 逐行算高度 84单调栈”“90 排序 同层去重”用一两句话逼自己抓住本质。第二把当天写过的代码先全部藏起来给自己 15 分钟在白纸上重新实现一遍尤其是 85 和 87。第三用费曼的方式讲给自己听比如“让我解释一下为什么格雷编码公式相邻只差一位”讲不下去的地方就是下次复习的重点。这几件事看起来麻烦但效果比再刷十道新题还明显。因为刷题真正要练的是从“看懂题解”到“独立写出”之间的那段距离这个距离只能靠主动回忆来缩短。5.2 后续安排按我的计划接下来一天会刷 91-96覆盖解码方法、反转链表 II、二叉树中序遍历、不同的二叉搜索树 II、恢复二叉搜索树、不同的二叉搜索树。这个区间同样硬核既有动态规划又有树的 Morris 遍历。我会把今天踩过的坑比如heights.append(0)、cur.next None、i start这些细节写进错题本后面每周复习一次。建议你也准备一个类似的错题本不需要很复杂记一条坑、一行原因、一个解法就够了比收藏一堆题解有用得多。刷题这件事短期拼的是题量长期拼的是复盘质量。Day 2 这六道题能坚持下来强度不算低但收获确实实在在。继续保持这个节奏几天后回头再看你会发现自己看题的视角已经不一样了。
