1. 问题背景与题目解析今天我们来聊聊力扣LeetCode上一道经典的广度优先搜索BFS题目——腐烂的橘子题目编号994。这道题在力扣的hot100题库中热度很高也是面试中经常出现的算法题之一。题目描述是这样的在一个给定的网格中每个单元格可以有以下三个值之一0 代表空单元格1 代表新鲜橘子2 代表腐烂的橘子每分钟任何与腐烂橘子相邻上下左右的新鲜橘子都会腐烂。我们需要计算直到没有橘子可以继续腐烂时所需的最小分钟数。如果不可能使所有橘子都腐烂则返回-1。举个例子 输入 [[2,1,1], [1,1,0], [0,1,1]] 输出4这个题目看似简单但考察了多个重要的算法概念和编程技巧。接下来我将从多个角度深入分析这道题的解法。2. 解题思路分析2.1 问题建模首先我们需要将这个问题转化为计算机可以处理的形式。这实际上是一个典型的图论问题每个橘子值为1或2的单元格可以看作图中的一个节点相邻的橘子之间存在边上下左右四个方向腐烂过程就是从初始腐烂节点开始的广度优先遍历2.2 关键观察点解决这个问题的关键在于几个重要观察腐烂过程是同步进行的所有当前腐烂的橘子会同时影响它们周围的新鲜橘子我们需要跟踪轮次每一轮代表一分钟的时间流逝最终需要检查是否还有新鲜橘子剩余2.3 算法选择基于上述观察广度优先搜索BFS是最合适的选择原因如下BFS天然适合处理层级或轮次的概念它可以同时从多个起点开始搜索多源BFS能够保证找到最短时间最小轮次3. 详细实现步骤3.1 初始准备首先我们需要准备以下数据记录所有初始腐烂橘子的位置队列初始化统计新鲜橘子的数量用于最终判断定义四个方向的移动向量上、下、左、右directions [(-1, 0), (1, 0), (0, -1), (0, 1)]3.2 BFS框架搭建标准的BFS框架包括初始化队列记录访问状态本题中可以通过直接修改网格值来实现层级/轮次计数from collections import deque def orangesRotting(grid): queue deque() fresh 0 rows, cols len(grid), len(grid[0]) # 初始化找到所有腐烂橘子和新鲜橘子数量 for r in range(rows): for c in range(cols): if grid[r][c] 2: queue.append((r, c)) elif grid[r][c] 1: fresh 13.3 多源BFS实现多源BFS的关键在于在每一轮开始时记录当前队列的大小处理完这一批所有节点后再处理新加入的节点只有处理完一整轮才增加时间计数time 0 while queue and fresh 0: # 处理当前轮次的所有节点 for _ in range(len(queue)): r, c queue.popleft() for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 2 fresh - 1 queue.append((nr, nc)) if queue: # 只有有新腐烂的橘子才增加时间 time 1 return time if fresh 0 else -14. 复杂度分析与优化4.1 时间复杂度我们需要遍历整个网格两次第一次初始化统计新鲜橘子和腐烂橘子第二次BFS过程最坏情况下所有橘子都会腐烂时间复杂度为O(m×n)其中m和n是网格的行数和列数4.2 空间复杂度队列的大小最多为O(m×n)当所有橘子同时腐烂时因此空间复杂度也是O(m×n)4.3 可能的优化提前终止如果在某一轮结束后新鲜橘子数量已经为0可以提前退出并行处理对于特别大的网格可以考虑并行处理不同区域的腐烂过程空间优化可以使用位运算或其他技巧减少空间使用但对于这个问题意义不大5. 边界条件与测试用例5.1 常见边界情况网格为空应该返回0因为没有橘子需要腐烂没有新鲜橘子直接返回0没有腐烂橘子如果有新鲜橘子返回-1如果没有新鲜橘子返回0新鲜橘子无法被全部腐烂返回-15.2 测试用例设计好的测试用例应该包括常规情况[[2,1,1],[1,1,0],[0,1,1]] # 预期输出4无法全部腐烂[[2,1,1],[0,1,1],[1,0,1]] # 预期输出-1没有新鲜橘子[[0,2]] # 预期输出0多个腐烂源[[2,1,1],[2,1,1],[1,1,2]] # 预期输出26. 实际编码中的注意事项6.1 常见错误时间计数错误忘记在队列不为空时才增加时间在每处理一个橘子后就增加时间新鲜橘子计数错误没有正确初始化fresh计数器在腐烂橘子时没有减少fresh计数边界检查不完整没有检查网格索引是否越界没有处理空网格的情况6.2 调试技巧打印中间状态print(fTime: {time}, Fresh: {fresh}, Queue size: {len(queue)})可视化网格变化for row in grid: print(row) print()使用小网格测试边界条件7. 算法扩展与变种7.1 相关题目墙与门LeetCode 286类似的多源BFS问题岛屿数量LeetCode 200连通分量问题01矩阵LeetCode 542多源BFS的另一个应用7.2 变种问题橘子腐烂速度不同某些橘子腐烂速度更快或更慢三维空间中的橘子腐烂网格变为三维橘子有抗腐烂能力需要多次接触才会腐烂动态添加新鲜橘子在腐烂过程中不断有新鲜橘子加入8. 面试中的应用8.1 面试官考察点对BFS算法的理解和应用能力处理多源BFS的能力边界条件的考虑代码的整洁度和可读性时间/空间复杂度分析能力8.2 回答策略先明确问题并给出简单例子讨论可能的算法选择为什么选BFS而不是DFS逐步构建解决方案讨论时间/空间复杂度提出可能的优化考虑边界条件8.3 常见面试问题如何证明你的算法能找到最小时间BFS保证最短路径/最小轮次如果网格非常大怎么办讨论并行处理或分布式算法如何修改算法处理腐烂速度不同的情况引入优先级队列或不同的处理逻辑9. 个人实战经验分享在实际解决这个问题时我遇到了几个有趣的坑时间计数问题最初我在每个橘子处理后都增加时间导致结果偏大。正确的做法是在处理完一整轮所有当前腐烂橘子后才增加时间。新鲜橘子计数忘记在初始化时统计新鲜橘子数量导致无法正确判断是否所有橘子都已腐烂。多源BFS的队列初始化一开始只加入了一个腐烂橘子而忽略了其他同时存在的腐烂源。一个实用的调试技巧是可视化每一分钟后的网格状态这能帮助快速定位问题所在。例如初始状态 [2,1,1] [1,1,0] [0,1,1]第1分钟后 [2,2,1] [2,1,0] [0,1,1]第2分钟后 [2,2,2] [2,2,0] [0,1,1]...通过这种可视化可以清晰看到腐烂过程的进展帮助验证算法的正确性。
1. 问题背景与题目解析今天我们来聊聊力扣LeetCode上一道经典的广度优先搜索BFS题目——腐烂的橘子题目编号994。这道题在力扣的hot100题库中热度很高也是面试中经常出现的算法题之一。题目描述是这样的在一个给定的网格中每个单元格可以有以下三个值之一0 代表空单元格1 代表新鲜橘子2 代表腐烂的橘子每分钟任何与腐烂橘子相邻上下左右的新鲜橘子都会腐烂。我们需要计算直到没有橘子可以继续腐烂时所需的最小分钟数。如果不可能使所有橘子都腐烂则返回-1。举个例子 输入 [[2,1,1], [1,1,0], [0,1,1]] 输出4这个题目看似简单但考察了多个重要的算法概念和编程技巧。接下来我将从多个角度深入分析这道题的解法。2. 解题思路分析2.1 问题建模首先我们需要将这个问题转化为计算机可以处理的形式。这实际上是一个典型的图论问题每个橘子值为1或2的单元格可以看作图中的一个节点相邻的橘子之间存在边上下左右四个方向腐烂过程就是从初始腐烂节点开始的广度优先遍历2.2 关键观察点解决这个问题的关键在于几个重要观察腐烂过程是同步进行的所有当前腐烂的橘子会同时影响它们周围的新鲜橘子我们需要跟踪轮次每一轮代表一分钟的时间流逝最终需要检查是否还有新鲜橘子剩余2.3 算法选择基于上述观察广度优先搜索BFS是最合适的选择原因如下BFS天然适合处理层级或轮次的概念它可以同时从多个起点开始搜索多源BFS能够保证找到最短时间最小轮次3. 详细实现步骤3.1 初始准备首先我们需要准备以下数据记录所有初始腐烂橘子的位置队列初始化统计新鲜橘子的数量用于最终判断定义四个方向的移动向量上、下、左、右directions [(-1, 0), (1, 0), (0, -1), (0, 1)]3.2 BFS框架搭建标准的BFS框架包括初始化队列记录访问状态本题中可以通过直接修改网格值来实现层级/轮次计数from collections import deque def orangesRotting(grid): queue deque() fresh 0 rows, cols len(grid), len(grid[0]) # 初始化找到所有腐烂橘子和新鲜橘子数量 for r in range(rows): for c in range(cols): if grid[r][c] 2: queue.append((r, c)) elif grid[r][c] 1: fresh 13.3 多源BFS实现多源BFS的关键在于在每一轮开始时记录当前队列的大小处理完这一批所有节点后再处理新加入的节点只有处理完一整轮才增加时间计数time 0 while queue and fresh 0: # 处理当前轮次的所有节点 for _ in range(len(queue)): r, c queue.popleft() for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 2 fresh - 1 queue.append((nr, nc)) if queue: # 只有有新腐烂的橘子才增加时间 time 1 return time if fresh 0 else -14. 复杂度分析与优化4.1 时间复杂度我们需要遍历整个网格两次第一次初始化统计新鲜橘子和腐烂橘子第二次BFS过程最坏情况下所有橘子都会腐烂时间复杂度为O(m×n)其中m和n是网格的行数和列数4.2 空间复杂度队列的大小最多为O(m×n)当所有橘子同时腐烂时因此空间复杂度也是O(m×n)4.3 可能的优化提前终止如果在某一轮结束后新鲜橘子数量已经为0可以提前退出并行处理对于特别大的网格可以考虑并行处理不同区域的腐烂过程空间优化可以使用位运算或其他技巧减少空间使用但对于这个问题意义不大5. 边界条件与测试用例5.1 常见边界情况网格为空应该返回0因为没有橘子需要腐烂没有新鲜橘子直接返回0没有腐烂橘子如果有新鲜橘子返回-1如果没有新鲜橘子返回0新鲜橘子无法被全部腐烂返回-15.2 测试用例设计好的测试用例应该包括常规情况[[2,1,1],[1,1,0],[0,1,1]] # 预期输出4无法全部腐烂[[2,1,1],[0,1,1],[1,0,1]] # 预期输出-1没有新鲜橘子[[0,2]] # 预期输出0多个腐烂源[[2,1,1],[2,1,1],[1,1,2]] # 预期输出26. 实际编码中的注意事项6.1 常见错误时间计数错误忘记在队列不为空时才增加时间在每处理一个橘子后就增加时间新鲜橘子计数错误没有正确初始化fresh计数器在腐烂橘子时没有减少fresh计数边界检查不完整没有检查网格索引是否越界没有处理空网格的情况6.2 调试技巧打印中间状态print(fTime: {time}, Fresh: {fresh}, Queue size: {len(queue)})可视化网格变化for row in grid: print(row) print()使用小网格测试边界条件7. 算法扩展与变种7.1 相关题目墙与门LeetCode 286类似的多源BFS问题岛屿数量LeetCode 200连通分量问题01矩阵LeetCode 542多源BFS的另一个应用7.2 变种问题橘子腐烂速度不同某些橘子腐烂速度更快或更慢三维空间中的橘子腐烂网格变为三维橘子有抗腐烂能力需要多次接触才会腐烂动态添加新鲜橘子在腐烂过程中不断有新鲜橘子加入8. 面试中的应用8.1 面试官考察点对BFS算法的理解和应用能力处理多源BFS的能力边界条件的考虑代码的整洁度和可读性时间/空间复杂度分析能力8.2 回答策略先明确问题并给出简单例子讨论可能的算法选择为什么选BFS而不是DFS逐步构建解决方案讨论时间/空间复杂度提出可能的优化考虑边界条件8.3 常见面试问题如何证明你的算法能找到最小时间BFS保证最短路径/最小轮次如果网格非常大怎么办讨论并行处理或分布式算法如何修改算法处理腐烂速度不同的情况引入优先级队列或不同的处理逻辑9. 个人实战经验分享在实际解决这个问题时我遇到了几个有趣的坑时间计数问题最初我在每个橘子处理后都增加时间导致结果偏大。正确的做法是在处理完一整轮所有当前腐烂橘子后才增加时间。新鲜橘子计数忘记在初始化时统计新鲜橘子数量导致无法正确判断是否所有橘子都已腐烂。多源BFS的队列初始化一开始只加入了一个腐烂橘子而忽略了其他同时存在的腐烂源。一个实用的调试技巧是可视化每一分钟后的网格状态这能帮助快速定位问题所在。例如初始状态 [2,1,1] [1,1,0] [0,1,1]第1分钟后 [2,2,1] [2,1,0] [0,1,1]第2分钟后 [2,2,2] [2,2,0] [0,1,1]...通过这种可视化可以清晰看到腐烂过程的进展帮助验证算法的正确性。
