[LeetCode]200. 岛屿数量(Number of Islands)

题目描述

给定一个由 ‘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