断断续续刷LeetCode两年今年终于给自己下了死命令跟着第28届打卡训练营走完一整个周期。今天是Day03我却意外找回了最初刷题那种“解谜上头”的感觉。为什么这么说因为第三天的选题恰好踩在一组非常经典的组合上——LeetCode 994腐烂的橘子、073爱吃香蕉的狒狒外加一道224基本计算器。这三道题分别对应多源BFS、二分答案、栈与递归解析简直就是把“算法三板斧”按头塞给你练。如果你也正在纠结LeetCode刷题指南里那些“每天该刷什么”的问题今天这篇文章就是一份实打实的Day03复盘从题目拆解到踩坑记录全部摊开讲。1. 28届LeetCode打卡训练营Day03到底在练什么1.1 打卡活动是怎么运作的为什么值得跟很多人听到“28届”第一反应是这训练营都办到28届了是不是割韭菜我一开始也这么想但实际跟下来才发现这类打卡训练营的核心价值不是“每天给你几道题”而是它提供了两个单干时很难获得的东西节奏感和反馈感。Day01通常是最简单的数组题Day02开始接触哈希表和双指针到了Day03题目难度会明显抬升一个台阶。这个设计是有讲究的——热身期大概三天如果前几天是“活动筋骨”第三天就是“上强度”的信号。训练营把994、073、224这三道中等偏难的题安排在同一天目的很明确让你一次性接触三种不同思维方向的题型逼你在一天内完成“识别模型—套模板—处理细节”的完整闭环。我自己的经验是刷题最怕的不是题难而是“刷了没感觉”。如果连续三天都在做easy题大脑会进入舒适区第四天遇到真正的难题反而会崩。Day03这种“一题一模型”的编排恰好能避免这个问题。1.2 三题组合背后的选题逻辑先说结论994腐烂的橘子是“图上多源扩散”的经典题073爱吃香蕉的狒狒是“二分答案”的入门必刷224基本计算器是“栈表达式解析”的代表作。这三个方向在LeetCode热门100题里出现的频率非常高属于那种“今天不练以后早晚得补”的题。从难度曲线看994和073都算中等题224是困难题。这也很符合打卡训练营第三天的安排逻辑前两题用来建立信心最后一题用来让你意识到“自己还有很大提升空间”。说句实在的我做224之前觉得自己栈玩得还行做完之后发现能把表达式解析写得干净优雅跟能把题AC之间还差着一段距离。另外不知道你们发现没有这几道题的数据范围都很有“心眼”。994的棋盘最大是10x10073的piles长度最大是10^4224的字符串最长有3x10^5个字符。数据范围决定了算法选择这也是刷题指南里反复强调的一点先看数据范围再决定用什么复杂度。2. LeetCode 994腐烂的橘子多源BFS的经典打开方式2.1 题目到底在考什么为什么一眼锁定BFS994这道题的描述很形象网格里有新鲜橘子1、烂橘子2和空格0每分钟烂橘子会把上下左右四个方向的新鲜橘子也弄烂问全部腐烂需要多少分钟如果永远无法全部腐烂就返回-1。我第一次做这道题的时候第一反应是模拟每分钟遍历整张图把新鲜橘子挨个检查是否相邻烂橘子然后更新状态。这个思路没错但实现起来很啰嗦而且每一步都要扫一遍全图复杂度是O(NMT)如果数据再大一点就得超时。正确的姿势是多源BFS。为什么因为“烂橘子扩散”这个行为本质上是多个起点同时向外做广度优先遍历。这里的关键词是“同时”——多个烂橘子在同一个时刻一起感染而不是一个烂橘子先扩散完再轮到另一个。如果你把每个烂橘子单独BFS一遍再取最大值会有人为制造的时间偏差结果大概率是错的。多源BFS的处理方式非常直接初始时把所有值为2的格子全部入队然后一层一层往外扩散。每一层扩散对应一分钟。这个“层”的概念就是BFS天然自带的“时间戳”。2.2 用Python实现多源BFS代码该怎么组织先放我当天提交的版本然后逐行拆解from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) queue deque() fresh_count 0 # 初始化把所有坏橘子入队统计好橘子数量 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh_count 1 # 如果根本没有好橘子直接返回0 if fresh_count 0: return 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] minutes 0 while queue and fresh_count 0: minutes 1 # 记录当前队列长度只处理这一层的节点 for _ in range(len(queue)): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 2 # 原地修改标记已感染 fresh_count - 1 queue.append((nx, ny)) return minutes if fresh_count 0 else -1这个版本的几个细节值得说道说道。第一队列的层序遍历。for _ in range(len(queue))这行是关键。在while循环里我们先把当前队列长度固定下来只处理这个长度范围内的节点。这样每一轮while循环对应BFS的一层也就对应一分钟。如果不这样写而是直接while queue加popleft你会发现分钟数会变成“节点数”而不是“层数”结果完全不对。第二原地修改grid代替visited数组。把新鲜橘子标记为2省掉额外的visited二维数组。这块小优化在图上做BFS时非常实用尤其当你想压缩代码量的时候。缺点是这个操作会污染输入的grid如果后续还需要原始数据就得另建拷贝。刷题场景一般无所谓但如果你在公司笔试里遇到的题允许修改输入这会是一个不错的优化点。第三fresh_count提前返回。如果初始状态下就没有新鲜橘子那答案是0分钟不需要BFS。这个边界卡掉了很多人的第一次提交。另外如果初始有新鲜橘子但没有任何烂橘子那fresh_count永远不可能归零while循环直接不执行最后返回-1。这个分支由最后的判断自然处理不需要额外写if。2.3 腐烂的橘子踩坑记录新鲜橘子数、分钟数、重复入队做这道题最容易翻车的三个地方我都替你们试过了。第一个坑是分钟数的语义。之前写过一版把分钟数放在节点入队时加一结果发现答案比标准答案大了一倍。原因很简单BFS的“层”和“节点”是两回事。如果你在入队时记录层数一个节点的子节点会继承父节点的时间戳再加一这在多源场景下会重复累加。正确做法是每一层While循环结束才加一对应“这一分钟所有扩散动作完成”。第二个坑是没有统计fresh_count而是BFS结束后重新扫grid。这样做也能AC但多了一次O(N*M)的遍历而且逻辑绕。直接在初始化和感染过程中维护一个计数器BFS自然结束就能判断题干里的“是否全部腐烂”干净利落。第三个坑是方向数组忘记检查边界。四个方向的坐标偏移很好写但越界检查一旦漏掉数组越界异常或者把-1当成合法坐标都会让结果变得莫名其妙。我一般在写BFS时会把方向数组和边界检查作为“肌肉记忆”先写好再动业务逻辑。做完994再回头看这道题其实就是“多源BFS”这个知识点的照妖镜模型识别对了10分钟AC识别错了半小时改不出来。774分钟不存在的层数就是答案。3. LeetCode 073爱吃香蕉的狒狒二分答案的实战套路3.1 暴力解法为什么不行二分的判断条件怎么找073这道题有个很可爱的背景狒狒每小时能吃k根香蕉如果一堆香蕉少于k根它就全部吃完然后必须等满一个小时才能碰下一堆。给定piles数组和总时间h问最小的k是多少。直观的暴力思路是从k1开始逐个尝试算一下按这个速度能不能在h小时内吃完。如果能答案就是当前k不能就k加一接着试。这个思路没错但piles数组长度可以到10^4每堆香蕉的数量可以到10^9k的取值范围从1到最大堆的数量。暴力试下去时间复杂度大约是O(max(piles) * piles.length)在极端数据下直接TLE。二分答案的核心洞察是k越大吃完所有香蕉所需的总时间越少。k和时间之间是单调递减关系。单调性意味着我们可以用二分查找在这个值域上进行搜索把“从1逐个试”变成“每次排除一半”。判断条件怎么写给定一个速度mid计算按这个速度吃完所有堆需要的总小时数def can_finish(speed, piles, h): hours 0 for pile in piles: hours (pile speed - 1) // speed # 向上取整 return hours h这里有个非常容易踩的细节每小时最多只能吃一堆不是“这一小时吃了半堆下一小时继续吃剩下半堆”。所以每堆香蕉需要的时间都是独立的向上取整。比如一堆有10根速度是3那吃完整堆需要ceil(10/3)4小时——3小时吃掉9根剩1根还得再花完整的一小时。(pile speed - 1) // speed是整数向上取整的标准写法避免了浮点数运算。用math.ceil(pile / speed)不是不行但float在pile很大时有精度问题而且多一次函数调用。刷题时看到除法就手痒想用浮点的人最后都会在某个边角料样例上翻车不如一开始就用整数公式。3.2 二分边界和整数溢出这些细节决定你能不能一次AC确定了判断函数接下来是二分框架。我常用的模板是“左闭右开”风格left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid, piles, h): right mid else: left mid 1 return left这里left初始化为1而不是0因为速度0没有意义。right初始化为max(piles)因为当k等于最大堆的香蕉数时每堆只需要一小时总共需要len(piles)小时这是必然能完成的最慢上限。如果你让right更大比如10^9那二分要多跑大约30轮虽然也能过但没必要。检查can_finish(mid)返回True时当前速度可行但我们想找“最小可行速度”所以把右边界收回来继续在左边找。返回False时说明速度太慢左边界移动到mid1。这个模板配合“找下界”的语义几乎可以套用所有二分答案题目。代码里还有一个隐藏的坑计算总小时数时如果piles数组很大且速度很小hours有可能非常大。在Python里整数没有溢出问题但如果用C/Java写记得用long。我见过面试者当场因为int溢出导致TLE的——不是算法复杂度问题是类型问题特别冤。3.3 073的边界测试单堆香蕉、刚好整除、h等于堆数二分答案题最怕的不是二分写错而是边界没考虑全。这道题的几个典型边界第一len(piles) h时。这种情况每一堆必须正好花一小时答案就是max(piles)因为速度不够的话某堆要耗两小时总时长就会超过h。用二分跑也能得到正确答案但理解这个边界有助于你验证自己的二分实现是否可靠。第二h非常大比如h sum(piles)。这时候速度1就能完成答案就是1。这个case可以帮你确认left初始化的正确性——如果left初始化为0二分过程中可能出现除以零的错误虽然语言层面不一定崩但逻辑上是不对的。第三pile刚好是speed的整数倍。比如一堆6根速度3(6 2) // 3 2不需要2.5向上取整到3。“向上取整”这四个字在整除时是退化为普通除法的很多人单独测试时知道但放进二分循环里就忘了。这道题做透了之后后面遇到“第K个最小值”“魔法词典”“分配巧克力”等一堆二分答案题你会发现都是同一个骨架换皮找单调性写判断函数套二分模板。这就是刷题指南里常说的“模型迁移”。4. LeetCode 224基本计算器栈与递归的工程思维4.1 表达式求值的核心难点为什么需要栈224基本计算器是这三道题里最硬核的一道。题目要求实现一个支持加、减、括号的简单计算器输入字符串包含数字、空格、、-、(、)没有乘除但允许负数出现。比如1 - ( - 2 )这种输入。第一眼看会觉得没有乘除不是很简单吗从左到右累加不就行了但括号一出现问题就来了。括号改变了运算优先级而且括号是可以嵌套的。从左到右扫的时候你遇到左括号必须暂时把当前结果“存起来”等括号里的子表达式算完再根据括号前的符号组合进总结果。这个“存起来”的动作正是栈的天然用途。你可以把栈理解成一个小型储物柜遇到左括号时把当前结果和括号前的正负号存进柜子然后重置当前结果专心计算括号内部的表达式遇到右括号时从柜子里取出之前存的结果和符号把括号内的计算结果“组合”回去。224题在LeetCode热门100题里有一席之地是因为它同时考察了“处理字符串的细节”和“用栈管理嵌套状态”两个能力而这两点在实际工作——比如写SQL解析器、表达式引擎、模板语言——中都会遇到。4.2 代码讲解符号位、数字读取、弹出时的符号处理我当天AC的版本class Solution: def calculate(self, s: str) - int: stack [] sign 1 result 0 i 0 while i len(s): ch s[i] if ch.isdigit(): num 0 while i len(s) and s[i].isdigit(): num num * 10 int(s[i]) i 1 result sign * num continue elif ch : sign 1 elif ch -: sign -1 elif ch (: stack.append(result) stack.append(sign) result 0 sign 1 elif ch ): sign stack.pop() prev_result stack.pop() result prev_result sign * result i 1 return result代码不长但每一行都有讲究。sign变量的作用是记录当前数字应该以正号还是负号并入结果。扫描到就记为1扫描到-就记为-1。所有数字统一用result sign * num处理这样加法和减法就统一成一个逻辑了。注意-后面可能紧跟空格再跟数字比如- 3所以状态切换和数字读取是两个独立的处理分支。数字读取那段循环处理了“多位数字”。比如123 4扫描到1时不能立刻停止要把后面的2和3一起读进来。这里有个细节读完之后i已经指向数字后面的那一格所以要用continue跳过一次外层while末尾的i 1否则会跳过一个字符。如果你不习惯continue也可以把外层循环改成手动步进逻辑等价但代码会啰嗦些。遇到左括号时把当前result和sign依次压栈然后把result清0、sign重置为1。这样进入括号内部时我们就有一个全新的“局部计算上下文”。栈里保存的是“括号外的世界”。嵌套括号也很好处理每进入一层括号就压一层栈出来时就弹一层。遇到右括号时先从栈里弹出符号和之前的结果然后result prev_result sign * result。这里最容易出错的是符号的取用顺序因为压栈时先压result再压sign弹栈时就要先弹sign再弹prev_result。如果你调换了顺序或者把两者赋值搞反了结果会错得离谱而且Debug起来很痛苦。4.3 工程视角224里的栈技巧和真实计算器有什么关联说实话我刚刷到224这道题时第一反应是“面试会考这个”。后来在做一个小工具时需要解析用户输入的条件表达式比如(a b) (c - d)这种我才意识到LeetCode里的表达式题其实是一个简化版的编译原理入门。编译器解析表达式时会把中缀表达式我们平时写的1 2 * 3转换成后缀表达式也叫逆波兰表达式1 2 3 * 然后用栈来完成计算。224这道题虽然没到逆波兰那一步但“遇到左括号压栈、右括号弹栈”的机制本质上就是在模拟递归下降解析中的上下文切换。如果你有兴趣可以在AC 224之后试着自己扩展一下加入*和/、处理一元负号、甚至加入变量替换。做完这些扩展后再回头看224会发现LeetCode的题目并不是孤立的脑筋急转弯它们是在用很小的样例训练你把“嵌套结构”抽象成“栈操作”的能力。从这个角度说224比994和073更需要耐心。第一次提交你可能TLE或者WA不要慌先检查符号位有没有漏更新再检查数字读取的指针有没有跳格最后检查左右括号的配对逻辑。这三个地方占了这道题90%的bug来源。5. Day03三题横向总结与刷题方法论5.1 三题对比模型、复杂度、易错点在哪儿做完三题之后我习惯画一张对比表来复盘强迫自己用语言把每道题最核心的点写清楚。题号核心考点时间/空间复杂度最容易错的细节994腐烂的橘子多源BFS、层序遍历O(NM) / O(NM)fresh_count维护、分钟数在层间加一073爱吃香蕉的狒狒二分答案、单调性判断O(N log M)M为最大堆香蕉数 / O(1)向上取整公式、left初始化、h边界224基本计算器栈、表达式解析、状态切换O(N) / O(N)sign重置、括号压栈顺序、多位数字读取这三题有一个共同点它们都有“一眼看穿模型之后的固定套路”。994是BFS队列模板073是二分答案模板224是栈处理括号模板。之所以说Day03适合做这种“模板训练”是因为模板这种东西只有在你亲手写过一遍、踩过一次坑、然后再对着标答检查一遍之后才会真正长在脑子里。如果今天是你第一次做这三道题建议不要只看这篇总结就完事。试着合上书自己把代码写一遍然后跑几个特殊用例994试试全空棋盘、073试试h特别大、224试试全是括号的输入。跑完了再去翻LeetCode题解你会发现自己对“为什么这么写”的理解会加深很多。5.2 从三题抽象出的“元能力”怎么把题模迁移到新题LeetCode刷题指南里经常出现一句话“刷题不是背题而是识别模式”。Day03这三题就是把这句话具象化的好例子。所谓“元能力”第一是扩散类问题的BFS直觉。见到“从一个点或多个点向周围扩散”的题不管是感染、污染、洪水还是消息传播第一反应就该是BFS而不是DFS。BFS保证的是“最短时间/最小步数”DFS则更适合“是否存在路径”。994里同时有多个传染源所以是多源BFS如果题目变成“从最短路线的起点出发到达终点”那就是单源BFS或者Dijkstra了。第二是最优值搜索的二分直觉。遇到“找一个值它是最小的满足条件X的值”只要这个条件X具有单调性就优先考虑二分答案。很多人对二分的理解停留在“在有序数组里找一个数”实际上二分的威力在于“在值域上做搜索”073就是典型的“答案在1到max(piles)之间二分”的题。第三是嵌套结构的状态栈直觉。遇到底层结构是同构的题——括号嵌套、XML标签嵌套、函数调用嵌套——都应该想想能不能用栈保存“外层状态”。224做多了之后你会发现“括号匹配”类题目和“表达式求值”类题目本质上是同一个东西区别只是括号中间夹的是数字还是另一个表达式。5.3 三题连刷时的时间分配与心态管理最后说点实操层面的。我Day03的实际用时大概是994约20分钟第一次WA在分钟数计算073约25分钟卡在left初始化224约40分钟一开始符号处理绕晕了。三道题加起来一个半小时出头加上复盘写笔记总共约两小时。如果你的基础比较薄我建议把224留到最后前面两题先把BFS和二分的手感找回来。如果两道题都在15分钟内AC那说明你的基础模板已经比较扎实了可以直接冲224如果前面两道题超过40分钟还没AC建议今天先不碰224回头去补一道简单的“括号匹配”题做好铺垫。心态上有个小技巧不要在一道题上死磕超过45分钟。打卡训练营的意义在于持续积累今天卡住的题睡一觉之后第二天再看往往会有新思路。如果45分钟还没有任何进展果断看题解看懂之后合上答案自己重新敲一遍代码。这个“倒着做”的过程远比“正着盯一晚上”高效。另外我还发现一个规律Day03这种难度组合恰恰是大量刷题者放弃的节点。Day01、Day02谁都能坚持Day03开始有困难题了就有人开始“跳题”“只看题解不敲代码”。你要是能完整跟下这一天其实已经赢过一半人了。6. 顺手聊聊这周的热点LeetCode周赛430和热门100题6.1 周赛430里有什么值得关注的题这周LeetCode周赛430我也参加了。因为是周日上午场状态一般只AC了两道题。说句公道话周赛的题质量并不总是比每日一题高但它最大的价值在于限时45分钟的压力环境。在这种环境下你才会真正暴露自己在“模型识别”上的短板——哪些题你能在5分钟内锁定考点哪些题你盯了10分钟还在瞎试一览无余。6.2 热门100题为什么值得反复刷怎么刷最后想聊一下LeetCode热门100题。很多新手朋友问我“100题刷完一遍是不是就够了”我的真实感受是100题第一遍刷完只是“见过”这些题第二遍刷完才算是“掌握”了一部分第三遍隔两周再刷才能真正内化成自己的东西。拿994来说我这是第三次做了。第一次做的时候连多源BFS都没想到第二次做的时候能写出正确代码但解释不清为什么这次做的时候已经能顺手写出层序遍历的时间戳写法并且能预判到fresh_count那个坑了。题目还是同一道题但你的理解深度完全不一样。具体的二刷方法我建议按“知识点”而不是“题号”分组。比如这周刷完Day03可以把BFS、二分答案、栈这三类题集中再过一遍每类挑两三道典型题做一遍加写题解。这比漫无目的地按顺序刷100题效果好得多。写在最后的经验今天这段Day03的刷题过程对我来说最大的收获不是AC了这三道题而是重新确认了一个道理刷题进步的秘诀不在智商而在刻意练习的频率和复盘深度。如果你也想这样系统性地刷题我建议你加入一个打卡训练营或者自己定一个“每天固定三道题、周末复盘”的规矩。关键是让刷题变成习惯而不是靠意志力硬撑。第28届训练营也好自己拉的刷题群也罢形式不重要坚持和思考才重要。明天是Day04按照节奏安排大概会进入二叉树和回溯的专题了。如果你也是第28届的一员或者正在用类似的方式刷LeetCode欢迎在评论区分享一下你的Day03用了多久哪道题卡住的时间最长——咱们互相取取经。 LeetCode打卡Day03复盘：三道题吃透多源BFS、二分答案与栈
断断续续刷LeetCode两年今年终于给自己下了死命令跟着第28届打卡训练营走完一整个周期。今天是Day03我却意外找回了最初刷题那种“解谜上头”的感觉。为什么这么说因为第三天的选题恰好踩在一组非常经典的组合上——LeetCode 994腐烂的橘子、073爱吃香蕉的狒狒外加一道224基本计算器。这三道题分别对应多源BFS、二分答案、栈与递归解析简直就是把“算法三板斧”按头塞给你练。如果你也正在纠结LeetCode刷题指南里那些“每天该刷什么”的问题今天这篇文章就是一份实打实的Day03复盘从题目拆解到踩坑记录全部摊开讲。1. 28届LeetCode打卡训练营Day03到底在练什么1.1 打卡活动是怎么运作的为什么值得跟很多人听到“28届”第一反应是这训练营都办到28届了是不是割韭菜我一开始也这么想但实际跟下来才发现这类打卡训练营的核心价值不是“每天给你几道题”而是它提供了两个单干时很难获得的东西节奏感和反馈感。Day01通常是最简单的数组题Day02开始接触哈希表和双指针到了Day03题目难度会明显抬升一个台阶。这个设计是有讲究的——热身期大概三天如果前几天是“活动筋骨”第三天就是“上强度”的信号。训练营把994、073、224这三道中等偏难的题安排在同一天目的很明确让你一次性接触三种不同思维方向的题型逼你在一天内完成“识别模型—套模板—处理细节”的完整闭环。我自己的经验是刷题最怕的不是题难而是“刷了没感觉”。如果连续三天都在做easy题大脑会进入舒适区第四天遇到真正的难题反而会崩。Day03这种“一题一模型”的编排恰好能避免这个问题。1.2 三题组合背后的选题逻辑先说结论994腐烂的橘子是“图上多源扩散”的经典题073爱吃香蕉的狒狒是“二分答案”的入门必刷224基本计算器是“栈表达式解析”的代表作。这三个方向在LeetCode热门100题里出现的频率非常高属于那种“今天不练以后早晚得补”的题。从难度曲线看994和073都算中等题224是困难题。这也很符合打卡训练营第三天的安排逻辑前两题用来建立信心最后一题用来让你意识到“自己还有很大提升空间”。说句实在的我做224之前觉得自己栈玩得还行做完之后发现能把表达式解析写得干净优雅跟能把题AC之间还差着一段距离。另外不知道你们发现没有这几道题的数据范围都很有“心眼”。994的棋盘最大是10x10073的piles长度最大是10^4224的字符串最长有3x10^5个字符。数据范围决定了算法选择这也是刷题指南里反复强调的一点先看数据范围再决定用什么复杂度。2. LeetCode 994腐烂的橘子多源BFS的经典打开方式2.1 题目到底在考什么为什么一眼锁定BFS994这道题的描述很形象网格里有新鲜橘子1、烂橘子2和空格0每分钟烂橘子会把上下左右四个方向的新鲜橘子也弄烂问全部腐烂需要多少分钟如果永远无法全部腐烂就返回-1。我第一次做这道题的时候第一反应是模拟每分钟遍历整张图把新鲜橘子挨个检查是否相邻烂橘子然后更新状态。这个思路没错但实现起来很啰嗦而且每一步都要扫一遍全图复杂度是O(NMT)如果数据再大一点就得超时。正确的姿势是多源BFS。为什么因为“烂橘子扩散”这个行为本质上是多个起点同时向外做广度优先遍历。这里的关键词是“同时”——多个烂橘子在同一个时刻一起感染而不是一个烂橘子先扩散完再轮到另一个。如果你把每个烂橘子单独BFS一遍再取最大值会有人为制造的时间偏差结果大概率是错的。多源BFS的处理方式非常直接初始时把所有值为2的格子全部入队然后一层一层往外扩散。每一层扩散对应一分钟。这个“层”的概念就是BFS天然自带的“时间戳”。2.2 用Python实现多源BFS代码该怎么组织先放我当天提交的版本然后逐行拆解from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) queue deque() fresh_count 0 # 初始化把所有坏橘子入队统计好橘子数量 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh_count 1 # 如果根本没有好橘子直接返回0 if fresh_count 0: return 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] minutes 0 while queue and fresh_count 0: minutes 1 # 记录当前队列长度只处理这一层的节点 for _ in range(len(queue)): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 2 # 原地修改标记已感染 fresh_count - 1 queue.append((nx, ny)) return minutes if fresh_count 0 else -1这个版本的几个细节值得说道说道。第一队列的层序遍历。for _ in range(len(queue))这行是关键。在while循环里我们先把当前队列长度固定下来只处理这个长度范围内的节点。这样每一轮while循环对应BFS的一层也就对应一分钟。如果不这样写而是直接while queue加popleft你会发现分钟数会变成“节点数”而不是“层数”结果完全不对。第二原地修改grid代替visited数组。把新鲜橘子标记为2省掉额外的visited二维数组。这块小优化在图上做BFS时非常实用尤其当你想压缩代码量的时候。缺点是这个操作会污染输入的grid如果后续还需要原始数据就得另建拷贝。刷题场景一般无所谓但如果你在公司笔试里遇到的题允许修改输入这会是一个不错的优化点。第三fresh_count提前返回。如果初始状态下就没有新鲜橘子那答案是0分钟不需要BFS。这个边界卡掉了很多人的第一次提交。另外如果初始有新鲜橘子但没有任何烂橘子那fresh_count永远不可能归零while循环直接不执行最后返回-1。这个分支由最后的判断自然处理不需要额外写if。2.3 腐烂的橘子踩坑记录新鲜橘子数、分钟数、重复入队做这道题最容易翻车的三个地方我都替你们试过了。第一个坑是分钟数的语义。之前写过一版把分钟数放在节点入队时加一结果发现答案比标准答案大了一倍。原因很简单BFS的“层”和“节点”是两回事。如果你在入队时记录层数一个节点的子节点会继承父节点的时间戳再加一这在多源场景下会重复累加。正确做法是每一层While循环结束才加一对应“这一分钟所有扩散动作完成”。第二个坑是没有统计fresh_count而是BFS结束后重新扫grid。这样做也能AC但多了一次O(N*M)的遍历而且逻辑绕。直接在初始化和感染过程中维护一个计数器BFS自然结束就能判断题干里的“是否全部腐烂”干净利落。第三个坑是方向数组忘记检查边界。四个方向的坐标偏移很好写但越界检查一旦漏掉数组越界异常或者把-1当成合法坐标都会让结果变得莫名其妙。我一般在写BFS时会把方向数组和边界检查作为“肌肉记忆”先写好再动业务逻辑。做完994再回头看这道题其实就是“多源BFS”这个知识点的照妖镜模型识别对了10分钟AC识别错了半小时改不出来。774分钟不存在的层数就是答案。3. LeetCode 073爱吃香蕉的狒狒二分答案的实战套路3.1 暴力解法为什么不行二分的判断条件怎么找073这道题有个很可爱的背景狒狒每小时能吃k根香蕉如果一堆香蕉少于k根它就全部吃完然后必须等满一个小时才能碰下一堆。给定piles数组和总时间h问最小的k是多少。直观的暴力思路是从k1开始逐个尝试算一下按这个速度能不能在h小时内吃完。如果能答案就是当前k不能就k加一接着试。这个思路没错但piles数组长度可以到10^4每堆香蕉的数量可以到10^9k的取值范围从1到最大堆的数量。暴力试下去时间复杂度大约是O(max(piles) * piles.length)在极端数据下直接TLE。二分答案的核心洞察是k越大吃完所有香蕉所需的总时间越少。k和时间之间是单调递减关系。单调性意味着我们可以用二分查找在这个值域上进行搜索把“从1逐个试”变成“每次排除一半”。判断条件怎么写给定一个速度mid计算按这个速度吃完所有堆需要的总小时数def can_finish(speed, piles, h): hours 0 for pile in piles: hours (pile speed - 1) // speed # 向上取整 return hours h这里有个非常容易踩的细节每小时最多只能吃一堆不是“这一小时吃了半堆下一小时继续吃剩下半堆”。所以每堆香蕉需要的时间都是独立的向上取整。比如一堆有10根速度是3那吃完整堆需要ceil(10/3)4小时——3小时吃掉9根剩1根还得再花完整的一小时。(pile speed - 1) // speed是整数向上取整的标准写法避免了浮点数运算。用math.ceil(pile / speed)不是不行但float在pile很大时有精度问题而且多一次函数调用。刷题时看到除法就手痒想用浮点的人最后都会在某个边角料样例上翻车不如一开始就用整数公式。3.2 二分边界和整数溢出这些细节决定你能不能一次AC确定了判断函数接下来是二分框架。我常用的模板是“左闭右开”风格left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid, piles, h): right mid else: left mid 1 return left这里left初始化为1而不是0因为速度0没有意义。right初始化为max(piles)因为当k等于最大堆的香蕉数时每堆只需要一小时总共需要len(piles)小时这是必然能完成的最慢上限。如果你让right更大比如10^9那二分要多跑大约30轮虽然也能过但没必要。检查can_finish(mid)返回True时当前速度可行但我们想找“最小可行速度”所以把右边界收回来继续在左边找。返回False时说明速度太慢左边界移动到mid1。这个模板配合“找下界”的语义几乎可以套用所有二分答案题目。代码里还有一个隐藏的坑计算总小时数时如果piles数组很大且速度很小hours有可能非常大。在Python里整数没有溢出问题但如果用C/Java写记得用long。我见过面试者当场因为int溢出导致TLE的——不是算法复杂度问题是类型问题特别冤。3.3 073的边界测试单堆香蕉、刚好整除、h等于堆数二分答案题最怕的不是二分写错而是边界没考虑全。这道题的几个典型边界第一len(piles) h时。这种情况每一堆必须正好花一小时答案就是max(piles)因为速度不够的话某堆要耗两小时总时长就会超过h。用二分跑也能得到正确答案但理解这个边界有助于你验证自己的二分实现是否可靠。第二h非常大比如h sum(piles)。这时候速度1就能完成答案就是1。这个case可以帮你确认left初始化的正确性——如果left初始化为0二分过程中可能出现除以零的错误虽然语言层面不一定崩但逻辑上是不对的。第三pile刚好是speed的整数倍。比如一堆6根速度3(6 2) // 3 2不需要2.5向上取整到3。“向上取整”这四个字在整除时是退化为普通除法的很多人单独测试时知道但放进二分循环里就忘了。这道题做透了之后后面遇到“第K个最小值”“魔法词典”“分配巧克力”等一堆二分答案题你会发现都是同一个骨架换皮找单调性写判断函数套二分模板。这就是刷题指南里常说的“模型迁移”。4. LeetCode 224基本计算器栈与递归的工程思维4.1 表达式求值的核心难点为什么需要栈224基本计算器是这三道题里最硬核的一道。题目要求实现一个支持加、减、括号的简单计算器输入字符串包含数字、空格、、-、(、)没有乘除但允许负数出现。比如1 - ( - 2 )这种输入。第一眼看会觉得没有乘除不是很简单吗从左到右累加不就行了但括号一出现问题就来了。括号改变了运算优先级而且括号是可以嵌套的。从左到右扫的时候你遇到左括号必须暂时把当前结果“存起来”等括号里的子表达式算完再根据括号前的符号组合进总结果。这个“存起来”的动作正是栈的天然用途。你可以把栈理解成一个小型储物柜遇到左括号时把当前结果和括号前的正负号存进柜子然后重置当前结果专心计算括号内部的表达式遇到右括号时从柜子里取出之前存的结果和符号把括号内的计算结果“组合”回去。224题在LeetCode热门100题里有一席之地是因为它同时考察了“处理字符串的细节”和“用栈管理嵌套状态”两个能力而这两点在实际工作——比如写SQL解析器、表达式引擎、模板语言——中都会遇到。4.2 代码讲解符号位、数字读取、弹出时的符号处理我当天AC的版本class Solution: def calculate(self, s: str) - int: stack [] sign 1 result 0 i 0 while i len(s): ch s[i] if ch.isdigit(): num 0 while i len(s) and s[i].isdigit(): num num * 10 int(s[i]) i 1 result sign * num continue elif ch : sign 1 elif ch -: sign -1 elif ch (: stack.append(result) stack.append(sign) result 0 sign 1 elif ch ): sign stack.pop() prev_result stack.pop() result prev_result sign * result i 1 return result代码不长但每一行都有讲究。sign变量的作用是记录当前数字应该以正号还是负号并入结果。扫描到就记为1扫描到-就记为-1。所有数字统一用result sign * num处理这样加法和减法就统一成一个逻辑了。注意-后面可能紧跟空格再跟数字比如- 3所以状态切换和数字读取是两个独立的处理分支。数字读取那段循环处理了“多位数字”。比如123 4扫描到1时不能立刻停止要把后面的2和3一起读进来。这里有个细节读完之后i已经指向数字后面的那一格所以要用continue跳过一次外层while末尾的i 1否则会跳过一个字符。如果你不习惯continue也可以把外层循环改成手动步进逻辑等价但代码会啰嗦些。遇到左括号时把当前result和sign依次压栈然后把result清0、sign重置为1。这样进入括号内部时我们就有一个全新的“局部计算上下文”。栈里保存的是“括号外的世界”。嵌套括号也很好处理每进入一层括号就压一层栈出来时就弹一层。遇到右括号时先从栈里弹出符号和之前的结果然后result prev_result sign * result。这里最容易出错的是符号的取用顺序因为压栈时先压result再压sign弹栈时就要先弹sign再弹prev_result。如果你调换了顺序或者把两者赋值搞反了结果会错得离谱而且Debug起来很痛苦。4.3 工程视角224里的栈技巧和真实计算器有什么关联说实话我刚刷到224这道题时第一反应是“面试会考这个”。后来在做一个小工具时需要解析用户输入的条件表达式比如(a b) (c - d)这种我才意识到LeetCode里的表达式题其实是一个简化版的编译原理入门。编译器解析表达式时会把中缀表达式我们平时写的1 2 * 3转换成后缀表达式也叫逆波兰表达式1 2 3 * 然后用栈来完成计算。224这道题虽然没到逆波兰那一步但“遇到左括号压栈、右括号弹栈”的机制本质上就是在模拟递归下降解析中的上下文切换。如果你有兴趣可以在AC 224之后试着自己扩展一下加入*和/、处理一元负号、甚至加入变量替换。做完这些扩展后再回头看224会发现LeetCode的题目并不是孤立的脑筋急转弯它们是在用很小的样例训练你把“嵌套结构”抽象成“栈操作”的能力。从这个角度说224比994和073更需要耐心。第一次提交你可能TLE或者WA不要慌先检查符号位有没有漏更新再检查数字读取的指针有没有跳格最后检查左右括号的配对逻辑。这三个地方占了这道题90%的bug来源。5. Day03三题横向总结与刷题方法论5.1 三题对比模型、复杂度、易错点在哪儿做完三题之后我习惯画一张对比表来复盘强迫自己用语言把每道题最核心的点写清楚。题号核心考点时间/空间复杂度最容易错的细节994腐烂的橘子多源BFS、层序遍历O(NM) / O(NM)fresh_count维护、分钟数在层间加一073爱吃香蕉的狒狒二分答案、单调性判断O(N log M)M为最大堆香蕉数 / O(1)向上取整公式、left初始化、h边界224基本计算器栈、表达式解析、状态切换O(N) / O(N)sign重置、括号压栈顺序、多位数字读取这三题有一个共同点它们都有“一眼看穿模型之后的固定套路”。994是BFS队列模板073是二分答案模板224是栈处理括号模板。之所以说Day03适合做这种“模板训练”是因为模板这种东西只有在你亲手写过一遍、踩过一次坑、然后再对着标答检查一遍之后才会真正长在脑子里。如果今天是你第一次做这三道题建议不要只看这篇总结就完事。试着合上书自己把代码写一遍然后跑几个特殊用例994试试全空棋盘、073试试h特别大、224试试全是括号的输入。跑完了再去翻LeetCode题解你会发现自己对“为什么这么写”的理解会加深很多。5.2 从三题抽象出的“元能力”怎么把题模迁移到新题LeetCode刷题指南里经常出现一句话“刷题不是背题而是识别模式”。Day03这三题就是把这句话具象化的好例子。所谓“元能力”第一是扩散类问题的BFS直觉。见到“从一个点或多个点向周围扩散”的题不管是感染、污染、洪水还是消息传播第一反应就该是BFS而不是DFS。BFS保证的是“最短时间/最小步数”DFS则更适合“是否存在路径”。994里同时有多个传染源所以是多源BFS如果题目变成“从最短路线的起点出发到达终点”那就是单源BFS或者Dijkstra了。第二是最优值搜索的二分直觉。遇到“找一个值它是最小的满足条件X的值”只要这个条件X具有单调性就优先考虑二分答案。很多人对二分的理解停留在“在有序数组里找一个数”实际上二分的威力在于“在值域上做搜索”073就是典型的“答案在1到max(piles)之间二分”的题。第三是嵌套结构的状态栈直觉。遇到底层结构是同构的题——括号嵌套、XML标签嵌套、函数调用嵌套——都应该想想能不能用栈保存“外层状态”。224做多了之后你会发现“括号匹配”类题目和“表达式求值”类题目本质上是同一个东西区别只是括号中间夹的是数字还是另一个表达式。5.3 三题连刷时的时间分配与心态管理最后说点实操层面的。我Day03的实际用时大概是994约20分钟第一次WA在分钟数计算073约25分钟卡在left初始化224约40分钟一开始符号处理绕晕了。三道题加起来一个半小时出头加上复盘写笔记总共约两小时。如果你的基础比较薄我建议把224留到最后前面两题先把BFS和二分的手感找回来。如果两道题都在15分钟内AC那说明你的基础模板已经比较扎实了可以直接冲224如果前面两道题超过40分钟还没AC建议今天先不碰224回头去补一道简单的“括号匹配”题做好铺垫。心态上有个小技巧不要在一道题上死磕超过45分钟。打卡训练营的意义在于持续积累今天卡住的题睡一觉之后第二天再看往往会有新思路。如果45分钟还没有任何进展果断看题解看懂之后合上答案自己重新敲一遍代码。这个“倒着做”的过程远比“正着盯一晚上”高效。另外我还发现一个规律Day03这种难度组合恰恰是大量刷题者放弃的节点。Day01、Day02谁都能坚持Day03开始有困难题了就有人开始“跳题”“只看题解不敲代码”。你要是能完整跟下这一天其实已经赢过一半人了。6. 顺手聊聊这周的热点LeetCode周赛430和热门100题6.1 周赛430里有什么值得关注的题这周LeetCode周赛430我也参加了。因为是周日上午场状态一般只AC了两道题。说句公道话周赛的题质量并不总是比每日一题高但它最大的价值在于限时45分钟的压力环境。在这种环境下你才会真正暴露自己在“模型识别”上的短板——哪些题你能在5分钟内锁定考点哪些题你盯了10分钟还在瞎试一览无余。6.2 热门100题为什么值得反复刷怎么刷最后想聊一下LeetCode热门100题。很多新手朋友问我“100题刷完一遍是不是就够了”我的真实感受是100题第一遍刷完只是“见过”这些题第二遍刷完才算是“掌握”了一部分第三遍隔两周再刷才能真正内化成自己的东西。拿994来说我这是第三次做了。第一次做的时候连多源BFS都没想到第二次做的时候能写出正确代码但解释不清为什么这次做的时候已经能顺手写出层序遍历的时间戳写法并且能预判到fresh_count那个坑了。题目还是同一道题但你的理解深度完全不一样。具体的二刷方法我建议按“知识点”而不是“题号”分组。比如这周刷完Day03可以把BFS、二分答案、栈这三类题集中再过一遍每类挑两三道典型题做一遍加写题解。这比漫无目的地按顺序刷100题效果好得多。写在最后的经验今天这段Day03的刷题过程对我来说最大的收获不是AC了这三道题而是重新确认了一个道理刷题进步的秘诀不在智商而在刻意练习的频率和复盘深度。如果你也想这样系统性地刷题我建议你加入一个打卡训练营或者自己定一个“每天固定三道题、周末复盘”的规矩。关键是让刷题变成习惯而不是靠意志力硬撑。第28届训练营也好自己拉的刷题群也罢形式不重要坚持和思考才重要。明天是Day04按照节奏安排大概会进入二叉树和回溯的专题了。如果你也是第28届的一员或者正在用类似的方式刷LeetCode欢迎在评论区分享一下你的Day03用了多久哪道题卡住的时间最长——咱们互相取取经。