今天是我刷 LeetCode 面试经典150 的第59天日历正好翻到1月11日。说句实话这个节点比想象中微妙——150 题已经刷过一大半前面数组、链表、双指针带来的一马平川的爽感正在退潮后面等着的栈、二分、图这类题目全是那种想不明白一个骨架就根本没法动笔的硬骨头。今天这道打卡题单特别典型994 腐烂的橘子、224 基本计算器、875 爱吃香蕉的狒狒。三个题目分属 BFS、栈、二分答案三个完全不同的板块但晚上复盘时我发现它们本质上都在教同一件事把暴力循环里最慢的那一层用某种既定的搜索模式或数据结构替换掉。这篇文章我就拿 Day59 的真实经历来聊聊后半程刷题到底难在哪、这几道经典题目的完整思路和坑、以及我在周赛430之后对刷题方法的一次重新梳理。如果你也在刷面试经典150 或者热门100题这篇应该能帮你少走不少弯路。1. 第59天刷到哪了150题计划已经走进后半程的硬骨头区1.1 我的打卡表格和一个不算好看的进度我从 Day1 起就建了一个本地表格列是日期、题号、题名、所属分类、是否一次 AC、卡点一句话、是否需要二刷。每天睡前花五分钟填掉周末再花半小时把本周的卡点汇总成一张错题单。这个习惯听起来很笨但走到第59天的时候它的价值开始显现——我翻一翻 11 月、12 月的记录就能知道哪些分类是我反复踩坑的哪些分类已经稳定一次过。按我自己的节奏工作日一般刷 1 到 2 题周末状态好能到 3 到 4 题加上偶尔补一补周赛题59 天下来大概推进到 105 题附近占 150 题的七成左右。说实话这个进度不算快更算不上漂亮。很多刷题博主 Day30 就已经把 150 题过完一遍了但我自己的感受是前五十题求快后五十题求稳硬闯过去不等于你会做。特别是走到今天这个位置一天能稳稳吃透三道题比一天扫完十道题然后全部遗忘有用得多。1.2 后半程和前半程的分水岭面试经典150的前半段铺开的是数组、字符串、双指针、哈希表这些看到题目就知道大概要干嘛的题型。你写不出来往往只是语法不熟或者边界考虑不全很少会出现完全没有思路的绝望感。但到了后半程题型变成了二分查找、栈与表达式、图论 BFS/DFS、拓扑排序、回溯、字典树、堆等等。它们的共同点是暴力解法的复杂度一眼望过去就是错的你必须先找到正确的算法骨架再谈代码实现。我在 Day59 这天挑的三道题就很有代表性。腐烂的橘子考的是多源 BFS基本计算器考的是栈的现场保存与恢复爱吃香蕉的狒狒考的是二分答案的谓词设计。三个题放在一天刷一开始会觉得脑子要切换三次很累但你真把它们放在一起复盘反而会发现它们共享一套方法论暴力解法慢在哪哪种既定骨架正好能补上这个慢。1.3 刷题指南里的忠告一份清单刷到底最近在社区里经常看到有人在热门100题和面试经典150之间反复横跳今天刷 150 明天刷 100。我的建议是如果你时间够就认准 150 这一份刷到底如果时间很紧那就认认真真把热门100题啃透。两份清单本身有大量重叠题但它们的排序逻辑和覆盖范围不完全一致来回切换的最大坏处是打乱你的难度曲线和复习节奏。刷题指南里讲得最多的一致性比选哪份清单更重要。Day59 这个节点其实恰恰是最容易想换清单的时候后半程的题目变难AC 率下降人会自动怀疑是不是这份清单不适合自己。别急着换把今天这三道题的骨架吃住比换十份清单都有用。2. 腐烂的橘子994把分钟数翻译成BFS的层数2.1 为什么这题只能BFS不能DFS994 的题干大家应该都熟了一个 grid 里0 是空位1 是好橘子2 是烂橘子。每分钟烂橘子会向上下左右四个方向传染一格问最少多少分钟能让所有好橘子都变烂如果做不到就返回 -1。很多第一次做这题的人第一反应是 DFS从每个烂橘子出发往四个方向深搜然后用一个时间数组记录最早被传染的时刻。理论上这也能做但非常容易错。因为这个问题的核心特征是同时扩散——所有烂橘子在同一分钟一起传染不是一个烂橘子把一条路径走完再去管下一个。DFS 天然是深度优先的串行遍历和你想要的逐层同步推进语义不匹配。所以这题的正解是多源 BFS。多源的意思是初始队列里不是只放一个起点而是把当前所有烂橘子全部放进去。BFS 天然按层推进每一层就是一分钟这正好和题目的时间模型一一对应。把这个映射关系想清楚代码就成功了一半。2.2 多源BFS的代码骨架我直接贴出我最终的 AC 代码这个结构在后面很多扩散类题目里都能复用from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) q deque() fresh 0 for i in range(m): for j in range(n): if grid[i][j] 2: q.append((i, j)) elif grid[i][j] 1: fresh 1 # 如果没有好橘子0分钟就结束不需要额外处理 if fresh 0: return 0 minutes 0 dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] # 关键是 fresh 0 这个条件队列空了但还有好橘子就说明无法感染完 while q and fresh 0: minutes 1 size len(q) for _ in range(size): x, y q.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 2 fresh - 1 q.append((nx, ny)) return minutes if fresh 0 else -1这段代码有几个值得注意的点。第一进入 BFS 前先数好 fresh 的数量初始化为 0 的格子数量只在最后判断用不需要真的去模拟腐烂过程。第二我用while q and fresh 0而不是while q这样好橘子数量归零后就不会再多走一层空循环时间计算不会多出多余的一分钟。第三每层用一个size len(q)固定住本层节点数内层 for 只处理这一层BFS 的层数才会准确对应分钟数。2.3 我踩过的三个坑和完整排查过程这题我一开始写的版本错在了非常 stupid 的地方。第一次提交用的是while q每次循环先把minutes 1再处理一层。结果遇到 grid 全是你好橘子、周围没有烂橘子的情况队列不会空好橘子又永远减不到 0最后直接死循环。后来我在循环条件里加上fresh 0才解决。第二个坑是漏掉fresh 0的提前返回。如果不加这个判断一个全是空位或全是烂橘子的 gridBFS 进去走一圈,minutes 会被莫名其妙地加 1本来答案是 0 却输出 1。这是我调得最久的一次因为光看个别测试用例根本看不出来最后是把所有 corner case 列出来逐个跑才发现。第三个坑是忘了在入队时把grid[nx][ny]改成 2。如果只改 fresh 计数而不改 grid同一个橘子可能被多个方向的邻居重复入队fresh 计数会变成负数结果完全错乱。排查方法也很简单在入队前打印一下当前坐标和对应的 grid 值立刻就能发现重复入队的问题。提示BFS 里入队即标记是一个铁律。如果你在出队时才标记已访问同一层内可能有多个节点把同一个邻居加进队列导致数据错乱。严谨一点说应该是入队时标记不是出队时标记。2.4 延伸到其他多源扩散类题做透 994 之后再去看 542 零1矩阵、1162 地图分析这类题你会发现代码骨架几乎一模一样只是 BFS 里维护的不再是分钟数而是距离数组。我在 Day59 当天顺手把 542 的题解翻出来对了一下确认了多源 BFS 的通用性。以后凡是看到多个起点同时向外扩散求最早到达时间/最短距离这类描述第一反应就应该是多源 BFS。3. 基本计算器224一个符号栈把括号、负号和无空格全收拾干净3.1 题目考的是现场恢复224 基本计算器是面试里非常高频的一道栈题。表达式只包含数字、加号、减号、括号和空格要求按标准优先级计算。别看它只有加减法括号套括号、负号紧贴左括号、字符串里还混着空格这些细节凑在一起足够让初学者卡上半天。这道题最核心的洞察是既然只有加号和减号那每个数字前面都可以被看作带一个符号。加号表示 1减号表示 -1所有括号里的内容本质上就是一个带了外部符号的子表达式。我们不需要真正维护两个运算符栈只需要一个栈去保存进入括号之前的状态也就是所谓现场。用生活化的话说你是一个会计面前摆着一列待结算的数字。平时你从左往右算遇到加号减号就决定下一个数字该加还是该减。一旦碰到左括号相当于你要先去处理一张子账单这时候你得把当前的总账先压箱底等子账单算完再把它翻出来合到一起。右括号就是子账单的封口封口时要把箱底的总账和当时的正负符号取出来合并。3.2 单栈方案代码与手算轨迹我的 AC 代码长这样class Solution: def calculate(self, s: str) - int: stack [] result 0 sign 1 i, n 0, len(s) while i n: c s[i] if c.isdigit(): num 0 while i n and s[i].isdigit(): num num * 10 (ord(s[i]) - ord(0)) i 1 result sign * num continue elif c : sign 1 elif c -: sign -1 elif c (: # 保存进入括号前的累计结果进入括号前的符号 stack.append((result, sign)) # 括号内部是全新的算式结果归零符号归正 result 0 sign 1 elif c ): prev_result, prev_sign stack.pop() result prev_result prev_sign * result i 1 return result用一个具体例子手算一遍你就能完全看懂它为什么对。拿2-4-(8910)来说遇2result 2遇-sign -1遇4result 2 (-1)*4 -2遇-sign -1遇(把(result-2, sign-1)压栈然后 result 0sign 1括号内依次算8910result 变成 27遇)弹出prev_result-2, prev_sign-1result -2 (-1)*27 -29。整个式子2-4-(8910)手算也是 -29完全对得上。3.3 卡了我三个小时的负号排查过程复原我当天在这道题上浪费了三个小时最后发现全栽在一个细节上括号前是减号时括号里的正负号该怎么处理。比如1 - ( -2 )答案是 3。我第一次写的时候遇左括号只把 result 压栈没压 sign导致括号内的负数被按正数处理算出来变成 -1怎么想都不对。排查过程是这样的我拿1-( -2)逐行打印 result 和 sign发现进入括号后 sign 被重置为 1括号里的 -2 变成了 -2 本身的效果但其实括号外还有一个-号等着乘进去。也就是说括号内的 -2 乘上括号前的负号应该是 2最终 1 2 3。问题就出在我没有保存括号前的那个负号。修复方法也很简单把压栈信息从只压 result改成压 (result, sign) 元组右括号时用prev_result prev_sign * result合并。这个操作的本质是把括号内部的局部结果乘以括号外的整体符号再加回括号外已经算好的部分。另一个让我栽跟头的点是空格。题目里空格可能出现在任何位置比如 1 1 或者(1(452)-3)(68)。如果你用c 判断前不跳过空格程序会把空格当作未知字符直接跳过还好问题不大但如果你在空格处直接 break 或者 index 没处理好就容易漏读数字。我的做法是在 while 主循环里遇到非数字字符且非运算符时直接i 1空格天然被跳过不用额外判空。3.4 什么时候要用双栈或逆波兰刷到后面你会发现很多人讲基本计算器会用双栈法一个栈存数字一个栈存运算符遇右括号弹运算。那为什么我推荐单栈法因为 224 里只有加减法和括号没有乘除法没有优先级比较用单栈法最简洁。一旦题目升级成 227 基本计算器 II引入了乘除法优先级那就必须用带优先级的运算符栈或者把中缀转成后缀再求值。我的建议是先用单栈法把 224 吃透理解保存现场、恢复现场这个思想再去看 227 的优先级处理你会更容易明白双栈到底在干什么。4. 爱吃香蕉的狒狒875与二分答案边界比模板重要4.1 为什么每小时吃几根可以二分875 是一道很经典的二分答案题。Koko 每小时只能选一堆香蕉开吃吃多少由速度 k 决定如果某一堆剩余数量小于 k她这个小时也只吃这一堆剩下的时间不能去开下一堆。给定堆数组 piles 和总时间 h求能吃完所有香蕉的最小速度 k。这题的关键是发现一个单调性k 越大吃完所有香蕉所需的总小时数越少或不变k 越小所需小时数越多。所以我们可以把问题转化成找一个最小的 k使得f(k) h其中 f(k) 表示以速度 k 吃完所有香蕉需要的小时数。这是典型的二分答案——不是直接去搜答案对应的下标或位置而是先猜一个答案再验证这个答案是否可行。举个例子piles [3, 6, 7, 11]h 8。当 k 4 时每堆耗时分别是 ceil(3/4)1、ceil(6/4)2、ceil(7/4)2、ceil(11/4)3合计 8 小时刚好满足当 k 3 时合计 123410 小时超时。所以答案应该是 4。4.2 feasible 函数和整数除法的精度陷阱二分答案的核心是 feasible 函数也就是给定 k能不能在 h 小时内吃完。它的写法如下class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: def feasible(k): hours 0 for pile in piles: hours (pile k - 1) // k return hours h lo, hi 1, max(piles) while lo hi: mid (lo hi) // 2 if feasible(mid): hi mid else: lo mid 1 return lo这里最容易踩的坑就是ceil(pile / k)。千万不要在代码里写math.ceil(pile / k)因为浮点数除法在大数场景下可能因为精度误差导致结果差 1。正确姿势是一行整数运算(pile k - 1) // k。这个式子怎么理解给 pile 加上 k-1 再整除 k等价于向上取整。比如 pile11、k41131414//43正好是 ceil(2.75)3。如果你用的是 C 或 Java还得多留一个心眼piles 里单堆最大能到 10^9总小时数累加很容易超过 int 范围需要用 long 来存 hours。Python 虽然不用担心溢出但思路要记牢换语言写时别踩。4.3 lo 和 hi 的卡点我怎么定位 WA 的我第一次写这题时把 hi 设成了 sum(piles)。这当然也能二分出正确答案但会出现一个问题如果 h 本身就很大比如 h 10^9而你从 lo1、hisum(piles) 开始需要二分大约 30 多次这在复杂度上没问题但如果我随手把 lo 设成 0那 feasible(0) 就会出现除零错误。后来我认真推导了一遍边界lo 最小只能是 1因为速度不能是 00 的话永远吃不完hi 最合理的是 max(piles)因为当 k max(piles) 时每一堆都恰好只需 1 小时总耗时等于堆的数量。题目保证 h len(piles)所以 k max(piles) 一定可行。有了lo 一定不可行、hi 一定可行的保证二分过程中维护不变量会更稳。这里要提醒一下边界风格的问题。网上二分答案有两种写法一种是while lo hihi mid/lo mid 1另一种是while lo himid 1/mid - 1最后取 lo 或某个变量。我个人的经验是在二分答案题里while lo hi配合可行就收缩 hi、不可行就 lo 加一这套写法最好用因为它天然把答案留在了区间缩到只剩一个点的位置不容易出现死循环。4.4 一眼看出这是二分答案的识别器很多读者问怎么才能判断一道题能不能用二分答案我的经验是看三点第一题目在最小化……的……或者最大化……的……比如最小速度、最少天数、最小装载能力第二存在一个单调的验证函数规模越大越容易满足或者越难满足第三答案本身落在某个连续整数区间里而暴力枚举这个区间太慢。类似题型可以拉一个清单1011 在 D 天内送达包裹的能力最小船运载量、410 分割数组的最大值、1552 两球之间的磁力最大化最小间距、2064 分配给商店的最多商品的最小值。这些题目表面上一个说香蕉一个说包裹一个说数组一个说磁力但解法都是同一个二分答案模板。Day59 之后我把这四题放在同一个复习分组里过两周再看一眼比单纯背模板有用得多。5. 三道题背后的同一个思维模型先想暴力再套骨架5.1 暴力到骨架的对照表今天三道题的共同点从暴力到骨架的视角看就特别清楚题目暴力做法瓶颈在哪替换成的骨架994 腐烂的橘子模拟每一分钟扫描整个 grid找所有烂橘子再扩散每分钟全网格扫描太慢O(分钟mn)多源 BFS一层等于一分钟O(m*n)224 基本计算器不停地算括号内表达式直到没有括号每次遇到右括号都要回溯重算压栈保存现场遇到右括号 O(1) 恢复O(n)875 爱吃香蕉的狒狒从 k1 开始逐个试到 max(piles)每次验证线性枚举太慢O(maxPile*n)利用单调性二分答案O(n log maxPile)这张表是我复盘时画在笔记本上的。刷题到后半程最有价值的动作不是把每道题的代码抄一遍而是每做完一题都做一次暴力到骨架的对照。你会发现绝大多数难题都只是在一个朴素暴力想法上面叠了一层加速结构。5.2 三步走把一道新题拆出骨架我刷到第59天总结出一套应对陌生题的三步流程今天恰好三次用到第一步先想暴力。不要急着套算法先想想如果没有任何复杂度限制你会怎么写。通常是一层或两层循环或者直接递归。第二步找瓶颈。那个暴力解法里最慢的操作是什么是重复扫描整个集合、还是反复计算同一个子问题、还是枚举了一个很大的范围第三步匹配骨架。重复扫描整个集合 → 可能用哈希表或预处理反复计算子问题 → 动态规划或记忆化层层扩散同时发生 → BFS枚举很大的区间且答案有单调性 → 二分答案需要保存中间现场再恢复 → 栈状态之间有明确前后依赖 → 拓扑排序、并查集……这个模式题库就是靠平时做题一点点积累的。Day59 对我来说最大的进步就是看到 994 的一瞬间能直接喊出多源 BFS看到 875 的一瞬间能直接喊出二分答案而不是盯着题目发呆十分钟。5.3 模板不是背出来的是画出来的很多人问我是不是要把各种模板抄在小本子上每天背。我的真实体会是模板这个东西光背没有用你必须亲手画一遍它的执行流程。比如 BFS 模板我把旋转橘子的扩散过程用方框画了四层每层框一个矩形标上第几分钟画完你就永远不会搞错层数和节点数的关系。比如二分答案模板我画过一条从不可行到可行的谓词曲线把 mid 落在哪个区间、hi 和 lo 怎么移动标在轴上。画过一遍之后你就不再是背模板而是理解为什么模板长这样。6. 周赛430的联动启发与刷题日志该怎么记6.1 周赛430我交出的学费这一周恰好赶上了 LeetCode 周赛430。我的成绩很普通但赛后复盘收获不小。周赛里的第一题本质上就是一个模拟题难度不高我却因为边界条件写错交了两发 WA。为什么因为那道题和我平时练的数组题很不一样它考验的是把题意准确翻译成边界判断这正是我在 Day59 这几道题里反复踩坑的同一个地方——不是算法难而是边界条件的完整性。第二题我一眼就看出是二分答案的味但套模板时把 hi 设错了导致答案偏大。赛后翻讨论区发现不少人都有同样的教训。这让我意识到一个很现实的问题刷题时你已经知道题目属于哪个分类当然知道用什么模板但周赛没有分类标签你必须自己在 30 秒内完成识别骨架这一步。这个能力靠的是平时做题时真的去复盘我为什么想到这个模板而不是只看题解里标的分类名。6.2 一份能复盘的刷题日志长什么样Day59 这个命名的价值恰恰在于它逼着我用一个又一个真实日期去记录刷题过程。我见过很多人刷题日志只记今天刷了哪几题然后就没有然后了。我自己的日志至少有这几栏题号、分类、是否一次 AC、卡了多久、核心卡点是什么、下次复习优先级。今天这三题的日志我记录如下题号分类一次AC卡点复习优先级994图/BFS否忘记提前处理 fresh0层数多算高224栈否括号前负号未保存压栈丢失 sign极高875二分答案是无模板已较熟练中看到没有一整天三题里两题没有一次 AC这个成绩单一点都不光鲜。但正是卡点那一列构成了我接下来一周的复习清单。过一周我再回来刷 994 和 224 的时候不用重看整道题只看卡点那行字就能迅速恢复记忆然后合上题解自己重写一遍。这种瞄准弱点重写的效率比把 AC 的代码抄十遍高得多。6.3 针对面试的最后一公里回到面试经典150 这个目标上。150 题刷完不是终点面试官不会因为你刷过 150 题就给你 offer他看的是你能不能边想边说以及你面对没见过的题时候的临场反应。我的体会是后半程刷题必须有意识地练两件事一是先口述暴力解法再优化很多候选人一上来就背模板面试官问为什么不用暴力反而答不上来二是把边界条件当一等公民像今天 994 的 fresh0、224 的括号前负号、875 的 hi 取值都是比会不会背模板更能拉开差距的地方。Day59 结束的时候我在日志最后写了一句给自己的话前一百题是在学题后五十题是在学型——从具体题目里抽出可复用的骨架才是刷题这件事真正开始产生复利的时候。这句话也送给正在这条路上死磕的你。