⌈算法进阶⌋图论::并查集——快速理解到熟练运用

目录

 一、原理

1. 初始化Init

  2. 查询 find 

3. 合并 union

二、代码模板

三、练习

1、  990.等式方程的可满足性🟢

2、  1061. 按字典序排列最小的等效字符串🟢

3、721.账户合并 🟡

4、  839.相似字符串组🟡

5、  2812.找出最安全路径 🔴


 一、原理

并查集主要运用与求一些不相交且有关联的集合的合并,这一点我们从后面的例题中进一步理解,我们首先掌握并查集的原理和运用

并查集的主要操作有:

1. 初始化Init

我们将每个数据看作一个树的节点,初始化每个节点指针指向自己

我们用一个数组fa[]的下标index表示节点, 用fa[index]表示该节点的根节点;

  2. 查询 find 

查询一个节点的根节点,以用于其他操作;

如上图, 若要查询数据3所在的集合的根节点,想做图这样的链接方式每次查询需要O(n)的时间,我们需要在查询时将树的结构转换成右图所示,这样之后的每次查询时间复杂度为O(logn)

3. 合并 union

实现两个集合的合并,可以抽象成两颗树的合并,即将两颗树的根节点相连;

二、代码模板

//初始化
vector<int> fa(n* n);
iota(fa.begin(), fa.end(), 0);//查询
function<int(int)> find = [&](int x) -> int { return x == fa[x] ? x : fa[x] = find(fa[x]); };  //合并
fa[find(x)] = find(y);   

三、练习

1、  990.等式方程的可满足性🟢

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。 

解题思路:合并等式方程两侧字母,运用并查集管理相等字母集合

class Solution {
public:bool equationsPossible(vector<string>& equations) {//初始化vector<int> fa(26);iota(fa.begin(), fa.end(), 0);//查询function<int(int)> find = [&](int x) -> int { return fa[x] == x ? x : fa[x] = find(fa[x]); };for (auto s : equations) {if (s[1] == '=') {int x = s[0] - 97, y = s[3] - 97;fa[find(x)] = find(y);   //相等则合并}}for (auto s : equations) {int x = s[0] - 97, y = s[3] - 97;if (s[1] == '!' && find(x) == find(y)) return false;   //矛盾,返回false}return true;}
};

2、  1061. 按字典序排列最小的等效字符串🟢

给出长度相同的两个字符串s1 和 s2 ,还有一个字符串 baseStr 。

其中  s1[i] 和 s2[i]  是一组等价字符。

  • 举个例子,如果 s1 = "abc" 且 s2 = "cde",那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'

等价字符遵循任何等价关系的一般规则:

  •  自反性 'a' == 'a'
  •  对称性 'a' == 'b' 则必定有 'b' == 'a'
  •  传递性 :'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如, s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样,那么 baseStr = "eed" , "acd" 或 "aab",这三个字符串都是等价的,而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息,找出并返回 baseStr 的按字典序排列最小的等价字符串。

