LeetCode 200 - Number of Islands 解題筆記

Posted on Edited on In Views: Word count in article: 761 Reading time ≈ 1 mins.

題目基本資訊

  • 題目名稱： Number of Islands
  • 題號編號： 200
  • 難度：Medium
  • 題目分類： Graph
  • 連結：LeetCode 題目連結

題目描述

給你一個由 0（水）和 1（陸地）組成的 2D 地圖，請你找出這張地圖中總共有幾個「島嶼」。

  • 島嶼的定義是：水平或垂直相連的陸地
  • 對角線不算相連
  • 四周預設都是水
  • 你要回傳島嶼的數量（也就是「有幾塊互相連接的陸地」）

範例輸入：

1
2
3
4
5
6
7
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
輸出結果：3

概念邏輯

為什麼這題適合用 DFS？
可以把整張地圖想像成一個「圖」，每個格子是一個節點，四個方向是它的鄰居。

當發現一個 1（陸地），就用 DFS 從這個點出發，把整個連在一起的陸地都「走一遍」。

每當從一個新的 1 開始走 DFS，表示發現一座新的島嶼。

也就是說：使用 DFS 的三個理由

  • 結構類似圖（2D grid）時，適合用來遍歷鄰接節點。
  • 遇到遞迴邏輯（例如連通區塊）時自然好寫。
  • 可以用 stack 或遞迴模擬，程式碼簡潔。

所以這題的核心是：

找有幾個連通區塊（connected components）

🚩DFS 適用時機

適用情境 說明
處理「圖」的遍歷 如：走迷宮、連通區塊、路徑搜尋
解構巢狀關係 如：遞迴樹結構（preorder, postorder）
模擬踩過所有相連節點 如：這題的島嶼問題

Pseudo Code

1
2
3
4
5
6
7
8
9
10
11
for 每一格 (r, c):
    如果是 '1':
        count += 1
        dfs(r, c)

function dfs(r, c):
    如果 (r, c) 超出邊界 或不是 '1':
        return

    將 (r, c) 標記為已訪問（變成 '0'）
    往上下左右四個方向繼續 dfs

JavaScript 程式碼（DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (
      r < 0 || c < 0 ||
      r >= rows || c >= cols ||
      grid[r][c] === '0'
    ) {
      return;
    }

    grid[r][c] = '0'; // 標記為已拜訪

    dfs(r - 1, c); // 上
    dfs(r + 1, c); // 下
    dfs(r, c - 1); // 左
    dfs(r, c + 1); // 右
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
};

時間與空間複雜度分析

1. 時間複雜度：O(m * n)

每一個格子最多只會拜訪一次。

地圖大小為 m x n，所以最多處理 m * n 次格子。

2. 空間複雜度：O(m * n)（最壞情況）

使用的是 遞迴 DFS，遞迴深度與島的大小有關。

最壞情況：地圖上整塊是連著的陸地，遞迴會走到 m * n 的深度（JS call stack 可能爆）。

實際空間會取決於島的最大連通面積。

解題過程出現的錯誤

  • 若遇到 Maximum call stack size exceeded，大機率是忘記將走過的格子設為 ‘0’（標記已拜訪）。