JAVA练习320- 腐烂的橘子

题目概览在给定的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来源994. 腐烂的橘子 - 力扣LeetCode解题分析方法一深度优先搜索橘子腐烂的方向无非是上下左右我们可以直接进行遍历如果当前是烂橘子就往上下左右腐烂因为数组里只有 0, 1, 2被腐烂的格子我们可以用 2 time 代替time 代表从烂橘子腐烂到这所用的次数当我们遍历到另一个非被动腐烂的 烂橘子时一样上下左右遍历如果遇到被腐烂的格子比较 time 和 从当前橘子腐烂所用次数取最小的一个如果 time 当前橘子的 time停止遍历。最后在遍历依次数组找最大腐烂次数即可。如果有新鲜橘子返回-1时间复杂度O(mn)空间复杂度O(mn)class Solution { public int orangesRotting(int[][] grid) { int m grid.length, n grid[0].length; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { rotting(grid, i, j, -1); } } } int time 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { return -1; } if (grid[i][j] 2) { time Math.max(time, grid[i][j] - 2); } } } return time; } public void rotting(int[][] grid, int i, int j, int time) { if (i 0 || j 0 || i grid.length || j grid[0].length) { return; } if (grid[i][j] 0) { return; } if (time ! -1 (grid[i][j] 2 || grid[i][j] 2 time)) { return; } time time -1 ? 0 : time; if (grid[i][j] 1 || grid[i][j] - 2 time){ grid[i][j] 2 time; } else if (grid[i][j] - 2 time) { return; } else { time grid[i][j] - 2; } time; rotting(grid, i 1, j, time); rotting(grid, i - 1, j, time); rotting(grid, i, j 1, time); rotting(grid, i, j - 1, time); } }方法二广度优先搜索我们可以先遍历一次用队列记录所有腐烂橘子的位置然后遍历队列先记录队列大小作为第一层的橘子数然后遍历所有第一层的橘子让他们朝着上下左右腐烂然后将腐烂的橘子入队列作为下一层的遍历。当队列的橘子清空时层数就为腐烂次数最后还要遍历依次整个数组如果有新鲜橘子返回 -1否则返回腐烂次数、时间复杂度O(mn)空间复杂度O(mn)class Solution { int[][] directs new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; public int orangesRotting(int[][] grid) { int m grid.length, n grid[0].length; QueueInteger queue new ArrayDeque(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { queue.offer(i * n j); } } } int num 0; while(!queue.isEmpty()) { int size queue.size(); boolean isRotted false; while(size-- ! 0) { int ncode queue.poll(); int i ncode / n, j ncode % n; for (int[] direct: directs) { int di i direct[0]; int dj j direct[1]; if (di 0 dj 0 di m dj n grid[di][dj] 1) { grid[di][dj] 2; queue.offer(di * n dj); isRotted true; } } } num isRotted ? 1 : 0; } for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { return -1; } } } return num; } }