 解题思路:由等价关系可以一眼看出这道题使用并查集,s1与s2对应字母放入一个集合(即将其合并),最终找到baseStr每个字母对应的集合中的最小字典序字母

class Solution {
public:string smallestEquivalentString(string s1, string s2, string baseStr) {//初始化vector<int> fa(26);iota(fa.begin(), fa.end(), 0);//查询function<int(int)> find = [&](int x) -> int { return fa[x] == x ? x : fa[x] = find(fa[x]); };for (int i = 0; i < s1.size(); i++) {int x = s1[i] - 97, y = s2[i] - 97;fa[find(y)] = find(x);   //合并}unordered_map<int, set<char>> g;   //统计以根节点代表的一个集合中的所有节点for (int i = 0; i < 26; i++) {g[find(i)].insert(i + 97);}for (int i = 0; i < baseStr.size(); i++) {//利用set默认排升序的特点,找到baseStr[i]的根节点的集合中的最小字母baseStr[i] = *(g[find(baseStr[i] - 97)].begin());   }return baseStr;}   
};

3、721.账户合并 🟡

给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是 名称 (name),其余元素是 emails 表示该账户的邮箱地址。

现在,我们想合并这些账户。如果两个账户都有一些共同的邮箱地址,则两个账户必定属于同一个人。请注意,即使两个账户具有相同的名称,它们也可能属于不同的人,因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户,但其所有账户都具有相同的名称。

合并账户后,按以下格式返回账户:每个账户的第一个元素是名称,其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

解题思路:根据题意,拥有相同邮箱的账户为同一人,最终需要将相同用户的邮箱合并到一起,同样也是一眼并查集,但是代码实现起来可能有些复杂;首先需要遍历所有邮箱,判断是否有重复,将拥有同一邮箱的用户合并,需要特别注意的是,用户名相同不代表是同一人,最终将属于同一集合的用户邮箱用set去重,返回结果;

class Solution {
public:vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {int n = accounts.size();//以accounts的下标[0, n)作为用户名字,方便以下标寻找父亲vector<int> fa(n);iota(fa.begin(), fa.end(), 0);    //初始化function<int(int)> find = [&](int i) -> int { return fa[i] == i ? i : fa[i] = find(fa[i]); };//key:邮箱  val:名字unordered_map<string, vector<int>> email_name;for (int i = 0; i < n; i++) {for (int j = 1; j < accounts[i].size(); j++) {    //遍历每个账户的所有邮箱email_name[accounts[i][j]].push_back(i);//如果同一个邮箱出现多个名字,那么认为为同一个人,此时连接if (email_name[accounts[i][j]].size() > 1) {fa[find(email_name[accounts[i][j]][0])] = find(i);   //合并}}}//之前尝试用map,但是同一个名字可能不是同一人,所以map行不通//用set去重vector<set<string>> g(n);for (int i = 0; i < n; i++) {int f = find(i);   //找到根节点,将邮箱插入到根节点的数组中for (int j = 1; j < accounts[i].size(); j++) {g[f].insert(accounts[i][j]);    }}vector<vector<string>> ans;for (int i = 0; i < n; i++) {if (g[i].size() != 0) {    vector<string> tmp = {g[i].begin(), g[i].end()};  //将set转vectortmp.insert(tmp.begin(), accounts[i][0]);   //头插名字ans.push_back(tmp);}}return ans;}
};

4、  839.相似字符串组🟡

如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等,那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。

例如,"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置); "rats" 和 "arts" 也是相似的,但是 "star" 不与 "tars""rats",或 "arts" 相似。

总之,它们通过相似性形成了两个关联组:{"tars", "rats", "arts"} 和 {"star"}。注意,"tars" 和 "arts" 是在同一组中,即使它们并不相似。形式上,对每个组而言,要确定一个单词在组中,只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组?

解题思路:暴力遍历+dfs查询相似字符串,将相似字符串合并,最终返回集合个数

class Solution {
public:int numSimilarGroups(vector<string>& strs) {int n = strs.size();//初始化vector<int> fa(n);iota(fa.begin(), fa.end(), 0);//查询function<int(int)> find = [&](int x) -> int { return x == fa[x] ? x : fa[x] = find(fa[x]); };   int vis[n];memset(vis, 0, sizeof(vis));//dfsfunction<void(int)> is_same = [&](int i) -> void {vis[i] = true;string& s1 = strs[i];for (int j = 0; j < n; j++) {if (!vis[j]) {string& s2 = strs[j];if (s1 == s2) {    //相同字符串相似,直接合并fa[find(j)] = fa[i];is_same(j);} else {int dif = 0;for (int k = 0; k < s1.size(); k++) {if (s1[k] != s2[k]) dif++;if (dif > 2) break;}if (dif == 2) {         //恰有两个位置字符不同则相似,合并fa[find(j)] = fa[i];is_same(j);}}}}};//dfs入口for (int i = 0; i < n; i++) {if(!vis[i]) is_same(i);}//用set去重,返回集合个数set<int> ans;for (int i = 0; i < n; i++) ans.insert(find(i));   //将根节点插入set中return ans.size();}
};

5、  2812.找出最安全路径 🔴

给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid ,其中 (r, c) 表示:

