产品网站建设框架,深圳网站开发建设培训机构,收购域名,网站建设 汇卓(优先整理热门100及面试150#xff0c;不定期持续更新#xff0c;欢迎关注) 994. 腐烂的橘子
在给定的 m x n 网格 grid 中#xff0c;每个单元格可以有以下三个值之一#xff1a;
值 0 代表空单元格#xff1b;值 1 代表新鲜橘子#xff1b;值 2 代表腐烂的橘子。
每…(优先整理热门100及面试150不定期持续更新欢迎关注) 994. 腐烂的橘子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一
值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。
每分钟腐烂的橘子周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。
示例 1
输入grid [[2,1,1],[1,1,0],[0,1,1]]
输出4示例 2
输入grid [[2,1,1],[0,1,1],[1,0,1]]
输出-1解释左下角的橘子第 2 行 第 0 列永远不会腐烂因为腐烂只会发生在 4 个方向上。 示例 3
输入grid [[0,2]]
输出0解释因为 0 分钟时已经没有新鲜橘子了所以答案就是 0 。 提示
m grid.lengthn grid[i].length1 m, n 10grid[i][j] 仅为 0、1 或 2
方法广度优先搜索 (BFS)
使用 BFS 模拟橘子腐烂过程记录每个层次的处理时间。初始队列包含所有腐烂橘子每处理完一层后若该层导致新腐烂则时间加 1。
初始化遍历网格记录所有腐烂橘子的位置和新鲜橘子数量。特殊情况若没有新鲜橘子直接返回 0。BFS 处理逐层处理队列中的腐烂橘子腐烂其周围的新鲜橘子并记录时间。结果判断若仍存在未腐烂的新鲜橘子返回 -1否则返回总时间。
代码实现(Java)
class Solution {public int orangesRotting(int[][] grid) {int rows grid.length;int cols grid[0].length;Queueint[] queue new LinkedList();int fresh 0;// 初始化队列和新鲜橘子计数for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (grid[i][j] 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] 1) {fresh;}}}// 没有新鲜橘子直接返回0if (fresh 0) return 0;int[][] dirs {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};int time 0;while (!queue.isEmpty()) {int size queue.size();boolean hasRotten false;// 处理当前层的所有节点for (int i 0; i size; i) {int[] point queue.poll();for (int[] dir : dirs) {int x point[0] dir[0];int y point[1] dir[1];// 检查边界且是否为新鲜橘子if (x 0 x rows y 0 y cols grid[x][y] 1) {grid[x][y] 2;queue.offer(new int[]{x, y});fresh--;hasRotten true;}}}// 若当前层导致腐烂时间加1if (hasRotten) time;}// 若仍有新鲜橘子返回-1否则返回时间return fresh 0 ? time : -1;}
}复杂度分析
时间复杂度O(m×n)每个节点最多被访问一次。空间复杂度O(m×n)队列在最坏情况下存储所有腐烂橘子。 博客源文件Gitee仓库:
gitee.com/richardmilos/allen-csdn-notes
(持续更新未完待续)
