LeetCode 200. 岛屿数量
目录
题目描述
题意分析
输入是一张只由字符
'1'和'0'组成的二维网格，'1'是陆地，'0'是水；要输出的是岛屿的个数。而「岛屿」的定义是一片彼此相连的陆地，这里的「相连」只承认上、下、左、右四个方向，斜对角贴着不算相连。所以左上角和右下角对角相邻的两个陆地格，是两座岛而不是一座——这一条几乎是本题所有错误答案的源头。把定义再抽象一层：网格本身就是一张隐式图。每个陆地格子是图上的一个节点，两个四方向相邻的陆地格子之间连一条无向边，水格子不参与这张图。于是「数岛屿」被翻译成一个非常标准的问题——数这张图里有多少个连通分量。图虽然没有以邻接表的形式给出，但节点的编号（行列下标）和求邻居的方法（下标加一减一）都是现成的，不需要真的建图，这也是网格类题目的通用套路。
题面还透露了两个信号。第一，矩阵里存的是字符而不是整数，判断陆地必须写
'1'而不是1。第二，题目只要求返回一个数量，没有任何地方要求返回后原网格保持不变，这给「直接在输入网格上做已访问标记」留下了空间——是否真的这么做，取决于你能否接受破坏输入。边界情形要提前想清楚：整张网格全是水，答案是
0；整张网格全是陆地，答案是1；只有一行或只有一列的退化网格；以及只有一个格子的网格。此外，位于首行、末行、首列、末列的格子邻居数量不足四个，任何访问邻居的代码都必须先做下标合法性检查，否则会用越界下标读数组。
解法：BFS 原地淹没
核心思路
把网格看作一张图，陆地是节点，上下左右相邻的陆地之间有边。扫描网格，每遇到一个未访问的陆地，岛屿数加一，再用 BFS 把整座岛标记为已访问。
直接把访问过的
'1'改成'0'，无需额外的visited数组。陆地必须在入队时标记，否则可能被多个邻居重复入队。
解题步骤
- 逐行扫描网格，跳过水域。
- 遇到
'1'时，岛屿数加一，将该格子改成'0'后入队。- 不断取出队首，检查其上下左右四个邻居。
- 合法且为陆地的邻居立即改成
'0'并入队。- 队列为空时，这座岛已处理完；扫描结束后返回岛屿数。
代码实现
import java.util.ArrayDeque;
class Solution {
private static final int[][] DIRECTIONS = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] != '1') {
continue;
}
islands++;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {row, col});
grid[row][col] = '0';
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] direction : DIRECTIONS) {
int nextRow = cell[0] + direction[0];
int nextCol = cell[1] + direction[1];
if (nextRow < 0 || nextRow >= rows
|| nextCol < 0 || nextCol >= cols
|| grid[nextRow][nextCol] != '1') {
continue;
}
grid[nextRow][nextCol] = '0';
queue.offer(new int[] {nextRow, nextCol});
}
}
}
}
return islands;
}
}
func numIslands(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
directions := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
islands := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if grid[row][col] != '1' {
continue
}
islands++
queue := [][2]int{{row, col}}
grid[row][col] = '0'
for head := 0; head < len(queue); head++ {
cell := queue[head]
for _, direction := range directions {
nextRow := cell[0] + direction[0]
nextCol := cell[1] + direction[1]
if nextRow < 0 || nextRow >= rows ||
nextCol < 0 || nextCol >= cols ||
grid[nextRow][nextCol] != '1' {
continue
}
grid[nextRow][nextCol] = '0'
queue = append(queue, [2]int{nextRow, nextCol})
}
}
}
}
return islands
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子最多入队、出队一次。
- 空间复杂度：$O(mn)$，最坏情况下队列可容纳同阶数量的格子。
关键点总结
- 外层扫描负责发现新岛屿，BFS 负责一次标记完整座岛。
- 入队时立即标记，保证每个陆地最多入队一次。
- 只检查上下左右四个方向，斜对角不连通。
- 代码会修改原网格；需要保留输入时应改用独立的访问数组。
易错点总结
- 把字符
'1'写成整数1。- 到出队时才标记，导致同一格子重复入队。
- 加入对角方向，错误地合并两座岛。
- 访问邻居前漏掉边界检查。
- 调用后仍复用原网格，却忽略陆地已经被改成水。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 130. 被围绕的区域 | 中等 | 反向思考：先从边界出发标出「不被围绕」的区域，再翻转其余部分 |
| 305. 岛屿数量 II | 困难 | 动态往网格里加陆地并在线输出岛屿数，需要并查集而非反复搜索 |
| 417. 太平洋大西洋水流问题 | 中等 | 从两组边界分别反向搜索再取交集，输出的是坐标集合而非计数 |
| 463. 岛屿的周长 | 简单 | 只有一座岛，统计的是与水或网格边界相接的边数 |
| 542. 01 矩阵 | 中等 | 多源 BFS 求每格到最近 0 的距离，必须逐层推进 |
| 547. 省份数量 | 中等 | 同样是数连通分量，但图以邻接矩阵给出，邻居不再是四方向 |
| 694. 不同岛屿的数量 | 中等 | 要把每座岛的形状序列化后去重，关心形状而不只是数量 |
| 695. 岛屿的最大面积 | 中等 | 淹没函数需要有返回值以累加面积，答案取各岛面积的最大值 |
| 733. 图像渲染 | 简单 | 只对给定起点做一次染色，没有外层扫描，也不改成水而是改成新色 |
| 827. 最大人工岛 | 困难 | 允许把一个 0 变 1，需先给每座岛编号记面积再枚举水格 |
| 994. 腐烂的橘子 | 中等 | 多源 BFS 求扩散轮数，必须按层出队，DFS 不再等价 |
| 1020. 飞地的数量 | 中等 | 数的是走不出边界的陆地格子总数，而不是连通分量个数 |
| 1254. 统计封闭岛屿的数目 | 中等 | 同样数岛但要排除接触边界的，淹没时需额外返回「是否触边」 |
| LCR 105. 岛屿的最大面积 | 中等 | 695 的同题换号，求最大面积而非数量 |
| 面试题 16.19. 水域大小 | 中等 | 统计每片水域的大小并排序输出，且连通性按八方向判定 |