  • 如果 grid[r][c] = 1 ,则表示一个存在小偷的单元格
  • 如果 grid[r][c] = 0 ,则表示一个空单元格

你最开始位于单元格 (0, 0) 。在一步移动中,你可以移动到矩阵中的任一相邻单元格,包括存在小偷的单元格。

矩阵中路径的 安全系数 定义为:从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。

返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。

单元格 (r, c) 的某个 相邻 单元格,是指在矩阵中存在的 (r, c + 1)(r, c - 1)(r + 1, c) 和 (r - 1, c) 之一。

两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | + | b - y | ,其中 |val| 表示 val 的绝对值。

解题思路:由题,求从左上角到右下角路径中的最小安全系数的最大值:倒序枚举答案(安全系数), 将>=当前安全系数的坐标用并查集相连(合并),一次循环结束判断左上角与右下角是否相连

class Solution {
public:static constexpr int dirs[5] = {1, 0, -1, 0, 1};int maximumSafenessFactor(vector<vector<int>>& grid) {int n = grid.size();vector<pair<int, int>> q;vector<vector<int>> dis(n, vector<int>(n, -1));for (int i = 0; i < n; i++) {for (int j = 0;j < n; j++) {if(grid[i][j] == 1) {q.push_back({i, j});dis[i][j] = 0;}}}//bfs求每个点安全系数,及不同安全系数的值的下标(用于后续并查集的合并)vector<vector<pair<int, int>>> groups = {q};while (!q.empty()) {int safe = groups.size();vector<pair<int, int>> tmp;for (auto &[i, j] : q) {for (int k = 0; k < 4; k++) {int x = i + dirs[k], y = j + dirs[k + 1];if (x >= 0 && x < n && y >= 0 && y < n && dis[x][y] < 0) {dis[x][y] = safe;tmp.push_back({x, y});}}}if (tmp.size() > 0)groups.push_back(tmp);q = move(tmp);}//初始化vector<int> fa(n*n);for (int i = 0; i < n * n; i++) fa[i] = i;//查询function<int(int)> find = [&](int x) -> int { return x == fa[x] ? x : fa[x] = find(fa[x]); };for (int ans = groups.size() - 1; ans > 0; ans--) {for (auto& [i, j] : groups[ans]) {for (int k = 0; k < 4; k++) {int x = i + dirs[k], y = j + dirs[k + 1];if (x >= 0 && x < n && y >= 0 && y < n && dis[x][y] >= dis[i][j]) fa[find(x * n + y)] = find(i * n + j);  //合并}}if (find(0) == find((n - 1) * n + n - 1)) return ans;   //相通则返回答案}return 0;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/86730.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

智能优化算法:猎豹优化算法-附代码

智能优化算法&#xff1a;猎豹优化算法 文章目录 智能优化算法&#xff1a;猎豹优化算法1.猎豹优化算法1.1 初始化1.2 搜索策略1.3坐等策略1.4攻击策略 2.实验结果3.参考文献4.Matlab5.python 摘要&#xff1a;CO算法是Mohammad AminAkbari等人于2022年受自然界猎豹狩猎启发而提…

JUL 日志 - 最简单易用的Java日志框架

在正式的生产环境下是不能使用 System.out 进行日志记录的 因为 System.out 不能提供时间、线程、执行过程 等信息&#xff0c;如果要手动打印输出则会非常麻烦 而日志就帮我们把这些事给干了 接下来我们学一个最简单的日志框架 JUL JUL全称Java util Logging是java原生的日志框…

支付整体架构

5.4 支付的技术架构 架构即未来&#xff0c;只有建立在技术架构设计良好的体系上&#xff0c;支付机构才能有美好的未来。如果支付的技术体系在架构上存在问题&#xff0c;那么就没有办法实现高可用性、高安全性、高效率和水平可扩展性。 总结多年来在海内外支付机构主持和参与…

Nginx负载均衡以及keepalived高可用实验

Vip 10.1.122 Keepalived-master 10.1.1.132Keepalied-backup 10.1.1.133Realserver_1 10.1.1.136Realserver_2 10.1.1.137 四台机器上安装nginx&#xff0c;编译安装的话需要另外安装pcre包支持&#xff0c;安装在/usr/local/nginx Keepalived-master 和backu…

Vue+SpringBoot后台管理系统:Vue3+TypeScript项目搭建(一)

写在开始:一个搬砖程序员的随缘记录文章目录 一、Node安装二、Vue CLI安装三、相关的版本四、创建Vue3TypeScript项目五、Vue项目初始化六、项目启动 一、Node安装 查看Note版本 node -v查看npm版本 npm -v然后将npm升级至最新版本 npm -g install npm将npm下载源换至http:…

项目中使用git vscode GitHubDesktopSetup-x64

一、使用git bash 1.使用git bash拉取gitee项目 1.在本地新建一个文件夹&#xff08;这个文件夹是用来存放从gitee上拉下来的项目的&#xff09; 2.在这个文件夹右键选择 git bash here 3.输入命令 git init (创建/初始化一个新的仓库) 4.输入命令 git remote add origin …

生成式人工智能模型:提升营销分析用户体验

使用生成式人工智能来改善分析体验&#xff0c;使业务用户能够询问有关我们数据平台中可用数据的任何信息。 在本文中&#xff0c;我们将解释如何使用新的生成式人工智能模型 ( LLM ) 来改善业务用户在我们的分析平台上的体验。假设我们为零售销售经理提供 Web 应用程序或移动应…

【问题解决】Git命令行常见error及其解决方法

以下是我一段时间没有使用xshell&#xff0c;然后用git命令行遇到的一些系列错误和他们的解决方法 遇到了这个报错&#xff1a; fatal: Not a git repository (or any of the parent directories): .git 我查阅一些博客和资料&#xff0c;可以解决的方式&#xff1a; git in…

迅镭激光PL12050重载型激光切管机中标国内知名企业美的集团!

近日&#xff0c;迅镭激光重型激光切管机中标国内知名企业——美的集团! 成立于2002年的菱王电梯&#xff0c;是美的集团暖通与楼宇事业部旗下的专业电梯品牌 &#xff0c;业务覆盖电(扶)梯的研发、设计、制造、销售、安装和维保&#xff0c;自主研发的8m/s超高速电梯和8吨超重…

题34(在排序数组中查找元素的第一个和最后一个位置)

使用二分查找 此题的关键在于找到左端点和右端点 找中点 两种操作 左端点用第一个方式 右端点用第二种&#xff0c;避免死循环 二分模板 class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()0) return{-…

Hadoop理论及实践-HDFS读写数据流程(参考Hadoop官网)

NameNode与DataNode回顾 主节点和副本节点通常指的是Hadoop分布式文件系统&#xff08;HDFS&#xff09;中的NameNode和DataNode。 NameNode&#xff08;主节点&#xff09;&#xff1a;NameNode是Hadoop集群中的一个核心组件&#xff0c;它负责管理文件系统的命名空间和元数据…

搭建Docker环境

目录 一、docker环境搭建 1、卸载旧版本docker 2、安装依赖和设置仓库 3、安装docker 4、启动并加入开机启动 5、验证是否安装成功 二、利用docker搭建nginx 1、拉取镜像 2、启动容器&#xff0c;部署nginx 一、docker环境搭建 1、卸载旧版本docker yum remove docke…

C++笔记之字节数组的处理

C笔记之字节数组的处理 code review! 文章目录 C笔记之字节数组的处理1.字节数组打印2.将字节数组转换为十六进制字符串并打印3.将字符串转为字节数组4.将字节数组转为字符串5.字节数组和字符数组的区别6.字节数组用于二进制数据存储7.字节数组用于网络通信数据传输8.使用 un…

如何创造千亿项目?合法合规的绿色消费增值积分,或许能冲出赛道

电商行业的竞争越来越激烈&#xff0c;大部分的电商平台都面临着这三大难题&#xff1a;如何吸引用户、如何留存用户以及如何让用户为平台带来更多的效益。为了解决这三大问题&#xff0c;我们提出了创造千亿项目的商业模式——绿色消费增值积分系统&#xff0c;帮助企业冲出赛…

文档控件DevExpress Office File API v23.1新版亮点 - 支持.NET MAUI

DevExpress Office File API是一个专为C#, VB.NET 和 ASP.NET等开发人员提供的非可视化.NET库。有了这个库&#xff0c;不用安装Microsoft Office&#xff0c;就可以完全自动处理Excel、Word等文档。开发人员使用一个非常易于操作的API就可以生成XLS, XLSx, DOC, DOCx, RTF, CS…

维深(Wellsenn):2023中国消费端VR内容开发商调研报告(附下载

关于报告的所有内容&#xff0c;公众【营销人星球】获取下载查看 核心观点 国内互联网大厂商入局VR&#xff0c;字节跳动、网易表态明确。字节跳动2021年收购国内头部VR硬件厂商PICO后&#xff0c;加速构建VR内容生态&#xff0c;2021年 成立海南创见未来当前已推出VR视频应用…

Docker安装 elasticsearch-head

目录 前言安装elasticsearch-head步骤1&#xff1a;准备1. 安装docker2. 搜索可以使用的镜像。3. 也可从docker hub上搜索镜像。4. 选择合适的redis镜像。 步骤2&#xff1a;拉取elasticsearch-head镜像拉取镜像查看已拉取的镜像 步骤3&#xff1a;创建容器创建容器方式1&#…

免费实用的日记应用:Day One for Mac中文版

Day One for Mac是一款运行在Mac平台上的日记软件&#xff0c;你可以使用Day One for mac通过快速菜单栏条目、提醒系统和鼓舞人心的信息来编写更多内容&#xff0c;day one mac版还支持Dropbox同步功能&#xff0c;想要day one mac中文免费版的朋友赶紧来试试吧&#xff01; …

苍穹外卖day12笔记

一、工作台 联系昨天 要实现的功能和昨天差不多&#xff0c;都是查询数据。 所以我们就写出查询语句&#xff0c;然后直接导入已经写好的代码。 实现效果 查询语句 今日数据 营业额 select count(amount) from orders where status5 and order_time > #{begin} and …

[保研/考研机试] KY30 进制转换-大整数转二进制 清华大学复试上机题 C++实现

描述 将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。 输入描述&#xff1a; 多组数据&#xff0c;每行为一个长度不超过30位的十进制非负整数。 &#xff08;注意是10进制数字的个数可能有30个&#xff0c;而非30bits的整数&#xff09; 输出描述&#xff…