Sui Xin's Blog

[LeetCode]200. 岛屿数量（Number of Islands）

Posted on In Disqus:

题目描述

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3

解题思路

  1. 方法一：深度优先搜索（DFS）。
  2. 方法二：广度优先搜索（BFS）。可以避免 DFS 时的回溯。
  3. 方法三：并查集。如果当前节点是“陆地”，尝试与周围的“陆地”合并；如果是“水域”，把所有的水域合并在一起，因此设置一个虚拟节点，用来连结所有的“水域”。注：使用此方法时只需遍历两个方向即可（向右+向下）；最后返回的岛屿数量需要减去虚拟的“水域”岛屿。

代码

Python 3.6

方法一：深度优先搜索（DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def __init__(self):
        self.steps = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]
        res = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1" and not visited[i][j]:
                    self.walk(grid, rows, cols, i, j, visited)
                    res += 1
        return res
    
    def walk(self, grid, rows, cols, i, j, visited):
        visited[i][j] = True
        for step in self.steps:
            x, y = i + step[0], j + step[1]
            if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1" and not visited[x][y]:
                self.walk(grid, rows, cols, x, y, visited)

执行用时：196 ms
内存消耗：15.2 MB

方法二：广度优先搜索（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def __init__(self):
        self.steps = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]
        res = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1" and not visited[i][j]:
                    res += 1
                    queue = [(i, j)]
                    while queue:
                        cur_i, cur_j = queue.pop(0)
                        for step_x, step_y in self.steps:
                            x, y = cur_i + step_x, cur_j + step_y
                            if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1" and not visited[x][y]:
                                queue.append((x, y))
                                visited[x][y] = True
        return res

执行用时：204 ms
内存消耗：14.7 MB

方法三：并查集

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        class UnionFind():
            def __init__(self, n):
                self.count = n  # 用来记录当前不交集合的数量
                self.parent = list(range(n))
                self.rank = [1] * n
            
            def get_count(self):
                return self.count
            
            def find(self, p):
                while p != self.parent[p]:
                    self.parent[p] = self.parent[self.parent[p]]
                    p = self.parent[p]
                return p
                
            def is_connected(self, p, q):
                return self.find(p) == self.find(q)
            
            def union(self, p, q):
                root_p = self.find(p)
                root_q = self.find(q)
                if root_p == root_q:
                    return
                if self.rank[root_p] == self.rank[root_q]:
                    self.parent[root_p] = root_q
                    self.rank[root_q] += 1
                elif self.rank[root_p] < self.rank[root_q]:
                    self.parent[root_p] = root_q
                else:
                    self.parent[root_q] = root_p
                self.count -= 1
                    
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        
        def get_flatten_index(x, y):
            return x * cols + y
        
        dummy_node = rows * cols
        UF = UnionFind(dummy_node + 1)
        
        steps = [(1, 0), (0, 1)]
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "0":
                    UF.union(get_flatten_index(i, j), dummy_node)
                else:
                    for step_x, step_y in steps:
                        x, y = i + step_x, j + step_y
                        if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1":
                            UF.union(get_flatten_index(i, j), get_flatten_index(x, y))
        return UF.get_count() - 1

执行用时 : 432 ms
内存消耗 : 17.3 MB

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集有三种基本操作：获得根节点、判断两节点是否连通、将两不连通的节点相连（相当于将两节点各自的集合合并）。

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
class UnionFind():
    def __init__(self, n):
        self.parent = list(range(n))  # 节点的父节点
        self.rank = [1] * n  # 节点所在树的深度
    
    def find(self, p):
        # 找到某个节点的父节点
        while p != self.parent[p]:
            # 为了后续节省时间，直接将该节点与其最远的祖先（当前集合的根节点）相连
            self.parent[p] = self.parent[self.parent[p]]
            p = self.parent[p]
        return p
        
    def is_connected(self, p, q):
        # 判断两个节点是否相连（属于同一个集合）
        return self.find(p) == self.find(q)
    
    def union(self, p, q):
        # 将两节点联通
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p == root_q:
            return
        if self.rank[root_p] == self.rank[root_q]:
            # 若两节点所在的树深度相同，则任意连接一个节点p到另一个节点q上作为子节点，同时将q的树的深度+1
            self.parent[root_p] = root_q
            self.rank[root_q] += 1
        elif self.rank[root_p] < self.rank[root_q]:
            # 将树的深度小的那个节点连接到深度大的那个节点上作为子节点
            self.parent[root_p] = root_q
        else:
            self.parent[root_q] = root_p

参考

https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l
https://segmentfault.com/a/1190000013805875

Related Posts