刷到第73天算法刷题这件事已经从最初的新鲜劲儿变成了一种固定的生活节奏。这一天我没有继续按题库顺序往前推而是把前面72天里反复出错的几类题目重新捞出来做了一次专题式的集中处理。说白了算法刷题到中段最容易遇到的瓶颈不是题不会做而是做过的题换个包装就不认识了。所以Day 73的核心任务就一句话把散落的题型收拢成几条主线弄清楚每类问题背后的算法骨架到底长什么样。这篇记录适合两类人看一类是刚起步、还在被边界条件折磨的新手另一类是做了一段时间、想从刷数量切换到刷质量的朋友。下面我把当天的完整思路、代码实现和踩坑过程都摊开讲。1. 刷到第七十三天我把策略从堆数量改成了啃专题1.1 前72天暴露出来的真实问题前两个多月我基本是每日三题的节奏题库里带标签的简单题和中档题混着做做完记个笔记就算过。前三十天效果很明显看到数组、字符串、链表这类题脑子里能快速调出对应套路。但到了第五十天往后问题开始冒头新题目的通过率没怎么涨反而在同一个知识点的不同变体上反复栽跟头。最典型的一次我连续三天做了三道看起来完全不同的题事后复盘才发现全是滑动窗口的变体只是题目把数组换成了字符串、把求和换成了计数我就没认出来。这件事让我意识到按题目编号顺序刷本质上是在做广度扫描它能把知识点覆盖面拉宽但很难把单个知识点砸深。知识点之间的连接是断的脑子里存的是一道道孤立的题而不是一张网。算法刷题的价值恰恰在于这张网——你看到一个问题能瞬间判断它属于哪一类、该用哪套工具、复杂度大概在什么量级。孤立地记题网就织不起来。1.2 Day 73 的调整方案三条主线加一套复盘模板想清楚问题之后我给Day 73定了三条主线每一条都对应一个我反复出错的领域查找与边界、字符串匹配、排序与图论基础。这三块看起来跨度大其实有个共同点——它们的核心都不是想到解法而是写对代码。二分查找的思路谁都会但十个人写有八个死在边界上KMP的next数组原理看视频能懂自己手推就懵Prim算法和最短路径算法一到实现就分不清该维护哪个数组。这类问题的共同特征是思路占三成实现细节占七成。所以我当天的训练方式也换了。每道题先不写代码用五分钟在纸上把算法骨架和边界条件写清楚再上机实现。写完不急着提交先自己造三组测试数据一组常规数据、一组边界数据空、单元素、全相同、一组随机数据。只有三组都过了才提交。这套流程看起来慢但它把调试时间提前到了设计时间实际算下来总耗时反而更短。我后面几节的复盘模板也是围绕这个逻辑展开的你可以直接拿去用。2. 二分查找看着最简单边界最容易翻车2.1 为什么二分总是死在死循环和漏解上二分的坑几乎全部来自区间定义不统一。很多人在写的时候脑子里一会儿是左闭右闭、一会儿是左闭右开while的条件、mid的更新、返回值的处理就全乱了。死循环的经典成因是lo mid配hi mid当区间只剩两个元素时mid永远等于lo区间不再收缩程序就卡住了。漏解则通常出现在返回lo还是hi的选择上尤其是要找第一个大于等于目标值的位置这种变体时随手返回mid基本必错。我的解决办法是固定一套模板只记一种区间语义绝不中途换。我选的是左闭右开区间[lo, hi)理由是它和大多数语言里数组切片、range的语义一致脑子里不用做额外转换。这套模板能覆盖绝大多数二分变体找目标值、找左边界、找右边界只是比较条件的不同。固定语义之后写的时候只需要关注我要的是哪个边界剩下的都是模板。2.2 一套可以直接背下来的模板和它的推导先看最基础的左边界查找也就是找到第一个大于等于target的下标def lower_bound(nums, target): lo, hi 0, len(nums) # 区间 [lo, hi) while lo hi: mid lo (hi - lo) // 2 if nums[mid] target: lo mid 1 # mid 及其左侧全部排除 else: hi mid # mid 可能是答案保留在区间内 return lo # lo hi就是第一个 target 的位置这段代码有三个细节值得单独说。第一mid lo (hi - lo) // 2而不是(lo hi) // 2是为了避免加法溢出虽然Python不会溢出但在C里这是必须养成的习惯两个int相加超过上限会直接变成负数导致下标越界。第二hi mid而不是hi mid - 1因为我们的区间是左闭右开mid本身还没被验证过不能直接排除。第三循环结束时lo hi这个位置就是答案不需要额外判断。理解了这套之后右边界查找只是在比较条件上做个镜像找最后一个小于等于target的位置判断条件改成nums[mid] target就往前推。我当天用这套模板一口气过了四道变体题包括在一堆重复元素里找左右边界、在旋转数组里找最小值、以及在一个先增后减的数组里找峰值。每道题的代码结构几乎一样改的只是那两三行判断。2.3 二分不能只用在有序数组上大多数教材讲二分都从有序数组找元素入手容易让人误以为二分的前提是数组有序。实际上二分的本质是单调性判断——只要你能在O(1)时间内判断答案在mid左边还是右边就能二分。所以二分的适用场景比想象中广得多求平方根的整数部分、求一个单调函数的最小可行解、在答案范围上做二分搜索比如最小的船载重量这类题都是二分的舞台。当天我练的一道答案二分题就很典型给一堆货物重量和天数求船的最小载重。这道题没有数组可以用但它满足单调性——载重越大需要的天数越少。于是我在载重的取值范围内二分每次用一个贪心函数判断这个载重能不能在天数内运完。这就是二分的通用形态值得单独记一笔。注意二分题目里凡是出现最小第一个至少这类字眼先停下来想想能不能在答案上二分别急着上动态规划。3. 字符串匹配与KMPnext数组到底在算什么3.1 从暴力匹配到KMP省下来的到底是什么暴力匹配的做法是从主串的每一位开始逐字符和模式串比对一旦失配就把主串指针回退到起始位置的下一位。最坏情况下主串长度n、模式串长度m复杂度是O(n×m)。它浪费的地方在于失配的那一刻其实已经知道前面一段文字长什么样了这部分信息完全可以复用但暴力做法把它丢弃了。KMP的核心贡献就是把这段信息用起来。它在模式串上预先算出一个数组有人叫next有人叫前缀函数记录每个位置失配时应该回退到哪里。这样一来主串的指针永远不回退一路向前整体复杂度降到O(nm)。理解KMP的关键不在代码而在于想通一件事模式串的前缀和后缀如果有重叠部分那这段重叠就是可以复用的。举个生活化的例子。假设你在核对一串编号模式串是ABABC。当匹配到第五位发现不对时暴力做法是回到开头重新来但KMP注意到模式串开头两位AB和倒数两位AB是一样的说明已经匹配上的那部分里尾部有两个字符可以作为新的开头回退到第三位继续比对就行前两个字符不用重新比。3.2 手推next数组的完整过程next数组前缀函数的定义是next[i]表示子串p[0..i]的最长相等前后缀的长度。手推一次比看十遍讲解管用我当天是这么推的以模式串ABABC为例下标 i子串最长相等前后缀next[i]0A无01AB无02ABAA13ABABAB24ABABC无0推完这张表代码其实就浮出水面了。递推的逻辑是如果p[i] p[j]那么next[i] j 1两个指针一起前进如果不相等就沿着next[j-1]往回跳直到找到能匹配的位置或者跳到起点。代码长这样def build_next(p): n len(p) nxt [0] * n j 0 # j 表示当前匹配到的前缀长度 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] # 失配则回退到上一个可能位置 if p[i] p[j]: j 1 nxt[i] j return nxt这里面最容易写错的是j nxt[j - 1]这个回退。注意是nxt[j-1]而不是nxt[j]因为nxt[j]还没计算出来而j-1位置的最长前后缀已经确定了。当天我在这里卡了差不多二十分钟跑出来的结果是错的就是栽在这个下标上。提示KMP的匹配部分和建表部分结构几乎一样如果建表写对了匹配就是把p[i] ! p[j]换成text[i] ! p[j]主串指针一直往前走。4. 排序家族堆排序、归并排序在刷题里的真实用途4.1 归并排序远不止是排序很多人学归并排序就是背个分治模板觉得实战里用不上——毕竟调个库函数就排完了谁还手写。但归并排序的真正价值在于它中途合并两个有序数组的那一步很多题目就是围绕这一步设计的。最经典的就是逆序对统计在合并两个有序数组的过程中如果右半边的元素比左半边的小那么左半边从当前位置到末尾的所有元素都和它构成逆序对可以一次性统计出来不需要额外循环。当天我把这个模板重新默写了一遍重点是统计逆序对的那一行def merge_sort(nums, lo, hi, tmp): if hi - lo 1: return 0 mid (lo hi) // 2 cnt merge_sort(nums, lo, mid, tmp) merge_sort(nums, mid, hi, tmp) i, j, k lo, mid, lo while i mid and j hi: if nums[i] nums[j]: tmp[k] nums[i]; i 1 else: tmp[k] nums[j]; j 1 cnt mid - i # 左半剩余元素都与 nums[j] 构成逆序对 k 1 tmp[k:hi] nums[i:mid] or nums[j:hi] nums[lo:hi] tmp[lo:hi] return cnt关键就是cnt mid - i这一句。它的含义是当nums[j]比nums[i]小时左半边从i到mid-1的所有元素都大于nums[j]且它们原本都在nums[j]前面所以全都构成逆序对一次加完。这个技巧省掉了O(n²)的两两比较把逆序对问题降到O(n log n)。归并排序还能用在链表排序上因为链表没法随机访问快排的partition不好写而归并只需要合并两个有序链表天然合适。4.2 堆排序与优先队列TopK和贪心的好搭档堆在刷题里的出场频率比很多人想的高。求第K大元素、合并K个有序链表、滑动窗口最大值、以及各种每次取最小的那个的贪心题背后都是堆。堆排序本身的思路很直白先建堆然后反复把堆顶最大值或最小值和末尾交换再调整堆。手写堆排序的人不多但理解堆顶永远是最值这个性质对用优先队列解题至关重要。我当天顺手把冒泡排序用C又写了一遍作为热身虽然它O(n²)的复杂度实战基本不用但它的提前退出优化是个很好的思维练习void bubbleSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 本轮无交换说明已经有序 } }当天的排序专题让我重新梳理了一张表把常见排序的适用场景对齐算法平均复杂度稳定性典型刷题场景归并排序O(n log n)稳定逆序对、链表排序、外部排序堆排序/优先队列O(n log n)不稳定TopK、合并K路、贪心取最值快速排序O(n log n)不稳定通用排序、第K大partition计数/桶排序O(nk)稳定值域小的整数排序5. 贪心与剪枝跳跃游戏2和搜索题的取舍5.1 跳跃游戏2的贪心边界推导跳跃游戏2是贪心的经典题给定一个非负整数数组每个元素表示从该位置最远能跳的步数求跳到末尾的最少步数。很多人第一反应是动态规划但贪心有更优的O(n)解法。核心洞察是在每一步能覆盖的范围内我们不需要逐个尝试跳到哪里只需要记录这一跳能到达的最远位置等走到当前覆盖范围的边界时步数加一再更新边界。这个在边界处才更新的细节是解题的关键也是最容易写错的地方。如果每走一步就更新边界就会多算步数。当天我推导的时候在草稿纸上画了个例子数组[2,3,1,1,4]从下标0出发最远到2这个范围内能到达的最远位置是下标1加3等于4也就是末尾所以两跳足够。代码实现如下def jump(nums): n len(nums) if n 1: return 0 cur_end 0 # 当前这一跳能到达的边界 farthest 0 # 下一跳能到达的最远位置 steps 0 for i in range(n - 1): # 注意不遍历最后一个位置 farthest max(farthest, i nums[i]) if i cur_end: # 走到边界才结算 steps 1 cur_end farthest if cur_end n - 1: break return steps有个细节值得强调循环只到n-2不遍历最后一个元素。因为在最后一个位置再跳一次没有意义反而会多算一步。这个小坑我当天第一次提交就踩了答案比预期大1。5.2 剪枝的三个判断层次搜索类题目回溯、DFS不剪枝的话指数级复杂度能瞬间爆掉时间限制。剪枝的思路是在进入下一层递归之前先判断这个分支有没有可能产生有效解没可能就直接跳过。我把它分成三个层次来记第一层是可行性剪枝当前状态已经违反题目约束比如和超过目标、访问过重复元素直接return第二层是最优性剪枝已经找到一个解并且当前分支不可能比它更优可以砍掉第三层是排序加去重剪枝先把候选数据排序让相同元素相邻再通过同一层跳过重复元素避免生成重复解。第三层是最容易被忽略、但对组合类问题收益最大的。比如求所有不重复子集如果不排序去重会生成大量重复答案再去重白白浪费时间。排序之后只需要在循环里判断当前元素和前一个元素相同且前一个元素在本层没被使用就跳过能直接把搜索树砍掉一大半。当天我在一道组合总和题上实测加了这个剪枝之后递归调用次数从一万多次降到几百次效果非常直观。注意剪枝的前提是搜索顺序确定。同一层去重和同一路径去重是两回事写的时候一定用visited数组或索引控制好层的边界否则会漏解。6. 图论基础Prim算法与最短路径的适用边界6.1 最小生成树和最短路径别搞混图论入门最容易混淆的一对概念是最小生成树和最短路径。最小生成树要求把图中所有顶点连通且边权总和最小典型算法是Prim和Kruskal最短路径求的是两个点之间的最短距离典型算法是Dijkstra、Bellman-Ford、Floyd。两者解决的问题完全不同——前者是连通全网的最低成本后者是从A到B怎么走最近。我当天专门把这两个问题放在一起对比因为它们看起来都是求最小但目标函数根本不一样。判断方法很简单如果题目要求连接所有城市铺设最少长度的道路使全图连通那是最小生成树如果问从起点到终点的最短距离最少花费到达某点那是最短路径。这个判断一旦建立选算法就不会错。另外最小生成树对负权边是允许的只要有边权就能建树而Dijkstra不允许负权边这是另一个区分点。6.2 Prim算法的实现细节与复杂度Prim的思路是贪心从一个起点开始每次把距离当前生成树最近的外部顶点拉进来直到所有顶点都被拉进来。用优先队列优化后复杂度是O(E log V)。实现的关键是维护visited数组和距离数组每次从堆里取出距离最小的未访问顶点。代码大致是这样import heapq def prim(graph, n): visited [False] * n heap [(0, 0)] # (边权, 顶点) total 0 used 0 while heap and used n: w, u heapq.heappop(heap) if visited[u]: # 懒删除跳过已访问顶点 continue visited[u] True total w used 1 for v, wt in graph[u]: if not visited[v]: heapq.heappush(heap, (wt, v)) return total if used n else -1这里有个技巧叫懒删除允许堆里存在同一个顶点的多条记录因为每次有更短边就连进去出堆时如果发现该顶点已访问就直接跳过。这样做省去了手动更新堆内元素的麻烦代码更简洁。代价是堆可能变大但复杂度仍然是O(E log E)可以接受。当天我在测试的时候故意加了一条零权边结果正常说明零权边不会影响已访问判断因为它只影响入堆的权重不影响的去重逻辑。7. 常见问题与排查技巧实录7.1 我整理的一份调试速查表刷题卡壳的时候最怕的是没有方向地乱改代码。我当天整理了一张速查表出问题先对照基本能定位到八成的情况现象高概率原因排查动作死循环区间不收缩检查while条件与指针更新是否配对答案差1边界包含关系打印首尾元素确认区间是闭还是开数组越界mid1方向错误手动代入n1和n2推一遍结果超时缺少剪枝或重复计算加备忘录降一层循环逆序对偏大重复计数检查等号和含义不同图论结果不对算法选错先判断是最小生成树还是最短路径这张表我贴在显示器边上出问题先扫一眼比盲目print快得多。尤其是答案差1和数组越界这两行几乎覆盖了我当天所有卡住的场景。7.2 三个我反复用到的排查套路第一个套路是最小规模代入。任何边界相关的bug都先构造规模为1或2的输入手动跑一遍。二分、双指针、区间类题目里规模为2时最容易暴露区间不收缩的问题。这个动作花不了一分钟但能省下大把调试时间。第二个套路是对照花时间最多的那一步。如果一道题写了很久不要急着优化整体先问自己哪一步写得最犹豫。犹豫的地方通常就是理解不透的地方那里极可能藏着错误。当天我在KMP的nxt[j-1]上犹豫果然就是它错了。第三个套路是换个数据规模验证复杂度。道理都对但不通过多半是复杂度爆了。这时候把数据规模翻十倍跑一遍如果时间明显超线性增长就回头找重复计算加缓存或者换算法。这个方法对动态规划和搜索题特别有效。实操心得调试时不要一次性改好几处代码。每改一处就重跑一次确认这处改动带来了什么变化否则最后你会不知道到底是哪处改动生效了。8. 复盘模板与长期节奏的维护8.1 一份能坚持下来的错题复盘模板刷题最怕的是做了等于没做。我前72天用了不少时间在记笔记上但很多笔记只是把题解抄了一遍回头再看毫无价值。Day 73我换了个模板只记四样东西这道题属于什么类型、我卡在哪一步、关键的那一行代码是什么、下次遇到同类题的第一反应是什么。四样都控制在一两句话内逼自己提炼而不是抄写。这个模板的好处是复习成本极低。一道题只留四行字一个专题几十道题也就几页睡前扫一遍不费劲。相比之下整篇题解的笔记我基本不会再翻第二次因为信息量太大复习的启动成本太高。当天我把前两个月的题翻出来用这个模板重新压缩了一遍原本几十页的笔记缩成了不到十页清爽了很多。8.2 专题训练的节奏怎么安排最后说说节奏。连续73天每天三题听起来很猛但我在第六十天左右明显感觉到效率在下降——疲劳状态下做题错误率高复盘质量也差。所以从Day 73开始我把每日三题改成了隔天专题一练加每日一题保手感。专题日集中攻一个方向做五六道同类型题把这类题的边界、模板、变体一次性吃透非专题日做一道综合题维持手感和状态。这个调整的底层逻辑是刷题的目的是把知识点连成网而不是把日历填满。数量堆积到一定程度后边际收益会迅速下降这时候把时间花在把一个点砸深上回报要高得多。我自己实测下来专题日的五道题带来的收获比之前零散做十五道题还多。当然这只是我的节奏你可以根据自己每天可支配的时间和当前的基础调整核心原则不变宁可一天吃透一类不要一天扫过一堆。在具体执行上我还会给每个专题设一个退出条件比如二分专题的退出条件是不看模板手写左边界和右边界查找各三道题一次通过。达到条件就换下一个专题达不到就再来一天。这个条件比做够多少题更靠谱因为它检验的是能力而不是数量。控件式的目标容易自我欺骗能力式的目标不会。