房产网签查询,网站建设seo虾哥网络,建立网站的几个步骤,重要新闻文章目录 1. 并查集概念1.1 理解并查集#xff1a;简介与应用场景1.2 Python 实现并查集及优化策略1.3 扁平化栈实现1.4 分析并查集的时间复杂度 2. 情侣牵手3. 相似字符串4. 岛屿数量 如果想了解并查集基础推荐去看左程云大神的算法讲解#xff0c;非常不错#xff0c;b站和… 文章目录 1. 并查集概念1.1 理解并查集简介与应用场景1.2 Python 实现并查集及优化策略1.3 扁平化栈实现1.4 分析并查集的时间复杂度 2. 情侣牵手3. 相似字符串4. 岛屿数量 如果想了解并查集基础推荐去看左程云大神的算法讲解非常不错b站和油管上都有它的视频
1. 并查集概念
1.1 理解并查集简介与应用场景
概述 并查集Disjoint Set是一种用于处理集合合并和查询等问题的数据结构。
并查集的作用
解决元素分组与连接问题用于图论中的最小生成树算法、连通性问题、网络分区等
1.2 Python 实现并查集及优化策略
class UnionFind:def __init__(self, n):# 初始化时每个元素的父节点为自己self.parent list(range(n))# 初始化时每个树的深度为0也可以设置为1self.rank [0] * n# 查找操作扁平化def find(self, x):if self.parent[x] ! x: # 如果当前节点的父节点不是自己说明不是根节点# 路径压缩将当前节点直接连接到根节点self.parent[x] self.find(self.parent[x])return self.parent[x] # 返回根节点的索引# 合并操作小挂大def union(self, x, y):root_x self.find(x) # 找到元素 x 的根节点root_y self.find(y) # 找到元素 y 的根节点if root_x ! root_y: # 如果两个元素不在同一个集合中if self.rank[root_x] self.rank[root_y]: # 如果树的深度秩小于另一个树# 将较浅的树的根节点连接到较深的树的根节点self.parent[root_x] root_yelif self.rank[root_x] self.rank[root_y]:self.parent[root_y] root_xelse: # 如果两个树深度相同则任意连接一个到另一个并将深度加一self.parent[root_y] root_xself.rank[root_x] 1优化策略
路径压缩优化扁平化在查找操作中将节点直接连接到根节点降低树的深度按秩合并优化小集合挂大集合将深度较浅的树挂在深度较深的树下保持树的平衡
1.3 扁平化栈实现
def find(self, x):# 使用栈记录路径path []# 找到根节点while self.parent[x] ! x:path.append(x)x self.parent[x]# 路径压缩将路径上的所有节点直接连接到根节点for node in path:self.parent[node] xreturn x1.4 分析并查集的时间复杂度
时间复杂度分析
查找操作Find近似为 O(1)。合并操作Union近似为 O(1)。综合时间复杂度近似为 O(α(n))其中 α(n) 是 Ackermann 函数的反函数通常视为常数级别。
2. 情侣牵手
测试链接https://leetcode.cn/problems/couples-holding-hands/ 分析
分析将每对情侣的对数看成一个集合例如第一对情侣(0,1)属于集合{0}第二对情侣(2,3)属于集合{1}...所以最开始一定有n个集合思路就是每次遍历相邻的两个人如果它们不是一对那么它们就分别属于各自的那一对将这两对的集合合并此时总集合数就少1求解答案两种1. 对于每一个集合如果里面有m对情侣那么就需要交换m-1次2. 总的集合数减去合并后的集合数例子[0,4,2,1,3,5]- 一共3对情侣3个集合{0},{1},{2}- 遍历0和40//2 ! 4//2它们不是一对将它们的集合合并此时有2个集合{0,2},{1}- 遍历2和12//2 ! 1//2它们不是一对将它们的集合合并此时有1个集合{0,2,1}- 所以一共需要交换1. 只有1个集合这个集合有3对情侣需要交换3-12次2. 原来有3个集合现在只有1个集合需要交换3-12次代码
class UnionFind:def __init__(self, n):self.father [0] * n# 初始化集合for i in range(n):self.father[i] i# 记录集合的数量self.sets ndef find(self, x):if self.father[x] ! x:self.father[x] self.find(self.father[x])return self.father[x]def union(self, x, y):fx self.find(x)fy self.find(y)# 如果它们的father不相同说明不是一对情侣需要合并if fx ! fy:self.father[fx] fy# 合并后集合数-1self.sets - 1class Solution(object):def minSwapsCouples(self, row)::type row: List[int]:rtype: intn len(row)couple UnionFind(n // 2)for i in range(0, n - 1, 2):# 依次遍历两个人是一对情侣就不合并不是一对情侣就合并couple.union(row[i] // 2, row[i 1] // 2)return n // 2 - couple.sets3. 相似字符串
测试链接https://leetcode.cn/problems/H6lPxb/ 题目分析
1. 什么是字母异位词假如给一个字符串abc它的字母异位词有acb,bac,bca,cab,cba。当然abc也同样是它们的字母异位词2. 什么是相似给定两个字符串xy都由小写字母组成分两种情况- 如果x和y不做任何操作就相同那它们相似- 如果x和y不同交换x中任意两个字母的位置能变成y就说明x和y相似3. 什么是相似字符串组根据示例1strs[tars,rats,arts,star]- 首先它们四个各自为一组共四个组- strs[0]和strs[1]相似把它们分到一组- strs[0]和strs[2]不相似不把strs[2]加入到strs[0]那一组- strs[0]和strs[3]不相似不把strs[3]加入到strs[0]那一组- strs[1]和strs[2]相似把strs[2]加入到strs[1]那一组- strs[1]和strs[3]不相似不把strs[3]加入到strs[1]那一组- ...- strs[3]和前面的字符串都不相似自己单独为一组- 最后就分为了两个组{strs[0],strs[1],strs[2]},{strs[3]}- 很明显地就是用并查集去分组- 只要剩余的字符串与一个组内的任一字符串相似就将它们合并代码
class UnionFind:def __init__(self, n):self.father [0] * nself.size [1] * nfor i in range(n):self.father[i] iself.sets ndef find(self, x):if self.father[x] ! x:self.father[x] self.find(self.father[x])return self.father[x]# 小挂大def union(self, x, y):fx self.find(x)fy self.find(y)if fx ! fy:if self.size[fx] self.size[fy]:self.father[fy] fxself.size[fx] self.size[fy]else:self.father[fx] fyself.size[fy] self.size[fx]self.sets - 1class Solution(object):def numSimilarGroups(self, strs)::type strs: List[str]:rtype: int# 共有n个字符串n len(strs)# 每个字符串长度为mm len(strs[0])connect UnionFind(n)for i in range(n):for j in range(i 1, n):# 两两比较字符串如果它们不在同一个组中并且它们相似就合并if (connect.find(i) ! connect.find(j)):diff 0# 依次比较strs[i]和strs[j]因为strs中的字符串都互为字母异位词# 所以只需要看strs[i]和strs[j]有几个字符不一样就行了for k in range(m):if strs[i][k] ! strs[j][k]:diff 1# strs[i]要么完全和strs[j]一样要么有两个字符不同这样才满足相似的条件if diff 3:break# 如果相似就合并if diff 0 or diff 2:connect.union(i, j)return connect.sets4. 岛屿数量
测试链接https://leetcode.cn/problems/number-of-islands/ 分析
思路使用并查集的话就是先将每个1都视为1个集合如果它的上下左右也是1就合并两个集合下标转换将二维下标转换为一维下标例如下面是一个4×4的二维表坐标[i][j]转换为一维的就是i*m jm为列的数量n\m 0 1 2 30 0 1 2 31 4 5 6 72 8 9 10 113 12 13 14 15代码
class UnionFind:def __init__(self, n, m, grid):# 正常建立并查集我们只需要关注“1”就行了“0”不用管self.father [-1] * ((n - 1) * m m)self.sets 0for i in range(n):for j in range(m):if grid[i][j] 1:self.father[i * m j] i * m jself.sets 1def find(self, x):if self.father[x] ! x:self.father[x] self.find(self.father[x])return self.father[x]def union(self, x, y):fx self.find(x)fy self.find(y)if fx ! fy:self.father[fy] fxself.sets - 1class Solution(object):def numIslands(self, grid)::type grid: List[List[str]]:rtype: intn len(grid)m len(grid[0])area UnionFind(n, m, grid)for i in range(n):for j in range(m):if grid[i][j] 1:# “0”不用管的原因是因为我们合并x,y的时候xy对应的二维坐标在二维表中一定是“1”# 下面只需检查每个“1”的左上是否为1就不用上下左右全部检查了if j 0 and grid[i][j - 1] 1:area.union(i * m j, i * m j - 1)if i 0 and grid[i - 1][j] 1:area.union(i * m j, (i - 1) * m j)return area.sets
