200. 岛屿数量 (Number of Islands)

🎯 问题描述（来源于LeetCode）

描述：给你一个 m x n 的二维二进制网格 grid，其中 1 代表陆地，0 代表水域。岛屿总是被水域包围，并且通过水平方向或垂直方向上相邻的陆地连接而成。你可以假设网格的四条边均被水域包围。

说明：请你计算网格中岛屿的数量。

  • 示例：
  • 示例 1：
    1
    2
    3
    4
    5
    6
    7
    8
    输入: grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    输出: 1
    解释: 所有的 '1' 都是相连的，构成一个岛屿。
  • 示例 2：
    1
    2
    3
    4
    5
    6
    7
    8
    输入: grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    输出: 3
    解释: 有三个独立的岛屿。

💻 解题思路

思路1：深度优先搜索 (DFS) 沉岛法

思路描述

这是一个典型的图遍历问题。核心思想是：

  1. 遍历网格：使用双重循环遍历每一个格子。
  2. 发现陆地：当遇到值为 '1'（陆地）的格子时，说明发现了一个新的岛屿，计数器 count 加 1。
  3. 淹没岛屿：立即启动 DFS，从该点开始，递归地将所有与之相连的 '1' 都标记为 '0'（或者使用 Visited 数组标记）。这一步称为“沉岛”，目的是防止后续遍历重复计算该岛屿的其他部分。
  4. 继续遍历：沉没整个岛屿后，继续遍历剩下的网格。

思路1：代码实现

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
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
            
        n, m = len(grid), len(grid[0])
        count = 0

        def dfs(i, j):
            # 边界检查和终止条件
            if i < 0 or i >= n or j < 0 or j >= m or 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 i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    dfs(i, j) # 触发 DFS，沉没整个岛屿
                    count += 1 # 岛屿数量 +1
        return count

思路1：📊 性能分析

提交结果
  • 运行时间：242ms击败72.58%
  • 内存消耗：21.50MB击败20.16%
复杂度验证
  • 时间复杂度：O(M×N)O(M \times N)
    • 其中 MM 和 NN 分别是网格的行数和列数。最坏情况下，网格全是陆地，我们需要遍历每一个格子一次。
  • 空间复杂度：O(M×N)O(M \times N)
    • 主要是递归调用栈的深度。在最坏情况下（整个网格是一个大岛屿），递归的深度会达到 M×NM \times N。

思考

  1. 为什么修改了原数组？ 为了节省空间，直接将访问过的 '1' 改为 '0' 是一种常见的技巧。如果在工程实践中不能修改原数据，应该定义一个同等大小的布尔型 visited 数组来记录状态。
  2. 递归边界：注意 grid[i][j] != '1' 这个条件包含了 grid[i][j] == '0'（海水）和越界的情况处理，是 DFS 的核心剪枝逻辑。