力扣刷题记录写到第三期正好是刷题打卡第五十天左右。这一阶段的做题感受跟前面两期最大的区别是已经从看题就懵、需要翻题解进到了拿到题能先判断大概属于哪个知识点的状态。说不上突飞猛进但明显觉得刷题状态不一样了。所以这一期记录我打算换一种写法不按题号顺序罗列而是把这一阶段沉淀下来的专题套路、几道印象最深的题的完整思考过程包括踩过的坑一次性梳理清楚。这个阶段适合正在刷题但感觉做一道忘一道的人参考我的核心思路是从随机刷题转向专题刷题用套路化思考替代题海战术。1. 第三期选题思路我为什么锁定二叉树、双指针和滑动窗口这期刷题计划和前两期完全不同。前两期我基本是顺着题库顺序往下做以简单题为主遇到难题就翻题解做了二三十道之后发现一个问题做过类似的题换个马甲又不会了。这就是典型的雾里刷题——题目没少刷知识结构却没有建立起来。所以第三期我做了一个非常关键的调整不做单题做专题。1.1 专题刷题优于随机刷题的三个理由第一个理由是覆盖面可控。力扣题目的总量很大逐题顺序刷非常容易陷入越刷越没底的状态。专题刷题不一样一个专题大概十到二十道题基本能覆盖这个知识点的绝大多数常见变化刷完一轮会明显感觉到这类题型的常见出法你都见过了。第二个理由是套路容易迁移。数据结构类题目有一个特点同一种结构解题模式高度相似。练完一组二叉树的遍历题再去做最近公共祖先、路径和之类的题思考路径几乎是相通的都是先从递归边界、递归子树、合并结果三个问题入手。这种迁移带来的正反馈比一道一道孤立刷题强太多。第三个理由是复习负担小。随机刷题时每道题都是新的忘记成本很低。专题刷题因为题目之间有强关联看到某道题能自然联想到同类题记忆牢固程度完全不一样。第三期我回头翻前两期做过的题能一眼反应出解法的基本都是反复出现在专题里的题目。1.2 二叉树、双指针、滑动窗口为什么是黄金组合这一期选这三个专题不是随便挑的。我大概翻了下后续要刷的内容也看了不少算法相关的讨论发现不管是笔试还是面试考来考去最频繁的其实就是这几个方向。二叉树是练递归和DFS/BFS的最佳载体。树的天然递归结构决定了树上很多题都能递归解很多人递归基础差本质上是因为没在树这种结构上练够。双指针解决的是一类数组和链表问题核心是让原本暴力O(n^2)的枚举变成O(n)性价比特别高。滑动窗口则可以说是字符串子串问题的通用框架最长无重复字符子串、覆盖子串、长度最小的子数组基本都是同一个模型。把这三个专题放在同一期刷还有一层考虑它们需要三种差异足够大的思考模式。树的递归、双指针的归纳、滑动窗口的状态维护在思维模式上互不相同交替训练比连续几天只刷同类题的记忆效果更好。如果你的时间比较紧这三个专题的性价比是最高的它们几乎占据了算法题里大量高频题的核心能力。这期的总体安排是每个专题用一周左右每天两道题一道深入吃透一道快速巩固。吃透的标准是不看题解能独立写出来并且能给一个完全没做过这道题的人讲明白。这两条标准让刷题节奏明显慢了下来但经过一个月的验证这种慢反而值得。2. 解题套路拆解三类高频题型的思考模型专题刷题最关键的是建立起见到题目先归位的能力。看到一道题第一反应应该是这题属于哪个题型用哪种套路。下面把三个专题的思考模型逐个拆开都是这一期里反复用并且验证过的。2.1 二叉树问题递归三板斧与迭代控制几乎所有的二叉树题目都能套用同一套递归框架。我把这个框架总结成三个问题。第一个问题递归的结束条件是什么对二叉树来说通常就是当前节点为空节点时返回。我写递归时习惯先把这一行写上防止写深了之后忘记处理边界。第二个问题需要对左子树和右子树分别做什么操作第三个问题拿到子树返回的结果后如何合并成当前节点的答案以求最大深度的题目为例结束条件是空节点返回0左子树和右子树分别递归求出深度合并结果是取两者较大值再加1这个加1代表当前节点自己占的那一层。这就是二叉树递归题的完整思考过程。它看起来很简单但大量树的问题都能用这条路想通。迭代写法就没那么统一了核心是用显式栈代替系统的调用栈。前序、中序、后序三种遍历各有固定的压栈顺序层序则需要用到队列。我个人的建议是在力扣环境下想快速通过就用递归想锻炼控制能力再尝试迭代。递归能解决的题迭代基本也都能解但代码复杂度会明显上升笔试场景下没必要和自己较劲。2.2 双指针问题左右指针与快慢指针的分工双指针这个叫法虽然简单实际包含两个完全不同的子类型。左右指针最常出现在数组排序后找组合的场景比如三数之和、两数之和变体、盛最多水的容器。这类题的前提通常是数组有序两个指针分别指向头部和尾部根据当前元素和与目标值的大小关系移动其中一个指针把枚举复杂度降一个维度。这个过程的核心是每次移动指针都必须能说明它不会漏掉正确答案否则就不是优化而是碰运气。快慢指针则是链表题目的常用大招。环形链表检测、寻找链表中点、寻找倒数第K个节点都能用一快一慢两个指针完成。背后的思路其实是路程差快指针每次走两步慢指针每次走一步在一个有限的环上两者终会相遇。我第一次见到这个解法时觉得非常巧妙但它的出发点只是一个朴素直觉——速度不同在闭环里快的肯定会追上慢的。判断一道题该用左右指针还是快慢指针一般看数据结构就行数组题目基本是左右指针链表题目基本是快慢指针。当然也有例外比如反转字符串这类数组题用的就完全是左右指针的思路。2.3 滑动窗口问题窗口合法性的维护套路滑动窗口题的模板比二叉树递归还要固定。核心是一个左边界和一个右边界右边界不停向右扩展把新字符或新数字纳入窗口一旦窗口不再满足题目要求就移动左边界缩小窗口直到恢复合法。这样右边界走完整个数组每个元素最多被进出窗口各一次整体时间复杂度是O(n)。这里最关键的是想清楚合法状态是什么以及用什么样的数据结构来记录。最长无重复字符子串题记录的是当前窗口内出现过的字符用Set就够覆盖类题目需要统计每个字符出现的次数得用字典。很多人写滑动窗口容易写进死循环我的经验是右边界加入窗口后马上判断合法性合法就更新答案不合法就收缩。收缩完之后不需要重新判断合法性因为收缩结束的位置恰好是合法状态直接继续右移就行。这三个模型互相配合基本能覆盖这一阶段遇到的大部分中等难度题目。下面进入实操环节记录这期里四道给我留下最深印象的题目。3. 四道典型题的完整实操记录这期刷了大概三十道题我挑四道比较有代表性的把做题时的思考过程、最终写法、AC之后还做了什么都写出来。每道题都有可以复用的点不是AC了就算结束。3.1 反转链表迭代5分钟递归看成外包反转链表是链表入门第一题我前两期一度写不顺原因是递归版本始终想不清楚凭什么这样就反转了。迭代版本的思路其实很直接遍历链表时把当前节点的next指针指向前一个节点。但这里有一个特别容易忽视的细节如果先改curr.next后面就找不到原本的下一个节点了。所以固定的三步顺序是先保存nxt curr.next再执行curr.next prev最后移动prev和curr。这个顺序我写错过三次后来总结成一句口诀先存后改再移。递归版本的思考角度完全不同。不要把它理解成在同一个函数里反复调用而是想成我把后面的链表交给另一个函数去反转它返回一个反转后的头节点。此时当前节点只需要做两件事让后面那个节点的next指向自己再把自己的next置空。这本质上就是把重活外包出去至于为什么能反转的细节在递归层层展开的时候自然成立。def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_headAC之后我做了两件事。第一是拿三个节点的链表在纸上把递归展开画一遍把每个状态标清楚这一画之后再遇到树的递归题心里就踏实很多。第二是拿空链表、单节点链表、两个节点链表三组边界用例把迭代版和递归版都跑一遍三个用例过了这题才算真稳。3.2 二叉树最大深度DFS和BFS的取舍最大深度这道题是二叉树专题里练递归和层序都不错的一道。递归写法基本就是模板但需要理解为什么是左子树深度和右子树深度取较大值再加1。树的深度定义是从根到最远叶子节点的节点数因此对于任意一个节点它的深度等于左子树或右子树深度的较大值再加上当前节点占的1层。这个推理直接对应代码逻辑。def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))迭代层序版本也值得写一遍因为层序天然能数出第几层数到最后一层就是深度。层序用队列这个队列是核心每次处理完当前层的所有节点后深度加1直到队列为空。def maxDepth(root): if not root: return 0 from collections import deque queue deque([root]) depth 0 while queue: for _ in range(len(queue)): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth两个版本我都保留在笔记里。同一道题用多种解法去写最大的价值在于理解DFS和BFS的本质区别递归是深度优先一层下去摸到叶子再回来层序是广度优先一层一层从上往下清点。理解了这一点后面遇到求最短路径判断二叉树是否对称这类问题就能快速判断该往哪个方向思考。3.3 最长无重复字符子串窗口怎么收缩是重点这道题是滑动窗口专题最典型的一道。题目是给一串字符找到不含重复字符的最长子串的长度比如在abcabcbb中最长的是abc长度是3。我第一版写的是暴力解法枚举每个起点从起点往右扩展遇到重复就停统计长度。时间复杂度是O(n^2)短字符串上没问题字符串一长就明显卡住。滑动窗口版本的核心数据结构是一个Set保存当前窗口内的字符。右指针每走一步先检查当前字符是否在Set里如果在说明重复了那就不断从Set里删掉s[left]并且把left右移直到把重复字符清走如果不在直接加入Set此时窗口一定合法更新最长长度。代码很短。def lengthOfLongestSubstring(s): window set() left 0 ans 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left 1 window.add(ch) ans max(ans, right - left 1) return ans这里最容易踩的坑是为什么收缩完不用重新检查合法性。因为重复的来源只有刚加入的chleft不断右移其实就是把窗口里的字符逐个删掉直到ch在窗口里不再出现此时窗口一定重新合法。这个点一旦想通滑动窗口类的题目基本都能用同一套模板写这也是我建议把模板敲熟、而不是死记每道题答案的原因。3.4 三数之和排序去重的细腻边界三数之和是双指针专题里的一道硬题。题目要求找到所有三个数让它们的和为0而且结果里不能有重复的三元组。暴力三层循环肯定超时正解是先排序再上双指针。排序的意义在于数组有序之后固定第一个数剩下两个数就可以用左右指针去逼近目标值。左指针从固定数的右边开始右指针从数组末尾开始两数之和偏大就右指针左移偏小就左指针右移。固定数循环n-2次每次双指针扫一轮整体复杂度O(n^2)比暴力O(n^3)好太多。去重才是这道题真正考人的地方。固定数在进入每轮循环时如果和上一轮相等就跳过找到一组解后left和right也要跳过后面的重复值。三处去重少一处都会输出重复三元组。我第一次提交时漏了left和right的跳过结果输出里出现大量重复组合跑测试用例才发现问题。def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i-1]: continue left, right i 1, n - 1 target -nums[i] while left right: s nums[left] nums[right] if s target: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return res去重的底层逻辑是排序让相等的数相邻相邻重复就可以安全跳过因为同一个值只需要被考虑一次。遇到这类去重问题时最好都自己讲一遍这个逻辑能讲明白就说明这一块真的过关了。4. 从刷题到能力沉淀我的四遍法与复盘笔记第三期刷到一半我开始注意到一个事实很多题我做出来了但过了三天可能又做不出来。这并不代表笨只是记忆管理出了问题。刷题如果不能转化为长期记忆本质上就是在做体力劳动。后来我调整了方式逐渐形成了适合自己的四遍刷题法和复盘笔记法。4.1 四遍刷题法从抄题解到独立复现我的四遍法是这样的。第一遍先读题尝试思考15分钟。如果15分钟都没有完整思路就直接看题解。注意关键词是完整思路——不是看了题解觉得好像懂了就翻过去而是要把题解思路读透然后合上答案自己在代码编辑器里重新写一遍。这一遍是很多人缺的因为看题解会产生一种虚假的掌握感只有亲手敲出来才算第一次真正学会。第二遍隔一天再做一次。这一遍不看提交过的代码完全凭第一遍形成的思路去写。如果第二遍写得磕磕绊绊说明第一遍并没有真正消化需要退回第一遍重新来。我通常把这一步放在第二天的早上花十分钟完成目的不是刷数量是确认昨天真的记住了。第三遍换一个角度优化。比如第一遍用递归第三遍就试着用迭代第一遍复杂度是O(n^2)第三遍就想想有没有O(n)的做法。这一步不是为了炫技而是逼大脑从不同路径理解同一道题理解会立体得多。第四遍讲出来。找一个没做过这道题的朋友把题目讲给他听或者自己在笔记里写一篇完整的文字题解。凡是讲不清楚、写不明白的地方就是自己还没吃透的漏洞。四遍走完这道题才真正属于你。这套方法看起来慢实际过程中不需要反复重做效率反而高。4.2 复盘笔记记录什么才不算白刷我在笔记里存了三十多条刷题复盘每条格式都一样包含题目简化描述、首次通过用时、错误原因、核心套路总结。最容易忽略的两个维度是错误原因和复杂度分析。错误原因特别重要因为很多人做错是反复错在同一类细节上比如边界条件漏判、循环里指针的移动顺序写反。把这些错误原因分类统计才会发现自己的最大薄弱点在哪。复杂度分析也不能跳过每道题都写清楚解法的空间和时间开销才能逐步建立对算法优劣的判断力而不是AC了就觉得自己很强。还有一个我一直坚持的维度是同类题联系。每写完一题我会花几分钟想想这道题和本周做过的哪些题用了同一个套路然后写在这条笔记的末尾。刷题最怕做一道忘一道而这个小动作相当于每次都在给大脑做一次索引归档之后的复习效率提升非常明显。5. 刷题路上的常见问题与排查实录刷题过程中踩的坑很多时候比做题本身带来更多成长。这期梳理几个高频问题按现象、原因、处理办法的方式整理出来。5.1 递归栈溢出调高限制只是治标第三期在做递归专题时遇到过几次报错提示递归深度超限。Python的默认递归深度大约是一千层但有些链表的长度就能超过这个数。网上有建议把递归深度限制调高到一万这只能让程序暂时不报错并没有真正解决问题——数据再深一层照样崩。正确的思路是认清递归适用的场景。递归适合树的这类天然深度可控的结构树的深度通常不会离谱。而超长链表这种容易形成深链的结构必须优先考虑迭代写法。判断标准很简单看数据会不会形成一条很长的链。如果是果断写循环或者用显式栈。排查这类问题我有一套固定流程。第一步确认报错发生在哪个函数看递归路径是否比自己预想的长第二步构造一个最长的输入用例看实际递归深度是多少第三步判断这个深度在默认限制内是否安全不安全立刻换非递归实现。这套流程走过几次再遇到递归超限的报错就淡定了。5.2 边界条件漏判最小用例测试法刷题提交被判定解答错误十次有八次是边界条件。链表题的空链表、二叉树题的空树、数组题的空数组这些问题我在前两期里反复踩。后来我给自己定了一条规矩写完代码不管多自信都先把几个最小用例跑一遍。具体是空输入、只有一个元素的输入、只有两个元素的输入、所有元素值相同、输入顺序为反序。这五个用例是我从大量报错里总结出来的能覆盖绝大多数边界问题。背后有个通用思想叫最小化触发。很多bug不是逻辑整体错了而是代码里某个分支没有覆盖到特殊情况。最小用例测试法就是主动构造最小规模的特殊数据让边界分支的代码路径真正执行一次。虽然看起来是个土办法但排查效率比对着代码干看高得多。5.3 思路正确但代码总是有小毛病局部变量与循环结构还有一类问题很隐蔽解题思路完全正确但提交之后总是有小毛病或者运行耗时很高。我从这期实战里总结出两个主要原因。第一个原因是局部变量的作用域搞错。例如在循环里初始化了一个变量却希望循环结束后还能用结果每次循环都被重置最终答案自然不对。定位这类问题最快的方法是在关键位置打印日志观察这个变量的值在一个循环周期内是怎么变的。第二个原因是循环结构选错。典型的就是用for循环去手动改迭代变量这在Python里是不行的——for循环每次迭代会自动重新赋值迭代变量手动修改不会影响循环进度很容易造成逻辑错乱或者死循环。需要手动控制边界的时候直接使用while循环是更安全的选择。如果超出的是时间限制优先排查有没有重复计算。比如三层循环内层在做加法可以先预处理前缀和把暴力O(n^3)降下来。这类优化不会自己出现需要主动去挖。第三期以来遇到的高频问题整理成了一张速查表遇到同类问题可以直接照顺序排查。现象常见原因快速处理办法递归报错提示深度超限递归层数超过默认限制换成迭代或显式栈尤其针对长链结构解答错误且数据规模较小边界条件漏判空输入、单元素、双元素等最小用例逐个跑通输出结果包含重复项去重逻辑不完整排序后相邻相等跳过检查每一个循环层级提交通过但运行耗时高算法复杂度过高检查是否存在暴力循环用双指针或前缀和优化本地运行正常但提交出错未处理某些特殊输入对照题目约束检查每个分支是否有返回6. 环境配置与刷题节奏的经验谈这一期除了刷题本身我对刷题环境和节奏也做了不少调整。这两件事看起来和算法关系不大实际上对状态影响非常大。6.1 语言与环境Python的优与坑我用Python刷题原因很简单语法简洁、写起来快在力扣环境下运行速度对大多数题都够。但Python有几个需要提前避开的点不然会在低级问题上浪费很多时间。第一是引用类型的问题。new_list old_list这样赋值后两者共享同一片内存修改new_list会同步改到old_list。在需要复制数组的题目里必须用切片或者copy方法创建独立对象。这种问题在数组、列表类的题目里出现频率很高。第二个是collections模块值得提前熟悉。deque是双端队列处理滑动窗口和层序遍历基本是标配Counter做字符统计比手写字典方便非常多defaultdict可以省去一堆判空的代码。这四个东西deque、Counter、defaultdict、heapq是我刷题时使用频率最高的建议在正式刷题前先花半小时过一遍它们常用的API。还有一个小习惯是本地准备好统一的代码模板包括常见的import语句和输入输出辅助函数。虽然力扣已经处理了输入输出本地调试的时候还是需要一套顺手的脚手架可以减少在环境问题上反复折腾的时间。6.2 每天刷多少题以保留状态感为底线这里讲两个让我刷题节奏更可持续的小体会。第一个体会是每天刷题数量不重要重要的是保持住状态感。状态感的意思是打开编辑器看到一道不太难的中等题心里不慌知道自己大概率能一步一步做出来。这个状态感一旦超过三四天不碰题就会明显消退。所以我把刷题频率定成每天早上四十分钟做两道题。如果当天状态不好只吃透一道也没问题关键是每天见一面保持和算法题的熟悉感。这种细水长流比周末一口气刷八个小时的效果要好。休息日集中刷题第二天基本都会出现明显的大脑疲劳感而每天固定四十分钟反而更容易坚持。第二个体会是把做题和记录分开。做题的时候专注做题复盘的时候专注复盘。如果一边做题一边写笔记两个任务互相干扰做题容易敷衍笔记也记不细。我自己的流程是前面二十分钟做一道新题后面二十分钟做一道同类旧题并整理复盘。这个节奏稳定下来后整个第三期的产出效率明显提升。关于每周节奏我给自己定了这么一张表也贴出来做个参考。时间任务目标每天早上前20分钟做一道新题维持对新题型的识别能力每天早上后20分钟做一道同类旧题并整理复盘通过类比巩固套路周末其中一天回顾本周所有错题把一周的错误沉淀成经验每月最后一天复选一道经典难题口头讲解验证长期记忆和理解深度到这里第三期刷题记录的核心内容差不多写完了。最后分享一个这期收获最大的小技巧用讲题来验收学习效果。方法很简单每做完一道值得记录的题就打开手机录音假装自己在给一个刚开始学算法的朋友讲题讲清楚题目在问什么、用了什么套路、为什么这么写、复杂度是多少。讲的过程中一旦卡壳那个卡壳的位置就是自己还没理解透的地方回到题目里再琢磨。我这期录过好几段回放时发现了很多问题比如这里我为什么跳过不讲了这个复杂度其实我根本没算对。坚持这个习惯之后做题的稳定性提升明显因为讲题会强迫把模糊的知识点变成清清爽爽的语言表达。下期我计划把重心放在动态规划专项上连续刷两周再整理成新一期记录。
力扣刷题记录写到第三期正好是刷题打卡第五十天左右。这一阶段的做题感受跟前面两期最大的区别是已经从看题就懵、需要翻题解进到了拿到题能先判断大概属于哪个知识点的状态。说不上突飞猛进但明显觉得刷题状态不一样了。所以这一期记录我打算换一种写法不按题号顺序罗列而是把这一阶段沉淀下来的专题套路、几道印象最深的题的完整思考过程包括踩过的坑一次性梳理清楚。这个阶段适合正在刷题但感觉做一道忘一道的人参考我的核心思路是从随机刷题转向专题刷题用套路化思考替代题海战术。1. 第三期选题思路我为什么锁定二叉树、双指针和滑动窗口这期刷题计划和前两期完全不同。前两期我基本是顺着题库顺序往下做以简单题为主遇到难题就翻题解做了二三十道之后发现一个问题做过类似的题换个马甲又不会了。这就是典型的雾里刷题——题目没少刷知识结构却没有建立起来。所以第三期我做了一个非常关键的调整不做单题做专题。1.1 专题刷题优于随机刷题的三个理由第一个理由是覆盖面可控。力扣题目的总量很大逐题顺序刷非常容易陷入越刷越没底的状态。专题刷题不一样一个专题大概十到二十道题基本能覆盖这个知识点的绝大多数常见变化刷完一轮会明显感觉到这类题型的常见出法你都见过了。第二个理由是套路容易迁移。数据结构类题目有一个特点同一种结构解题模式高度相似。练完一组二叉树的遍历题再去做最近公共祖先、路径和之类的题思考路径几乎是相通的都是先从递归边界、递归子树、合并结果三个问题入手。这种迁移带来的正反馈比一道一道孤立刷题强太多。第三个理由是复习负担小。随机刷题时每道题都是新的忘记成本很低。专题刷题因为题目之间有强关联看到某道题能自然联想到同类题记忆牢固程度完全不一样。第三期我回头翻前两期做过的题能一眼反应出解法的基本都是反复出现在专题里的题目。1.2 二叉树、双指针、滑动窗口为什么是黄金组合这一期选这三个专题不是随便挑的。我大概翻了下后续要刷的内容也看了不少算法相关的讨论发现不管是笔试还是面试考来考去最频繁的其实就是这几个方向。二叉树是练递归和DFS/BFS的最佳载体。树的天然递归结构决定了树上很多题都能递归解很多人递归基础差本质上是因为没在树这种结构上练够。双指针解决的是一类数组和链表问题核心是让原本暴力O(n^2)的枚举变成O(n)性价比特别高。滑动窗口则可以说是字符串子串问题的通用框架最长无重复字符子串、覆盖子串、长度最小的子数组基本都是同一个模型。把这三个专题放在同一期刷还有一层考虑它们需要三种差异足够大的思考模式。树的递归、双指针的归纳、滑动窗口的状态维护在思维模式上互不相同交替训练比连续几天只刷同类题的记忆效果更好。如果你的时间比较紧这三个专题的性价比是最高的它们几乎占据了算法题里大量高频题的核心能力。这期的总体安排是每个专题用一周左右每天两道题一道深入吃透一道快速巩固。吃透的标准是不看题解能独立写出来并且能给一个完全没做过这道题的人讲明白。这两条标准让刷题节奏明显慢了下来但经过一个月的验证这种慢反而值得。2. 解题套路拆解三类高频题型的思考模型专题刷题最关键的是建立起见到题目先归位的能力。看到一道题第一反应应该是这题属于哪个题型用哪种套路。下面把三个专题的思考模型逐个拆开都是这一期里反复用并且验证过的。2.1 二叉树问题递归三板斧与迭代控制几乎所有的二叉树题目都能套用同一套递归框架。我把这个框架总结成三个问题。第一个问题递归的结束条件是什么对二叉树来说通常就是当前节点为空节点时返回。我写递归时习惯先把这一行写上防止写深了之后忘记处理边界。第二个问题需要对左子树和右子树分别做什么操作第三个问题拿到子树返回的结果后如何合并成当前节点的答案以求最大深度的题目为例结束条件是空节点返回0左子树和右子树分别递归求出深度合并结果是取两者较大值再加1这个加1代表当前节点自己占的那一层。这就是二叉树递归题的完整思考过程。它看起来很简单但大量树的问题都能用这条路想通。迭代写法就没那么统一了核心是用显式栈代替系统的调用栈。前序、中序、后序三种遍历各有固定的压栈顺序层序则需要用到队列。我个人的建议是在力扣环境下想快速通过就用递归想锻炼控制能力再尝试迭代。递归能解决的题迭代基本也都能解但代码复杂度会明显上升笔试场景下没必要和自己较劲。2.2 双指针问题左右指针与快慢指针的分工双指针这个叫法虽然简单实际包含两个完全不同的子类型。左右指针最常出现在数组排序后找组合的场景比如三数之和、两数之和变体、盛最多水的容器。这类题的前提通常是数组有序两个指针分别指向头部和尾部根据当前元素和与目标值的大小关系移动其中一个指针把枚举复杂度降一个维度。这个过程的核心是每次移动指针都必须能说明它不会漏掉正确答案否则就不是优化而是碰运气。快慢指针则是链表题目的常用大招。环形链表检测、寻找链表中点、寻找倒数第K个节点都能用一快一慢两个指针完成。背后的思路其实是路程差快指针每次走两步慢指针每次走一步在一个有限的环上两者终会相遇。我第一次见到这个解法时觉得非常巧妙但它的出发点只是一个朴素直觉——速度不同在闭环里快的肯定会追上慢的。判断一道题该用左右指针还是快慢指针一般看数据结构就行数组题目基本是左右指针链表题目基本是快慢指针。当然也有例外比如反转字符串这类数组题用的就完全是左右指针的思路。2.3 滑动窗口问题窗口合法性的维护套路滑动窗口题的模板比二叉树递归还要固定。核心是一个左边界和一个右边界右边界不停向右扩展把新字符或新数字纳入窗口一旦窗口不再满足题目要求就移动左边界缩小窗口直到恢复合法。这样右边界走完整个数组每个元素最多被进出窗口各一次整体时间复杂度是O(n)。这里最关键的是想清楚合法状态是什么以及用什么样的数据结构来记录。最长无重复字符子串题记录的是当前窗口内出现过的字符用Set就够覆盖类题目需要统计每个字符出现的次数得用字典。很多人写滑动窗口容易写进死循环我的经验是右边界加入窗口后马上判断合法性合法就更新答案不合法就收缩。收缩完之后不需要重新判断合法性因为收缩结束的位置恰好是合法状态直接继续右移就行。这三个模型互相配合基本能覆盖这一阶段遇到的大部分中等难度题目。下面进入实操环节记录这期里四道给我留下最深印象的题目。3. 四道典型题的完整实操记录这期刷了大概三十道题我挑四道比较有代表性的把做题时的思考过程、最终写法、AC之后还做了什么都写出来。每道题都有可以复用的点不是AC了就算结束。3.1 反转链表迭代5分钟递归看成外包反转链表是链表入门第一题我前两期一度写不顺原因是递归版本始终想不清楚凭什么这样就反转了。迭代版本的思路其实很直接遍历链表时把当前节点的next指针指向前一个节点。但这里有一个特别容易忽视的细节如果先改curr.next后面就找不到原本的下一个节点了。所以固定的三步顺序是先保存nxt curr.next再执行curr.next prev最后移动prev和curr。这个顺序我写错过三次后来总结成一句口诀先存后改再移。递归版本的思考角度完全不同。不要把它理解成在同一个函数里反复调用而是想成我把后面的链表交给另一个函数去反转它返回一个反转后的头节点。此时当前节点只需要做两件事让后面那个节点的next指向自己再把自己的next置空。这本质上就是把重活外包出去至于为什么能反转的细节在递归层层展开的时候自然成立。def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_headAC之后我做了两件事。第一是拿三个节点的链表在纸上把递归展开画一遍把每个状态标清楚这一画之后再遇到树的递归题心里就踏实很多。第二是拿空链表、单节点链表、两个节点链表三组边界用例把迭代版和递归版都跑一遍三个用例过了这题才算真稳。3.2 二叉树最大深度DFS和BFS的取舍最大深度这道题是二叉树专题里练递归和层序都不错的一道。递归写法基本就是模板但需要理解为什么是左子树深度和右子树深度取较大值再加1。树的深度定义是从根到最远叶子节点的节点数因此对于任意一个节点它的深度等于左子树或右子树深度的较大值再加上当前节点占的1层。这个推理直接对应代码逻辑。def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))迭代层序版本也值得写一遍因为层序天然能数出第几层数到最后一层就是深度。层序用队列这个队列是核心每次处理完当前层的所有节点后深度加1直到队列为空。def maxDepth(root): if not root: return 0 from collections import deque queue deque([root]) depth 0 while queue: for _ in range(len(queue)): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth两个版本我都保留在笔记里。同一道题用多种解法去写最大的价值在于理解DFS和BFS的本质区别递归是深度优先一层下去摸到叶子再回来层序是广度优先一层一层从上往下清点。理解了这一点后面遇到求最短路径判断二叉树是否对称这类问题就能快速判断该往哪个方向思考。3.3 最长无重复字符子串窗口怎么收缩是重点这道题是滑动窗口专题最典型的一道。题目是给一串字符找到不含重复字符的最长子串的长度比如在abcabcbb中最长的是abc长度是3。我第一版写的是暴力解法枚举每个起点从起点往右扩展遇到重复就停统计长度。时间复杂度是O(n^2)短字符串上没问题字符串一长就明显卡住。滑动窗口版本的核心数据结构是一个Set保存当前窗口内的字符。右指针每走一步先检查当前字符是否在Set里如果在说明重复了那就不断从Set里删掉s[left]并且把left右移直到把重复字符清走如果不在直接加入Set此时窗口一定合法更新最长长度。代码很短。def lengthOfLongestSubstring(s): window set() left 0 ans 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left 1 window.add(ch) ans max(ans, right - left 1) return ans这里最容易踩的坑是为什么收缩完不用重新检查合法性。因为重复的来源只有刚加入的chleft不断右移其实就是把窗口里的字符逐个删掉直到ch在窗口里不再出现此时窗口一定重新合法。这个点一旦想通滑动窗口类的题目基本都能用同一套模板写这也是我建议把模板敲熟、而不是死记每道题答案的原因。3.4 三数之和排序去重的细腻边界三数之和是双指针专题里的一道硬题。题目要求找到所有三个数让它们的和为0而且结果里不能有重复的三元组。暴力三层循环肯定超时正解是先排序再上双指针。排序的意义在于数组有序之后固定第一个数剩下两个数就可以用左右指针去逼近目标值。左指针从固定数的右边开始右指针从数组末尾开始两数之和偏大就右指针左移偏小就左指针右移。固定数循环n-2次每次双指针扫一轮整体复杂度O(n^2)比暴力O(n^3)好太多。去重才是这道题真正考人的地方。固定数在进入每轮循环时如果和上一轮相等就跳过找到一组解后left和right也要跳过后面的重复值。三处去重少一处都会输出重复三元组。我第一次提交时漏了left和right的跳过结果输出里出现大量重复组合跑测试用例才发现问题。def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i-1]: continue left, right i 1, n - 1 target -nums[i] while left right: s nums[left] nums[right] if s target: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return res去重的底层逻辑是排序让相等的数相邻相邻重复就可以安全跳过因为同一个值只需要被考虑一次。遇到这类去重问题时最好都自己讲一遍这个逻辑能讲明白就说明这一块真的过关了。4. 从刷题到能力沉淀我的四遍法与复盘笔记第三期刷到一半我开始注意到一个事实很多题我做出来了但过了三天可能又做不出来。这并不代表笨只是记忆管理出了问题。刷题如果不能转化为长期记忆本质上就是在做体力劳动。后来我调整了方式逐渐形成了适合自己的四遍刷题法和复盘笔记法。4.1 四遍刷题法从抄题解到独立复现我的四遍法是这样的。第一遍先读题尝试思考15分钟。如果15分钟都没有完整思路就直接看题解。注意关键词是完整思路——不是看了题解觉得好像懂了就翻过去而是要把题解思路读透然后合上答案自己在代码编辑器里重新写一遍。这一遍是很多人缺的因为看题解会产生一种虚假的掌握感只有亲手敲出来才算第一次真正学会。第二遍隔一天再做一次。这一遍不看提交过的代码完全凭第一遍形成的思路去写。如果第二遍写得磕磕绊绊说明第一遍并没有真正消化需要退回第一遍重新来。我通常把这一步放在第二天的早上花十分钟完成目的不是刷数量是确认昨天真的记住了。第三遍换一个角度优化。比如第一遍用递归第三遍就试着用迭代第一遍复杂度是O(n^2)第三遍就想想有没有O(n)的做法。这一步不是为了炫技而是逼大脑从不同路径理解同一道题理解会立体得多。第四遍讲出来。找一个没做过这道题的朋友把题目讲给他听或者自己在笔记里写一篇完整的文字题解。凡是讲不清楚、写不明白的地方就是自己还没吃透的漏洞。四遍走完这道题才真正属于你。这套方法看起来慢实际过程中不需要反复重做效率反而高。4.2 复盘笔记记录什么才不算白刷我在笔记里存了三十多条刷题复盘每条格式都一样包含题目简化描述、首次通过用时、错误原因、核心套路总结。最容易忽略的两个维度是错误原因和复杂度分析。错误原因特别重要因为很多人做错是反复错在同一类细节上比如边界条件漏判、循环里指针的移动顺序写反。把这些错误原因分类统计才会发现自己的最大薄弱点在哪。复杂度分析也不能跳过每道题都写清楚解法的空间和时间开销才能逐步建立对算法优劣的判断力而不是AC了就觉得自己很强。还有一个我一直坚持的维度是同类题联系。每写完一题我会花几分钟想想这道题和本周做过的哪些题用了同一个套路然后写在这条笔记的末尾。刷题最怕做一道忘一道而这个小动作相当于每次都在给大脑做一次索引归档之后的复习效率提升非常明显。5. 刷题路上的常见问题与排查实录刷题过程中踩的坑很多时候比做题本身带来更多成长。这期梳理几个高频问题按现象、原因、处理办法的方式整理出来。5.1 递归栈溢出调高限制只是治标第三期在做递归专题时遇到过几次报错提示递归深度超限。Python的默认递归深度大约是一千层但有些链表的长度就能超过这个数。网上有建议把递归深度限制调高到一万这只能让程序暂时不报错并没有真正解决问题——数据再深一层照样崩。正确的思路是认清递归适用的场景。递归适合树的这类天然深度可控的结构树的深度通常不会离谱。而超长链表这种容易形成深链的结构必须优先考虑迭代写法。判断标准很简单看数据会不会形成一条很长的链。如果是果断写循环或者用显式栈。排查这类问题我有一套固定流程。第一步确认报错发生在哪个函数看递归路径是否比自己预想的长第二步构造一个最长的输入用例看实际递归深度是多少第三步判断这个深度在默认限制内是否安全不安全立刻换非递归实现。这套流程走过几次再遇到递归超限的报错就淡定了。5.2 边界条件漏判最小用例测试法刷题提交被判定解答错误十次有八次是边界条件。链表题的空链表、二叉树题的空树、数组题的空数组这些问题我在前两期里反复踩。后来我给自己定了一条规矩写完代码不管多自信都先把几个最小用例跑一遍。具体是空输入、只有一个元素的输入、只有两个元素的输入、所有元素值相同、输入顺序为反序。这五个用例是我从大量报错里总结出来的能覆盖绝大多数边界问题。背后有个通用思想叫最小化触发。很多bug不是逻辑整体错了而是代码里某个分支没有覆盖到特殊情况。最小用例测试法就是主动构造最小规模的特殊数据让边界分支的代码路径真正执行一次。虽然看起来是个土办法但排查效率比对着代码干看高得多。5.3 思路正确但代码总是有小毛病局部变量与循环结构还有一类问题很隐蔽解题思路完全正确但提交之后总是有小毛病或者运行耗时很高。我从这期实战里总结出两个主要原因。第一个原因是局部变量的作用域搞错。例如在循环里初始化了一个变量却希望循环结束后还能用结果每次循环都被重置最终答案自然不对。定位这类问题最快的方法是在关键位置打印日志观察这个变量的值在一个循环周期内是怎么变的。第二个原因是循环结构选错。典型的就是用for循环去手动改迭代变量这在Python里是不行的——for循环每次迭代会自动重新赋值迭代变量手动修改不会影响循环进度很容易造成逻辑错乱或者死循环。需要手动控制边界的时候直接使用while循环是更安全的选择。如果超出的是时间限制优先排查有没有重复计算。比如三层循环内层在做加法可以先预处理前缀和把暴力O(n^3)降下来。这类优化不会自己出现需要主动去挖。第三期以来遇到的高频问题整理成了一张速查表遇到同类问题可以直接照顺序排查。现象常见原因快速处理办法递归报错提示深度超限递归层数超过默认限制换成迭代或显式栈尤其针对长链结构解答错误且数据规模较小边界条件漏判空输入、单元素、双元素等最小用例逐个跑通输出结果包含重复项去重逻辑不完整排序后相邻相等跳过检查每一个循环层级提交通过但运行耗时高算法复杂度过高检查是否存在暴力循环用双指针或前缀和优化本地运行正常但提交出错未处理某些特殊输入对照题目约束检查每个分支是否有返回6. 环境配置与刷题节奏的经验谈这一期除了刷题本身我对刷题环境和节奏也做了不少调整。这两件事看起来和算法关系不大实际上对状态影响非常大。6.1 语言与环境Python的优与坑我用Python刷题原因很简单语法简洁、写起来快在力扣环境下运行速度对大多数题都够。但Python有几个需要提前避开的点不然会在低级问题上浪费很多时间。第一是引用类型的问题。new_list old_list这样赋值后两者共享同一片内存修改new_list会同步改到old_list。在需要复制数组的题目里必须用切片或者copy方法创建独立对象。这种问题在数组、列表类的题目里出现频率很高。第二个是collections模块值得提前熟悉。deque是双端队列处理滑动窗口和层序遍历基本是标配Counter做字符统计比手写字典方便非常多defaultdict可以省去一堆判空的代码。这四个东西deque、Counter、defaultdict、heapq是我刷题时使用频率最高的建议在正式刷题前先花半小时过一遍它们常用的API。还有一个小习惯是本地准备好统一的代码模板包括常见的import语句和输入输出辅助函数。虽然力扣已经处理了输入输出本地调试的时候还是需要一套顺手的脚手架可以减少在环境问题上反复折腾的时间。6.2 每天刷多少题以保留状态感为底线这里讲两个让我刷题节奏更可持续的小体会。第一个体会是每天刷题数量不重要重要的是保持住状态感。状态感的意思是打开编辑器看到一道不太难的中等题心里不慌知道自己大概率能一步一步做出来。这个状态感一旦超过三四天不碰题就会明显消退。所以我把刷题频率定成每天早上四十分钟做两道题。如果当天状态不好只吃透一道也没问题关键是每天见一面保持和算法题的熟悉感。这种细水长流比周末一口气刷八个小时的效果要好。休息日集中刷题第二天基本都会出现明显的大脑疲劳感而每天固定四十分钟反而更容易坚持。第二个体会是把做题和记录分开。做题的时候专注做题复盘的时候专注复盘。如果一边做题一边写笔记两个任务互相干扰做题容易敷衍笔记也记不细。我自己的流程是前面二十分钟做一道新题后面二十分钟做一道同类旧题并整理复盘。这个节奏稳定下来后整个第三期的产出效率明显提升。关于每周节奏我给自己定了这么一张表也贴出来做个参考。时间任务目标每天早上前20分钟做一道新题维持对新题型的识别能力每天早上后20分钟做一道同类旧题并整理复盘通过类比巩固套路周末其中一天回顾本周所有错题把一周的错误沉淀成经验每月最后一天复选一道经典难题口头讲解验证长期记忆和理解深度到这里第三期刷题记录的核心内容差不多写完了。最后分享一个这期收获最大的小技巧用讲题来验收学习效果。方法很简单每做完一道值得记录的题就打开手机录音假装自己在给一个刚开始学算法的朋友讲题讲清楚题目在问什么、用了什么套路、为什么这么写、复杂度是多少。讲的过程中一旦卡壳那个卡壳的位置就是自己还没理解透的地方回到题目里再琢磨。我这期录过好几段回放时发现了很多问题比如这里我为什么跳过不讲了这个复杂度其实我根本没算对。坚持这个习惯之后做题的稳定性提升明显因为讲题会强迫把模糊的知识点变成清清爽爽的语言表达。下期我计划把重心放在动态规划专项上连续刷两周再整理成新一期记录。
