【LeetCodehot100】 T200：岛屿数量 T994:腐烂的橘子

T200岛屿数量题目要求给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。核心思想当我们找到第一个1时我们开始判断四周有多少个1如果是1.则全部将其改为0count。在判断过程中我们使用DFS深度优先搜索从一个点出发把所有能走到的地方全部走一遍代码实现publicclassSolution{publicintnumIslands(char[][]grid){// 防止空数组if(gridnull||grid.length0){return0;}introwsgrid.length;intcolsgrid[0].length;intcount0;// 遍历整个地图for(inti0;irows;i){for(intj0;jcols;j){// 发现陆地if(grid[i][j]1){count;// 发现一个新岛dfs(grid,i,j);// 把这个岛“淹掉”}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){introwsgrid.length;intcolsgrid[0].length;// ❗ 边界判断 遇到水就停止if(i0||irows||j0||jcols||grid[i][j]0){return;}// 把当前陆地变成水避免重复计算grid[i][j]0;// 向四个方向扩散dfs(grid,i1,j);// 下dfs(grid,i-1,j);// 上dfs(grid,i,j1);// 右dfs(grid,i,j-1);// 左}}本题感悟区分了与的区别是赋值 是比较了解的本题解法思路通过dfs算法将所有连成的岛屿变成为0进行countT994:腐烂的橘子题目要求在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。核心思路多个起点 → 同时扩散 → 一层一层推进 → 求层数BFS广度优先搜索流程初始化遍历 grid找所有 2腐烂 加入队列统计 1新鲜 freshBFS 主循环while (!queue.isEmpty() fresh 0) 条件含义还有传播源还有目标没被感染“一层一层扩散”核心int size queue.size(); 这一句的意义 锁定“这一分钟要扩散的橘子数量”然后for (int i 0; i size; i) 只处理这一层这一分钟感染逻辑if (grid[nx][ny] 1) 做三件事grid[nx][ny] 2; // 标记感染queue.offer(…); // 加入下一层fresh–; // 更新剩余数量时间推进minutes; 一层结束 1分钟代码实现classSolution{publicintorangesRotting(int[][]grid){introwsgrid.length;intcolsgrid[0].length;Queueint[]queuenewLinkedList();intfresh0;// 新鲜橘子数量// 第一步初始化for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]2){queue.offer(newint[]{i,j});// 腐烂橘子入队}elseif(grid[i][j]1){fresh;// 统计新鲜橘子}}}intminutes0;// 四个方向int[][]dirs{{1,0},{-1,0},{0,1},{0,-1}};// BFS 扩散while(!queue.isEmpty()fresh0){intsizequeue.size();// 当前这一层的数量for(inti0;isize;i){int[]curqueue.poll();intxcur[0],ycur[1];for(int[]d:dirs){intnxxd[0];intnyyd[1];// 边界判断if(nx0nxrowsny0nycolsgrid[nx][ny]1){grid[nx][ny]2;// 感染queue.offer(newint[]{nx,ny});fresh--;// 新鲜橘子减少}}}minutes;// 一层结束 1分钟}// 如果还有新鲜橘子说明感染不到returnfresh0?minutes:-1;}}本题感悟代码看了好久才看懂复习时要好好琢磨本题是BFS可以与DFS进行区分BFS特征“扩散”“同时发生”“最短时间”“几分钟后”