LeetCode(#200) 岛屿数量问题-题解笔记 (Python)

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

方法一：深度优先搜索 (DFS)

目标：给定一个二维网格，求 '1' 的数量，其中，竖向和横向上相邻的 '1' 被视为一个。

思路：首先想到的是最简单的方法，遍历整个网格，遇到为 '1' 的网格，向它的上下左右四个方向深入搜索。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        # 计数器初始化为 0
        cnt = 0
        rowsn = len(grid)
        colsn = len(grid[0])
        def dfs(i,j):
            # 边界条件
            if not ( 0<=i<rowsn and 0<=j<colsn and grid[i][j] == '1'):
                return
            # 记录访问过的网格
            grid[i][j] = '2'
            # 遍历网格的四个邻居
            dfs(i+1,j)
            dfs(i-1,j)
            dfs(i,j+1)
            dfs(i,j-1)
        # 遍历整个网格
        for i in range(rowsn):
            for j in range(colsn):
                if  grid[i][j] == '1':
                    cnt += 1
                    dfs(i,j)
        return cnt

时间复杂度： \(O(MN)\)，其中，\(M,N\) 分别为网格的行数和列数，也既网格的数量大小。

空间复杂度： \(O(MN)\)，DFS 的最大层数也为网格的数量大小。

方法二：广度优先搜索(BFS)

类似地，可以想到，DFS 的解法往往会伴随着 BFS 的解法。

在这里，使用队列作为辅助，实现本题的 BFS 解法。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        # 计数器初始化为 0
        cnt = 0
        rowsn = len(grid)
        colsn = len(grid[0])
        # 上下左右四个邻居
        choices = ((1,0),(-1,0),(0,1),(0,-1))

        def bfs(i,j):
            # 使用双端队列，优化时间效率
            q = collections.deque()
            q.append((i,j))
            while q:
                i, j = q.popleft()
                if 0 <= i < rowsn and 0 <= j < colsn and grid[i][j] == '1':
                    grid[i][j] = '2'
                    for di, dj in choices:
                        q.append((i+di,j+dj))

        # 遍历整个网格
        for i in range(rowsn):
            for j in range(colsn):
                if  grid[i][j] == '1':
                    cnt += 1
                    bfs(i,j)
        return cnt

时间复杂度： \(O(MN)\)

空间复杂度： \(O(min(M,N))\)，在最坏情况下，队列的大小为\(min(M,N)\)

方法三：并查集

连通性问题一般可以想到使用「并查集」的数据结构。

关于并查集的相关知识，可以查看 Robert Sedgewick 所著的《算法（第4版）》一书中的第一章第五节。

class UF:
    def __init__(self, n):
        self.count = n
        self.parent = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def union(self, p, q):
        rootp = self.find(p)
        rootq = self.find(q)
        if rootp == rootq: return

        # 平衡性优化, 基于 size
        if self.size[rootp] > self.size[rootq]:
            self.parent[rootq] = rootp
            self.size[rootp] += self.size[rootq]
        else:
            self.parent[rootp] = rootq
            self.size[rootq] += self.size[rootp]
        self.count -= 1

    def find(self, x):
        while x != self.parent[x]:
            # 路径压缩
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    
    def is_connected(self, p, q):
        return self.find(p) == self.find(q)


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        rowsn = len(grid)
        colsn = len(grid[0])
        uf = UF(rowsn*colsn)
        # 统计'1'的个数：
        cnt = 0
        for i in range(rowsn):
            for j in range(colsn):
                if grid[i][j] == '1': cnt += 1
        uf.count = cnt
        for i in range(rowsn):
            for j in range(colsn):
                if grid[i][j] == '1':
                    # 标记探索过的网格
                    grid[i][j] = '2'
                    # 只需向右下方查看合并
                    for di, dj in ((0,1), (1,0)):
                        ii = i + di
                        jj = j + dj
                        if 0 <= ii < rowsn and 0 <= jj < colsn and grid[ii][jj] == '1':
                            uf.union(i*colsn+j, ii*colsn+jj)
        return uf.count

空间复杂度： \(O(MN)\)

时间复杂度： \(O(log* n)\)，证明略，\(log*n\) 为Iterated logarithm