力扣994题解析:多源BFS解决腐烂橘子问题
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]...通过这种可视化可以清晰看到腐烂过程的进展帮助验证算法的正确性。

相关新闻

数字折纸技法:3-8瓣立体花朵制作与透明贴图设计

数字折纸技法:3-8瓣立体花朵制作与透明贴图设计

1. 项目背景与核心目标这个折纸教学项目源自手工教育领域的一个具体需求——如何通过折纸技法制作3-8瓣的立体花朵。标题中提到的"通义万相"指的是一种折纸技法体系,"04"代表这是该系列的第4个教学版本。核心创新点在于将传统折纸与数字设计相结…

2026/11/13 1:54:34 阅读更多 →
3ds Max 2022 安装激活全攻略:从版本选择到避坑指南

3ds Max 2022 安装激活全攻略:从版本选择到避坑指南

最近在帮几个刚入行的学弟学妹配置3ds Max时,发现网上很多所谓的“安装教程”要么步骤不全,要么链接失效,甚至夹杂着各种捆绑软件和病毒,让新手们踩了不少坑。3ds Max作为建筑、室内、游戏、影视行业的核心建模与渲染工具&#xf…

2026/11/21 18:19:16 阅读更多 →
Minimax-h3-Turbo高级玩法:自定义视频生成参数全解析

Minimax-h3-Turbo高级玩法:自定义视频生成参数全解析

Minimax-h3-Turbo高级玩法:自定义视频生成参数全解析 【免费下载链接】Minimax-h3-Turbo 项目地址: https://ai.gitcode.com/hf_mirrors/lightx2v/Minimax-h3-Turbo Minimax-h3-Turbo是一款基于MiniMaxAI/MiniMax-H3底座模型开发的视频生成工具,…

2026/11/12 1:17:42 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