1. 问题概述理解岛屿数量问题的本质第一次看到LeetCode 200题岛屿数量时很多人会疑惑这到底是个什么算法问题。简单来说题目会给你一个由1(陆地)和0(水)组成的二维网格要求计算其中岛屿的数量。这里的岛屿指的是被水包围的、通过水平或垂直方向相邻的陆地组成的区域。举个例子下面这个3x3的网格[ [1,1,0], [1,0,0], [0,0,1] ]它包含2个岛屿左上角的两个相邻1组成一个岛屿右下角的单独1是另一个岛屿。这个问题看似简单但它实际上是图论中连通分量问题的二维变体也是许多实际应用的基础模型。比如在图像处理中识别连通区域、社交网络中找出独立群体等场景都可以抽象为这类问题。注意题目明确要求只考虑上下左右四个方向的相邻关系不考虑对角线相邻。这点在实际解题中非常关键很多同学一开始会忽略这个限制。2. 解题思路分析从暴力到优化2.1 基础思路深度优先搜索(DFS)最直观的解法是使用深度优先搜索。遍历整个网格当遇到一个1时就从这个位置开始进行DFS把所有相连的1都标记为已访问(比如改为0)这样就能确保每个岛屿只被计数一次。具体步骤初始化岛屿计数器为0遍历网格的每个单元格当遇到1时增加岛屿计数器从这个1开始进行DFS把所有相连的1都标记为0最终返回计数器值DFS的实现可以用递归也可以显式使用栈。递归写法更简洁但在极端情况下(如整个网格都是1)可能会导致栈溢出。2.2 广度优先搜索(BFS)方案对于大规模网格BFS可能是更好的选择因为它使用队列而非递归不会出现栈溢出问题。BFS的思路与DFS类似只是在标记相连1时使用队列来实现广度优先的遍历。BFS的伪代码queue [] 岛屿数量 0 for 每个网格单元格: if 是1: 岛屿数量 1 把当前坐标加入队列 while 队列不为空: 取出队首坐标 将其标记为0 把其上下左右未访问的1邻居加入队列2.3 并查集(Union-Find)方法对于特别大的网格或需要频繁查询的场景并查集数据结构可能更高效。基本思路是初始化时每个1都是一个独立的集合遍历网格将相邻的1合并到同一个集合最终统计独立集合的数量并查集的实现需要处理二维到一维的坐标映射以及路径压缩等优化技巧。虽然代码量较大但在某些情况下性能更好。3. 代码实现与优化技巧3.1 DFS的Python实现def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count优化点边界检查放在DFS函数开头避免重复判断直接修改原网格来标记访问节省额外空间递归前先修改当前值为0防止重复访问3.2 BFS的Java实现public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int count 0; int rows grid.length; int cols grid[0].length; for (int r 0; r rows; r) { for (int c 0; c cols; c) { if (grid[r][c] 1) { count; Queueint[] queue new LinkedList(); queue.add(new int[]{r, c}); grid[r][c] 0; while (!queue.isEmpty()) { int[] curr queue.poll(); int row curr[0], col curr[1]; if (row - 1 0 grid[row-1][col] 1) { queue.add(new int[]{row-1, col}); grid[row-1][col] 0; } if (row 1 rows grid[row1][col] 1) { queue.add(new int[]{row1, col}); grid[row1][col] 0; } if (col - 1 0 grid[row][col-1] 1) { queue.add(new int[]{row, col-1}); grid[row][col-1] 0; } if (col 1 cols grid[row][col1] 1) { queue.add(new int[]{row, col1}); grid[row][col1] 0; } } } } } return count; }提示BFS实现中在将邻居加入队列时立即将其标记为0很重要这样可以避免同一个位置被多次加入队列。3.3 复杂度分析假设网格大小为M×N时间复杂度O(M×N)因为每个单元格最多被访问一次空间复杂度DFSO(M×N)最坏情况(全部是陆地时递归深度)BFSO(min(M,N))因为队列中最多同时存储网格对角线长度的元素4. 常见错误与边界情况4.1 新手常犯的错误忘记处理空输入直接开始遍历而不检查grid是否为空对角线相邻误判题目明确只考虑上下左右四个方向修改原数组的副作用在实际工程中可能需要保留原数组访问越界在DFS/BFS中未正确检查数组边界重复计数没有正确标记已访问的单元格4.2 重要边界情况测试好的解法应该能处理以下特殊情况空网格([])全0的网格全1的网格单行或单列网格大型网格(测试性能)只有一个岛屿的网格每个1都是独立岛屿的网格4.3 调试技巧当你的解法出现问题时先用小网格(如2x2)手动模拟你的算法打印出每次DFS/BFS前后的网格状态检查岛屿计数器是否在正确时机增加确保所有相连的1都被正确标记5. 实际应用与变种问题5.1 实际应用场景岛屿数量问题看似简单但其算法思想在以下场景中有实际应用图像处理中的连通区域分析社交网络中的群体检测地图服务中的地块划分电路板上的连通区域检查医学图像中的病灶区域识别5.2 常见变种问题掌握了基础解法后可以尝试以下变种统计岛屿的最大面积(LeetCode 695)统计封闭岛屿数量(LeetCode 1254)统计不同形状岛屿的数量允许对角线相邻的岛屿计数动态岛屿问题(网格会随时间变化)5.3 性能优化进阶对于特别大的网格可以考虑并行处理将网格分块分别计算后合并结果增量计算当网格有小范围变化时只重新计算受影响区域多线程BFS使用工作窃取队列实现并行BFS6. 个人解题心得在多次解答这个问题后我总结出几点经验DFS的递归写法虽然简洁但在面试中最好同时掌握迭代写法因为面试官可能会问递归的缺点在BFS实现中将节点加入队列时立即标记为已访问很重要可以避免重复入队并查集解法虽然代码量大但在某些变种问题(如动态连接问题)中更有优势实际工程中如果输入数据很大可能需要使用更节省空间的访问标记方法这个问题是理解图遍历算法的绝佳起点掌握后可以轻松应对更复杂的网格类问题最后一个小技巧在面试中可以先从最简单的DFS解法开始然后讨论其局限性和优化方向这样能展示出你思考问题的全面性。