题目描述
LeetCode 200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3学习历程（对话式思考）
第一步：理解问题核心
我的第一反应：
核心问题是如何判断岛屿的界限，找到1后应该找上下左右是否有1，找过的置为0？
关键洞察："找过的置为0" 这个技巧叫「沉没岛屿」或「标记访问」，是这类题目的核心 trick。目的是防止重复计数，同时也避免了使用额外的 visited 数组。
第二步：选择遍历方式
找到一个 '1' 后，怎么找它周围所有的 '1'？两种选择：
数据范围分析：m, n <= 300，最多 90,000 个格子。
DFS 递归深度最多 90,000 层，Java 默认栈空间可能扛不住
BFS 使用队列，空间复杂度更可控
第三步：整体算法框架
岛屿数量 = 0
遍历每个格子：
如果是 '1'：
岛屿数量 += 1
从该点开始做 DFS/BFS，把所有连通的 '1' 都变成 '0'
返回岛屿数量关键点：
外层双重循环遍历每个格子
遇到
'1'就开启一次搜索，搜索结束后该岛屿所有陆地都变'0'下次遍历时不会重复计数
第四步：BFS 执行流程详解
以网格为例：
grid = [
["1","1","0"],
["1","1","0"],
["0","0","1"]
]找到第一个岛屿起点 (0,0)：
岛屿计数
count = 1启动 BFS，把
(0,0)入队grid[0][0] = '0'（沉岛，标记已访问）
BFS 扩散（队列处理）：
队列初始: [(0,0)]
第1轮：取出 (0,0)
检查上下左右：
- 上: 越界，跳过
- 下: (1,0) 是 '1' → 入队，grid[1][0]='0'
- 左: 越界，跳过
- 右: (0,1) 是 '1' → 入队，grid[0][1]='0'
队列: [(1,0), (0,1)]
第2轮：取出 (1,0)
检查上下左右：
- 上: (0,0) 已经是 '0'
- 下: (2,0) 是 '0'
- 左: 越界
- 右: (1,1) 是 '1' → 入队，grid[1][1]='0'
队列: [(0,1), (1,1)]
第3轮：取出 (0,1)
四个方向要么越界，要么已访问
队列: [(1,1)]
第4轮：取出 (1,1)
四个方向都是 '0' 或已访问
队列: []
队列空，BFS 结束。第一个岛屿处理完毕！继续遍历：在 (2,2) 发现 '1'，count = 2，启动第二次 BFS...
第五步：边界与细节
边界判断：
if (newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length) {
continue; // 越界，跳过
}注意：
grid是char[][]，比较时用'1'而不是1入队后立即
grid[newX][newY] = '0'，防止重复入队四个方向：上
(-1,0)、下(1,0)、左(0,-1)、右(0,1)
完整代码实现
BFS 版本（推荐，更安全）
import java.util.LinkedList;
import java.util.Queue;
public class NumIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int count = 0;
int m = grid.length;
int n = grid[0].length;
// 遍历每个格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++; // 发现新岛屿
bfs(grid, i, j); // 沉掉整个岛屿
}
}
}
return count;
}
private void bfs(char[][] grid, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0'; // 起点沉岛
// 四个方向：上、下、左、右
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
for (int[] dir : directions) {
int newX = x + dir[0];
int newY = y + dir[1];
// 边界检查
if (newX < 0 || newX >= grid.length ||
newY < 0 || newY >= grid[0].length) {
continue;
}
// 是陆地就入队并沉岛
if (grid[newX][newY] == '1') {
queue.offer(new int[]{newX, newY});
grid[newX][newY] = '0';
}
}
}
}
}DFS 版本（更简洁，但有栈溢出风险）
public class NumIslandsDFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
// 边界判断 或 不是陆地
if (i < 0 || i >= grid.length ||
j < 0 || j >= grid[0].length ||
grid[i][j] != '1') {
return;
}
grid[i][j] = '0'; // 沉岛
// 递归四个方向
dfs(grid, i - 1, j); // 上
dfs(grid, i + 1, j); // 下
dfs(grid, i, j - 1); // 左
dfs(grid, i, j + 1); // 右
}
}复杂度分析
对比：
BFS：空间占用稳定，不会栈溢出，适合大规模数据
DFS：代码简洁，但极端情况下（如长条岛屿）递归深度可能超标
关键总结
解题模板（Flood Fill）
1. 遍历网格每个点
2. 找到目标值（如 '1'）
3. 计数 + 1，启动搜索（BFS/DFS）
4. 搜索中把访问过的点标记（如改成 '0'）
5. 搜索结束，继续遍历面试技巧
先讲思路：遇到网格题，先想 Flood Fill 框架
BFS vs DFS：
如果面试官问优化，提 BFS 避免栈溢出
如果追求代码短，写 DFS
边界处理：一定要检查数组越界
原数组修改：询问面试官是否可以修改原数组，如果可以就用「沉岛」技巧省空间
易错点复盘
忘记边界检查：四个方向都要判断
newX和newY是否在范围内字符比较错误：
grid[i][j] == '1'不是== 1重复计数：忘记沉岛导致同一个格子被多次计数
BFS 忘写循环：BFS 是
while(!queue.isEmpty())不是递归