052腐烂的橘子

腐烂的橘子题目链接https://leetcode.cn/problems/rotting-oranges/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public int orangesRotting(int[][] grid) { int m grid.length, n grid[0].length; QueueInteger decayed new LinkedList();//记录腐烂的橘子的位置 int[][] directions new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}}; int freshNum 0;//新鲜橘子的个数 int ans 0; for(int i0; im; i){ for(int j0; jn; j){ if(grid[i][j] 1){ freshNum; } else if(grid[i][j] 2){ decayed.add(i * n j); } } } while(!decayed.isEmpty()){ if(freshNum 0){ break; } int size decayed.size(); while(size 0){ int index decayed.remove(); size--; int row index / n; int col index % n; for(int i0; i4; i){ row directions[i][0]; col directions[i][1]; if(row0 rowm col0 coln grid[row][col] 1){ grid[row][col] 2; freshNum--; decayed.add(row * n col); } row - directions[i][0]; col - directions[i][1]; } } ans; } return freshNum 0 ? ans : -1; }分析代码的时间复杂度为O(mn)空间复杂度为O(mn)。解题思路采用广度优先搜索。先遍历一遍grid统计出新鲜橘子的个数同时把腐烂橘子的位置加入队列然后对队列中腐烂的橘子用广搜进行拓展每次拓展到一个新鲜橘子就让新鲜的橘子变为腐烂的橘子并让新鲜的橘子数量减一直到队列为空或没有新鲜橘子为止最终根据新鲜橘子的数量返回答案。看了官方题解后的解答int[] dr new int[]{-1, 0, 1, 0}; int[] dc new int[]{0, -1, 0, 1}; public int orangesRotting(int[][] grid) { int R grid.length, C grid[0].length; QueueInteger queue new ArrayDequeInteger(); MapInteger, Integer depth new HashMapInteger, Integer(); for (int r 0; r R; r) { for (int c 0; c C; c) { if (grid[r][c] 2) { int code r * C c; queue.add(code); depth.put(code, 0); } } } int ans 0; while (!queue.isEmpty()) { int code queue.remove(); int r code / C, c code % C; for (int k 0; k 4; k) { int nr r dr[k]; int nc c dc[k]; if (0 nr nr R 0 nc nc C grid[nr][nc] 1) { grid[nr][nc] 2; int ncode nr * C nc; queue.add(ncode); depth.put(ncode, depth.get(code) 1); ans depth.get(ncode); } } } for (int[] row: grid) { for (int v: row) { if (v 1) { return -1; } } } return ans; }分析​ 1、上方直接粘贴了官方版本的解答。官方题解只有一种解法即“多源广度优先搜索”。解题思路与我的解答一致只是实现上有所差别。具体差别在于​ 第一对于在四个方向上的移动我选择采用二维数组而官方题解采用两个一维数组分别控制水平方向上的移动和垂直方向上的移动​ 第二我直接利用一个变量维护广搜的层数而官方题解采用哈希表将层数信息与每个腐烂的橘子绑定在某些需要回溯或记录每个节点状态的场景下会更有优势​ 第三我最初遍历grid时统计了新鲜橘子的数量最后根据新鲜橘子的数量情况返回答案而官方题解采用最后重新遍历一遍grid判断是否还有新鲜橘子来返回答案​ 第四官方题解采用ArrayDeque作为队列效率优于LinkedList。总结本题主要需要掌握“多源广度优先搜索”记录拓展的层数即可。