复盘 · LC 200 岛屿数量

题目

题号：LeetCode 200
名称：岛屿数量（Number of Islands）
难度：Medium
链接：leetcode.cn/problems/number-of-islands
今日代码：200-岛屿数量/index.js

题意

给一个 m × n 的二维网格，'1' 是陆地、'0' 是水。上下左右相邻的陆地连成一座岛，求岛屿个数。

网格非空；元素只有 '0' / '1'。
斜对角不相邻。
边界：全水、全陆、单格、细长条陆地。

涉及算法

标签	一句话
DFS / BFS	碰到未访问陆地就「淹掉」整座岛，计数 +1
矩阵搜索	四方向扩散；可用 `visited` 或原地改 `'1'→'0'`

教程对照：11 · 队列与层序思想（BFS 骨架）、19 · 递归心智与回溯框架（递归扩散）。

评价我的解法

你的思路：扫格子；遇到未访问的 '1' 就扩散标记整片连通陆地，res++。这是标准「数连通块」模板，能 AC（约 71ms / 59MB）。

我的代码（摘自 200-岛屿数量/index.js，不含本地测例）：

javascript

var numIslands = function (grid) {
  const rowLen = grid.length;
  const columnLen = grid[0].length;
  const isFindGrid = new Array(rowLen).fill([]);
  isFindGrid.forEach((_, i) => {
    isFindGrid[i] = new Array(columnLen).fill(false);
  });

  function BFS(i, j) {
    if (i < 0 || j < 0 || i >= rowLen || j >= columnLen) {
      return;
    }
    if (isFindGrid[i][j]) {
      return;
    }
    if (grid[i][j] === "0") {
      return;
    }
    isFindGrid[i][j] = true;
    BFS(i + 1, j);
    BFS(i, j + 1);
    BFS(i - 1, j);
    BFS(i, j - 1);
  }

  let res = 0;

  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < columnLen; j++) {
      const item = grid[i][j];
      if (item === "1" && !isFindGrid[i][j]) {
        BFS(i, j);
        res++;
      }
    }
  }

  return res;
};

对在哪、糙在哪：

连通块计数正确：外层双循环 + 内层四向扩散，语义清楚。
名字叫 BFS，实现是递归 DFS：面试口述会露馅；真 BFS 要用队列。递归在极大网格可能栈溢出（本题规模通常没事）。
new Array(n).fill([]) 是坑写法：fill([]) 会让每行先指向同一个数组引用；你后面用 forEach 整行替换掉了，所以碰巧正确，但第一步本身危险，不如直接 Array.from({ length: rowLen }, () => Array(columnLen).fill(false))。
额外 isFindGrid：时间和空间都是 O(mn)；原地把陆地改成 '0'（沉岛）可省掉 visited，内存通常更好。
提交偏慢/偏费内存：和「多一张布尔矩阵 + 递归」一致，方向对，实现未压到最省。

小结：套路选对了，能稳定过题；下一步把「DFS 沉岛」和「队列 BFS」各默写一遍，并改掉 fill([]) 习惯。

最佳题解

原地沉岛 DFS（空间更省、代码更短）：

javascript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;

  function dfs(i, j) {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== "1") return;
    grid[i][j] = "0";
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(i, j);
      }
    }
  }
  return count;
};

时间 O(mn)，空间 O(mn) 最坏递归栈（无额外 visited）。
为何更优：少一张矩阵；边界与水域统一用 !== "1" 判断；命名与实现一致。

若题目禁止改原数组，再用独立 visited，或 BFS 队列版（适合强调层序/队列模板时）。

关联题目

题	为何相关
695. 岛屿的最大面积	同一 DFS，计数改成累加面积
463. 岛屿的周长	网格陆地边界统计
130. 被围绕的区域	从边界 DFS/BFS「标记再翻转」
994. 腐烂的橘子	网格多源 BFS，练真队列

一句话带走

数岛屿：遇到 '1' 就 DFS/BFS 淹掉整片，每淹一次 +1；面试先说清 DFS 还是 BFS，别名字和实现对不上。

复盘 · LC 200 岛屿数量 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​