题目描述
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解题思路
- 方法一:深度优先搜索(DFS)。
- 方法二:广度优先搜索(BFS)。可以避免 DFS 时的回溯。
- 方法三:并查集。如果当前节点是“陆地”,尝试与周围的“陆地”合并;如果是“水域”,把所有的水域合并在一起,因此设置一个虚拟节点,用来连结所有的“水域”。注:使用此方法时只需遍历两个方向即可(向右+向下);最后返回的岛屿数量需要减去虚拟的“水域”岛屿。
代码
Python 3.6
方法一:深度优先搜索(DFS)
1 | class Solution: |
执行用时:196 ms
内存消耗:15.2 MB
方法二:广度优先搜索(BFS)
1 | class Solution: |
执行用时:204 ms
内存消耗:14.7 MB
方法三:并查集
1 | class Solution: |
执行用时 : 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
32class 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