微网站 地图,众筹网站建设,免费建网站程序,企业门户网站管理办法腐烂的橘子
在给定的 m x n 网格 grid 中#xff0c;每个单元格可以有以下三个值之一#xff1a;
值 0 代表空单元格#xff1b;值 1 代表新鲜橘子#xff1b;值 2 代表腐烂的橘子。
每分钟#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到…腐烂的橘子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一
值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。
每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 示例 1 输入grid [[2,1,1],[1,1,0],[0,1,1]]
输出4
方法
广度优先遍历BFS
思路
找出所有腐烂的橘子将他们放入队列作为第0层的节点然后进行广度优先遍历BFS每个节点的相邻节点可能是上下左右四个方向的节点此处需要判断节点是否超出网格的边界由于可能存在无法被污染的橘子需要记录新鲜橘子的数量每遍历污染一个橘子就将新鲜的橘子数量减一如果BFS结束后仍然存在新鲜橘子就返回-1否则返回污染橘子的轮数时间
代码一
class Solution {public int orangesRotting(int[][] grid) {// 获取数组的行数和列数int rows grid.length;int cols grid[0].length;// 创建一个队列 用于存储橘子的信息Queueint[] queue new LinkedList();// 初始化新鲜橘子的数量 0 int count 0;for(int row 0; row rows; row){for(int col 0; col cols; col){// 若为新鲜橘子 countif(grid[row][col] 1){count;}else if(grid[row][col] 2){// 若为腐烂橘子 将其坐标信息入队queue.add(new int[]{row, col});}}}// 初始化腐烂的轮数分钟数int sumMin 0;// 当还有新鲜橘子或者队列不为空时继续腐烂橘子while(count 0 ! queue.isEmpty()){sumMin ; // 每经过一轮循环分钟数加一// 获取队列的长度int queLen queue.size();for(int i 0; i queLen; i){// 出队一个腐烂橘子的信息 并获取其坐标int[] orange queue.poll();int r orange[0];int c orange[1];// 检查该腐烂橘子的上下左右橘子 若为新鲜橘子 对其进行腐烂处理 并入队// 上if(r-1 0 grid[r-1][c] 1){// 标记为腐烂并且入队grid[r-1][c] 2;count--;queue.add(new int[]{r-1, c});}// 下if(r1 rows grid[r1][c] 1){// 标记为腐烂并且入队grid[r1][c] 2;count--;queue.add(new int[]{r1, c});}// 左if(c-1 0 grid[r][c-1] 1){// 标记为腐烂并且入队grid[r][c-1] 2;count--;queue.add(new int[]{r, c-1});}// 右if(c1 cols grid[r][c1] 1){// 标记为腐烂并且入队grid[r][c1] 2;count--;queue.add(new int[]{r, c1});}}}// 若遍历完还存在新鲜橘子 返回-1if(count 0){return -1;}else{return sumMin; // 返回腐烂所有橘子需要的时间}}
} 代码二
简化之后的代码
class Solution {public int orangesRotting(int[][] grid) {// 获取数组的行数和列数int rows grid.length;int cols grid[0].length;// 创建一个队列 用于存储橘子的信息Queueint[] queue new LinkedList();// 初始化新鲜橘子的数量 0 int count 0;// 定义方向数组 分别表示向右、左、下、上移动int[][] directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};for(int row 0; row rows; row){for(int col 0; col cols; col){// 若为新鲜橘子 countif(grid[row][col] 1){count;}else if(grid[row][col] 2){// 若为腐烂橘子 将其坐标信息入队queue.add(new int[]{row, col});}}}// 初始化腐烂的轮数分钟数int sumMin 0;// 当还有新鲜橘子或者队列不为空时继续腐烂橘子while(count 0 ! queue.isEmpty()){sumMin ; // 每经过一轮循环分钟数加一// 获取队列的长度int queLen queue.size();for(int i 0; i queLen; i){// 出队一个腐烂橘子的信息 并获取其坐标int[] orange queue.poll();int r orange[0];int c orange[1];// 检查该腐烂橘子的上下左右橘子 若为新鲜橘子 对其进行腐烂处理 并入队for(int[] dir : directions){int newRow r dir[0];int newCol c dir[1];if(newRow 0 newRow rows newCol 0 newCol cols grid[newRow][newCol] 1){count --;grid[newRow][newCol] 2;queue.add(new int[]{newRow, newCol});}}}}// 若遍历完还存在新鲜橘子 返回-1if(count 0){return -1;}else{return sumMin; // 返回腐烂所有橘子需要的时间}}
}
分析
时间复杂度O(nm) 即进行一次广度优先搜索的时间其中 ngrid.lengthngrid.lengthngrid.length, mgrid[0].lengthmgrid[0].lengthmgrid[0].length 。
空间复杂度O(nm) 需要额外的 disdisdis 数组记录每个新鲜橘子被腐烂的最短时间大小为 O(nm)O(nm)O(nm)且广度优先搜索中队列里存放的状态最多不会超过 nmnmnm 个最多需要 O(nm)O(nm)O(nm) 的空间所以最后的空间复杂度为 O(nm)O(nm)O(nm)。
