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')，这样就能确保每个岛屿只被计数一次。

具体步骤：

1. 初始化岛屿计数器为0
2. 遍历网格的每个单元格
3. 当遇到'1'时：
   • 增加岛屿计数器
   • 从这个'1'开始进行DFS，把所有相连的'1'都标记为'0'
4. 最终返回计数器值

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'都是一个独立的集合
2. 遍历网格，将相邻的'1'合并到同一个集合
3. 最终统计独立集合的数量

并查集的实现需要处理二维到一维的坐标映射，以及路径压缩等优化技巧。虽然代码量较大，但在某些情况下性能更好。

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(r+1, c) dfs(r-1, c) dfs(r, c+1) 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

优化点：

1. 边界检查放在DFS函数开头，避免重复判断
2. 直接修改原网格来标记访问，节省额外空间
3. 递归前先修改当前值为'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++; Queue<int[]> 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[row+1][col] == '1') { queue.add(new int[]{row+1, col}); grid[row+1][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][col+1] == '1') { queue.add(new int[]{row, col+1}); grid[row][col+1] = '0'; } } } } } return count; }

提示：BFS实现中，在将邻居加入队列时立即将其标记为'0'很重要，这样可以避免同一个位置被多次加入队列。

3.3 复杂度分析

假设网格大小为M×N：

• 时间复杂度：O(M×N)，因为每个单元格最多被访问一次
• 空间复杂度：
  • DFS：O(M×N)最坏情况(全部是陆地时递归深度)
  • BFS：O(min(M,N))，因为队列中最多同时存储网格对角线长度的元素

4. 常见错误与边界情况

4.1 新手常犯的错误

1. 忘记处理空输入：直接开始遍历而不检查grid是否为空
2. 对角线相邻误判：题目明确只考虑上下左右四个方向
3. 修改原数组的副作用：在实际工程中可能需要保留原数组
4. 访问越界：在DFS/BFS中未正确检查数组边界
5. 重复计数：没有正确标记已访问的单元格

4.2 重要边界情况测试

好的解法应该能处理以下特殊情况：

1. 空网格([])
2. 全'0'的网格
3. 全'1'的网格
4. 单行或单列网格
5. 大型网格(测试性能)
6. 只有一个岛屿的网格
7. 每个'1'都是独立岛屿的网格

4.3 调试技巧

当你的解法出现问题时：

1. 先用小网格(如2x2)手动模拟你的算法
2. 打印出每次DFS/BFS前后的网格状态
3. 检查岛屿计数器是否在正确时机增加
4. 确保所有相连的'1'都被正确标记

5. 实际应用与变种问题

5.1 实际应用场景

岛屿数量问题看似简单，但其算法思想在以下场景中有实际应用：

1. 图像处理中的连通区域分析
2. 社交网络中的群体检测
3. 地图服务中的地块划分
4. 电路板上的连通区域检查
5. 医学图像中的病灶区域识别

5.2 常见变种问题

掌握了基础解法后，可以尝试以下变种：

1. 统计岛屿的最大面积(LeetCode 695)
2. 统计封闭岛屿数量(LeetCode 1254)
3. 统计不同形状岛屿的数量
4. 允许对角线相邻的岛屿计数
5. 动态岛屿问题(网格会随时间变化)

5.3 性能优化进阶

对于特别大的网格，可以考虑：

1. 并行处理：将网格分块，分别计算后合并结果
2. 增量计算：当网格有小范围变化时，只重新计算受影响区域
3. 多线程BFS：使用工作窃取队列实现并行BFS

6. 个人解题心得

在多次解答这个问题后，我总结出几点经验：

1. DFS的递归写法虽然简洁，但在面试中最好同时掌握迭代写法，因为面试官可能会问递归的缺点
2. 在BFS实现中，将节点加入队列时立即标记为已访问很重要，可以避免重复入队
3. 并查集解法虽然代码量大，但在某些变种问题(如动态连接问题)中更有优势
4. 实际工程中，如果输入数据很大，可能需要使用更节省空间的访问标记方法
5. 这个问题是理解图遍历算法的绝佳起点，掌握后可以轻松应对更复杂的网格类问题

最后一个小技巧：在面试中，可以先从最简单的DFS解法开始，然后讨论其局限性和优化方向，这样能展示出你思考问题的全面性。