Hot 100 --- 岛屿数量

本文概览本文以LeetCode题目岛屿数量为例从二叉树的递归视角迁移到二维网格的四方向递归讲解DFS和BFS两种标记岛屿的方法一、题目二、题目分析题目要求给定一个二维网格计算岛屿的数量。‘1’ 代表陆地‘0’ 代表水什么是岛屿这是这题最容易让人困惑的地方。岛屿的定义是对于某个 ‘1’它的上下左右如果也是 ‘1’就属于同一个岛屿。但如果斜着的 ‘1’则不属于这个岛屿的一部分看下面这个例子1 1 0 1 0 1左上角的三个 1左上和右上是横向相邻连通左上和左下是纵向相邻连通所以这三个 1 属于同一个岛屿右下角的 1和左下的 1 是斜着相邻但斜方向不算连通所以它是一个独立的岛屿最终这个网格有 2 个岛屿。关键就是只有上下左右方向相邻的 1 才算连通斜方向不算理解了岛屿的定义后这题其实和前面做过的二叉树是同一个套路二叉树二叉网格从当前节点出发的方向左、右上、下、左、右遍历方式递归左右子树递归上下左右防止重复访问天然有向父→子需要手动标记二叉树从父节点往子节点走天然不会走回去。但二维网格四个方向走来走去会重复访问同一个格子所以必须标记已访问的格子整体思路遍历整个网格每遇到一个新的 ‘1’就代表发现了一个新岛屿count1然后把这个岛屿的所有陆地都标记掉变成 ‘0’以后再遍历到就不算了。标记的方法有两种DFS 和 BFS思路概览方法一DFSclassSolution{// 岛屿数量privateintcount0;// 上下左右privatefinalint[][]dirs{{1,0},{-1,0},{0,-1},{0,1}};// 长宽privateintrows,cols;publicintnumIslands(char[][]grid){if(gridnull||grid.length0){return0;}rowsgrid.length;colsgrid[0].length;for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){dfs(grid,i,j);count;}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){if(i0||irows||j0||jcols||grid[i][j]0){return;}// 标记为已访问过grid[i][j]0;// 递归访问上下左右for(int[]dir:dirs){intnewRowidir[0];intnewColjdir[1];dfs(grid,newRow,newCol);}}}方法二BFSclassSolution{// 岛屿数量privateintcount0;// 上下左右privatefinalint[][]dirs{{1,0},{-1,0},{0,-1},{0,1}};// 长宽privateintrows,cols;publicintnumIslands(char[][]grid){if(gridnull||grid.length0){return0;}rowsgrid.length;colsgrid[0].length;for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){bfs(grid,i,j);count;}}}returncount;}privatevoidbfs(char[][]grid,inti,intj){Queueint[]queuenewLinkedList();// 入队时就标记防止重复加入grid[i][j]0;queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]curqueue.poll();introwcur[0];intcolcur[1];// 遍历上下左右for(int[]dir:dirs){intnewRowrowdir[0];intnewColcoldir[1];if(newRow0newRowrowsnewCol0newColcolsgrid[newRow][newCol]1){// 入队时就标记为已访问grid[newRow][newCol]0;queue.offer(newint[]{newRow,newCol});}}}}}思路简要说明建议DFS和BFS都掌握这是入门图类型算法题的好题目两种方法的外层逻辑完全一样遍历网格遇到 ‘1’ 就 count1 并把整个岛屿标记掉。区别只在标记岛屿的方式DFS遇到 ‘1’递归它的上下左右一路走到头和二叉树的先序遍历一个道理BFS遇到 ‘1’把它周围的 ‘1’ 全部加入队列一层层往外扩散BFS 的关键细节标记时机必须是入队时不是出队时。如果出队才标记同一个格子会被重复加入队列导致死循环三、思路详解第一步从二叉树到二维网格前面做了很多二叉树的题目核心就是从一个节点出发递归访问它的左右子树。这题其实是一样的思路只是方向从 2 个变成了 4 个二叉树2个方向 二维网格4个方向 节点 上 / \ | 左 右 左 — (i,j) — 右 | 下二叉树的递归模板privatevoiddfs(TreeNodenode){if(nodenull)return;// 出口// 处理当前节点dfs(node.left);// 递归左dfs(node.right);// 递归右}二维网格的递归模板privatevoiddfs(char[][]grid,inti,intj){if(越界||grid[i][j]0)return;// 出口grid[i][j]0;// 标记已访问// 递归上下左右for(int[]dir:dirs){dfs(grid,idir[0],jdir[1]);}}结构完全一样区别只有两点出口条件多了越界判断以及递归前多了一步标记已访问第二步为什么需要标记二叉树从父节点往子节点走是单向的天然不会走回去。但二维网格四个方向是互相的——你从 (0,0) 走到 (0,1)(0,1) 的左边方向又指回 (0,0)如果不标记就会无限来回走不标记的情况 (0,0) → 访问右边 (0,1) (0,1) → 访问左边 (0,0) ← 又回去了 (0,0) → 访问右边 (0,1) ← 又回来了 ... 死循环所以每次访问一个格子必须立刻把它变成 ‘0’这样后续任何方向走到这里都会直接 return第三步DFS 标记过程图解以这个 4×5 网格为例1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1遍历到 (0,0)发现 ‘1’count1开始 DFS 标记① 访问 (0,0)标记为 0递归上下左右 [0] 1 0 0 0 ← (0,0) 标记 1 1 0 0 0 ② 上越界下到 (1,0)标记为 0 [0] 1 0 0 0 [0] 1 0 0 0 ← (1,0) 标记 ③ (1,0) 的下越界左越界右到 (1,1)标记为 0 0 1 0 0 0 [0][0]0 0 0 ← (1,1) 标记 ④ (1,1) 的上是 (0,1)标记为 0 [0][0]0 0 0 ← (0,1) 标记 0 [0]0 0 0 ⑤ (0,1) 的上下左右要么越界要么是 0递归结束 标记后的网格 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1继续遍历到 (2,2)发现 ‘1’count2DFS 标记它单个格子继续遍历到 (3,3)发现 ‘1’count3DFS 标记 (3,3) 和 (3,4)最终 count 3第四步BFS 标记过程图解BFS 的思路不是一路走到头而是一层层往外扩散。以 (0,0) 为例初始 [1] 1 0 0 0 ← (0,0) 入队并标记为 0 1 1 0 0 0 第一轮出队 (0,0)把周围的 1 入队并标记 [0][1]0 0 0 ← (0,1) 入队标记 [1] 1 0 0 0 ← (1,0) 入队标记 队列[(0,1), (1,0)] 第二轮出队 (0,1)周围没有未标记的 1 出队 (1,0)把 (1,1) 入队并标记 0 [0]0 0 0 [0][1]0 0 0 ← (1,1) 入队标记 队列[(1,1)] 第三轮出队 (1,1)周围没有未标记的 1 队列为空BFS 结束第五步BFS 的关键细节——入队时标记还是出队时标记这是 BFS 写法里最容易踩坑的地方错误写法出队时标记// ❌ 错误出队时才标记while(!queue.isEmpty()){int[]curqueue.poll();grid[cur[0]][cur[1]]0;// 出队才标记for(int[]dir:dirs){intnewRowcur[0]dir[0];intnewColcur[1]dir[1];if(越界判断grid[newRow][newCol]1){queue.offer(newint[]{newRow,newCol});// 没有标记}}}为什么错看这个例子初始queue [(0,0)]grid[0][0] 还是 1 第一轮出队 (0,0)标记为 0 检查周围发现 (0,1) 和 (1,0) 是 1加入队列 queue [(0,1), (1,0)] 第二轮出队 (0,1)标记为 0 检查周围发现 (1,1) 是 1加入队列 同时 (0,0) 已经是 0 了跳过 queue [(1,0), (1,1)] 第三轮出队 (1,0)标记为 0 检查周围(0,0) 是 0 跳过 但 (1,1) 还是 1还没出队没被标记 于是又把 (1,1) 加入队列 queue [(1,1), (1,1)] ← 重复了同一个格子被加入队列多次每个出队时又会把周围的 ‘1’ 加入队列最终导致死循环正确写法入队时标记// ✅ 正确入队时就标记grid[newRow][newCol]0;// 入队前立刻标记queue.offer(newint[]{newRow,newCol});入队时就标记成 ‘0’后面其他格子检查到它时看到的是 ‘0’就不会重复加入了。一个格子只会入队一次不会死循环第六步DFS vs BFS 对比DFSBFS数据结构递归栈队列标记时机进入函数立即标记入队时立即标记遍历顺序一路走到头再回溯一层层往外扩散空间复杂度O(rows×cols) 最坏递归深度O(rows×cols) 最坏队列长度效果完全一样完全一样两种方法只是标记岛屿的遍历方式不同最终都能把同一个岛屿的所有陆地标记掉不影响 count 的计算复杂度分析时间复杂度O(rows×cols)每个格子最多被访问一次空间复杂度O(rows×cols)DFS 最坏递归深度BFS 最坏队列长度