解决岛屿数量问题:并查集、DFS
岛屿数量
leetcode:200
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例:
输入:
11110
11010
11000
00000
输出: 1
解法一:DFS
染色法是一种简单高效的回溯法。
使用染色法可以重置访问过的数据,本次染色可以上下左右判断。
每次进入 DFS 都要记录次数,DFS 完成的唯一功能就是染色。
染色的缺点是数据已经不再是原有的数据了,如果需要原始数据,记得备份。
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
count = 0
m, n = len(grid), len(grid[0])
def DFS(i, j):
grid[i][j] = '0'
for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
x, y = i+dx, j+dy
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
DFS(x, y)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
DFS(i, j)
return count
并查集
并查集是另外一种解法,其难点在于构建并查集本身。
并查集介绍
并查集(union & find):是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。
有两个必须要实现的方法:
- Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union:将两个子集合并成同一个集合。
并查集实现起来并不困难,伪代码如下:
function MakeSet(x)
x. parent:=x
function Find(x)
if x. parent==x
return x
else
return Find(x. parent)
function Union(x,y)
xRoot:=Find(x)
yRoot:=Find(y)
xRoot. parent:=yRoot
其中:
集合的根结点(就是俗称的顶头上司),是自己指向自己的。
普通结点指向自己的上级。指向问题很重要。
下图就是用并查集表示的两个集合。
并查集的优化
并查集有两种优化方法:
-
按 rank(等级、级别)优化:在合并时优化。
rank 就相当于二叉树的深度,我们都希望深度尽可能少,以便查询时能尽快找到自己的根进行判定。
合并时,rank 小的往 rank 大的上面合并。 -
路径压缩:在查找时进行的优化。
同样可以减少 rank 的值,减少层级关系,以提高效率。
解法二、并查集
使用优化后的并查集进行岛屿判定。
实现并查集的代码:
# 并查集
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m * n)
self.rank = [0] * (m * n)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
self.parent[i * n + j] = i * n + j # 降维:二维数组映射到一维数组上
self.count += 1
# 查找时路径压缩
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i]) # 以保证所有结点都指向根节点。
return self.parent[i]
# 按 rank 合并
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
if self.rank[rootx] < self.rank[rooty]:
self.parent[rootx] = rooty
elif self.rank[rootx] > self.rank[rooty]:
self.parent[rooty] = rootx
else:
self.parent[rooty] = rootx
self.rank[rootx] += 1
self.count -= 1
解释:
-
parent
表示自己的父节点(上级),在初始化的时候就要确定。Python 可以使用list
表示。 -
rank
一般的初始值都是为 0 的list
,表示尚未合并过结点。 -
count
用于统计集合的数量,随着合并加多,数值随之减小。 -
find()
和union()
是进行优化后代码,所有的并查集问题都可以直接用。find()
方法中自己调用了自己。合并集合时都是合并在根结点上的,根据情况,选择是否要更新rank
,而count
是肯定要减少的。另外要注意if
的判定条件。
主体代码:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
uf = UnionFind(grid)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1': # 不染色也可以解决该问题。
grid[i][j] = '0' # 染色能够减少以后的大量 union 判断。以保证合并的都是没有出现的数据。
for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
uf.union(i*n+j, x*n+y)
return uf.count
注意:
- 在解决并查集问题时,有时并不需要
count
统计集合数量。 - 平时在做题的时候,并查集的两种优化方法:查找时路径压缩、按
rank
合并,只需保留一种方法即可。
我个人建议保留路径压缩这种方法,这样连rank
都不需要定义了。这里代码没有给出,大家可以自己尝试一下。
希望对你能有帮助。
若看懂了,不妨尝试一下下面两道题:
990. 等式方程的可满足性
547. 朋友圈
本文地址:https://blog.csdn.net/weixin_43932942/article/details/107643320
下一篇: 爱得卑微啊