Python并查集大揭秘:让你在算法界呼风唤雨,秒杀一切复杂场景!

简介: 在编程与算法的广袤天地中,总有一些工具如同神兵利器,能够助你一臂之力,在复杂的问题前游刃有余。今天,我们就来深入探讨这样一件神器——Python并查集(Union-Find),看看它是如何让你在算法界呼风唤雨,轻松应对各种复杂场景的。

在编程与算法的广袤天地中,总有一些工具如同神兵利器,能够助你一臂之力,在复杂的问题前游刃有余。今天,我们就来深入探讨这样一件神器——Python并查集(Union-Find),看看它是如何让你在算法界呼风唤雨,轻松应对各种复杂场景的。

场景一:社交网络的朋友圈划分
想象一下,你正在开发一个社交网络平台,需要快速判断任意两个用户是否处于同一朋友圈中。这里,“朋友圈”的定义是基于用户之间的朋友关系形成的集合。并查集正是解决这类问题的绝佳选择。

python
class UnionFind:
def init(self, size):
self.parent = [i for i in range(size)]

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):  
    rootX = self.find(x)  
    rootY = self.find(y)  
    if rootX != rootY:  
        self.parent[rootX] = rootY  # 将一个集合的根节点指向另一个  

示例

uf = UnionFind(1000) # 假设有1000个用户
uf.union(1, 2) # 用户1和用户2成为朋友
uf.union(2, 3) # 用户2和用户3也成为朋友,现在1, 2, 3在同一朋友圈
print(uf.find(1) == uf.find(3)) # 输出True,表示用户1和用户3在同一朋友圈
场景二:岛屿数量的计算
在图像处理或游戏开发中,经常需要计算由相连像素(或格子)组成的岛屿数量。这同样可以利用并查集来解决,将每个独立的岛屿视为一个集合,通过合并相邻的像素来减少岛屿的数量。

python
class UnionFind:

# ...(与上述相同的UnionFind实现)  

def numIslands(grid):
if not grid or not grid[0]:
return 0

rows, cols = len(grid), len(grid[0])  
uf = UnionFind(rows * cols)  

# 定义四个方向的偏移量  
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  

for i in range(rows):  
    for j in range(cols):  
        if grid[i][j] == '1':  
            # 将当前位置与相邻的陆地合并  
            for dx, dy in directions:  
                ni, nj = i + dx, j + dy  
                if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':  
                    uf.union(i * cols + j, ni * cols + nj)  

# 统计根节点的数量,即岛屿的数量  
count = 0  
for i in range(rows * cols):  
    if uf.find(i) == i:  
        count += 1  

return count  

示例使用

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(numIslands(grid)) # 输出岛屿数量
结语
通过上述两个案例,我们可以看到并查集在解决实际问题时的强大能力。无论是社交网络中的朋友圈划分,还是图像处理中的岛屿数量计算,并查集都能以简洁高效的方式给出答案。掌握并查集,不仅能让你的编程技能更上一层楼,更能让你在算法界游刃有余,秒杀一切复杂场景。现在,就让我们一起,用并查集开启算法的新篇章吧!

目录
相关文章
|
22天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
41 0
|
8天前
|
数据采集 前端开发 算法
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
本文介绍了如何使用 Python 的 `requests` 库应对复杂的 HTTP 请求场景,包括 Spider Trap(蜘蛛陷阱)、SESSION 访问限制和请求频率限制。通过代理、CSS 类链接数控制、多账号切换和限流算法等技术手段,提高爬虫的稳定性和效率,增强在反爬虫环境中的生存能力。文中提供了详细的代码示例,帮助读者掌握这些高级用法。
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
|
4天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
10 3
|
7天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
18 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
11天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
19天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
43 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
9天前
|
监控 算法 数据挖掘
HyperLogLog算法有哪些应用场景呢
【10月更文挑战第19天】HyperLogLog算法有哪些应用场景呢
10 0
|
10天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
7天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
9天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。