4.7号做华为实习生笔试,第一题都没完全做出来,用了暴力模拟直接超时,考完后,才知道考察并查集,而且和并查集的经典题目找朋友十分类似,作为一个非科班的,没有系统学习过,只是一直在力扣上刷题,可能刷题少了,没有遇到过并查集的题目(恰巧今天刷每日一题,遇到了并查集),也是第一次听说并查集,所以写下这篇笔记,一方面记录一下学习流程,另一方面提醒自己基础不扎实
本文根据胡凡老师的算法笔记进行学习的
首先从字面上进行理解并查集,并就是合并(Union),查就是查找(find),集就是集合(set),在力扣上的英文标签也是Union find,所以并查集支持两种操作,合并和查找。并查集的实现方式就是数组,利用farther数组表示节点处的父亲,举例说明:father[1] = 1
表示1的父亲节点时自己,father[2] = 1
表示2的父亲节点时1。对于并查集来说,每个连通的集合都有自己的根节点,所有的根节点都指向自己,如下图所示,就是一个连通的集合,在该集合中,3的父亲节点时1,5的父亲节点是1,7的父亲节点是1,1的父亲节点是4,2的父亲节点是4,4的父亲节点也是4,所有节点的根节点都是4。以上也就是并查集所需要的的基本了解了,下面直接以找朋友这道例题进行详细讲解。
father[3] = 1;//3的父亲节点是1
father[5] = 1;//5的父亲节点是1
father[7] = 1;//7的父亲节点是1
father[1] = 4;//1的父亲节点是4
father[2] = 4;//2的父亲节点是4
father[4] = 4;//4的父亲节点是4
如果1和2是好朋友,2和3是好朋友,那么1和3也是好朋友,现在给定输入,一共又n个人,n个人的代号分别是1到n,有m组关系(两两之间的关系),问一共可以把这n个人分为几组。(最多有100个人)
输入:
7 5 //7个人,5组关系
1 2 //1和2是好朋友
2 3 //2和3是好朋友
3 1 //3和1是好朋友
1 4 //1和4是好朋友
5 6 //5和6是好朋友
输出:
3
//解释:由前四组关系可得:1、2、3和4是好朋友,
//由第四组关系可得:5和6是好朋友,由于7和任何人都不是好朋友,所以有三组。
也就是先假设每个人都没有好友,每个人都是孤立的,也就是每个人的父亲节点都指向自己。注意:没有代号为0的人,所以从1开始遍历。
int N = 101;
vector<int> father(N, 0);
void init(int n){
for(int i = 1; i <= n; i++){
father[i] = i;
}
}
初始化后的结果,如下图所示,每个人都是一个集合
也就是将所有人进行分组,每一组都是好朋友。什么是合并,合并就是将有关系的所有人放在一个集合中。放在一个集合中,需要将一个集合的根节点指向另一个集合的根节点(注意区别根节点和父节点,同时一个人也是一个集合,也就是说初始化后的状态有7个集合(0不算),每个集合的节点的父节点和根节点都是自己),所以合并的前提是找到每个集合的根节点,接下来就是根节点的查找过程:
这里也可以用递归实现,就是节点x一直往前遍历,遇到节点的父亲等于节点自己的时候,此时说明x已经为根节点了,跳出循环,返回根节点。
int findRoot(int x){
while(x != father[x]){
x = father[x];//节点x往前遍历
}
return x;
}
扩展:这里可以看到,如果是一条很长的链,查找一次需要从尾遍历到头,查找多次的话,是十分浪费时间的,我们可以在第一次查找x的时候,将所有x之前的节点都之间挂在到根节点,这样的话,等我们再次查找x节点之前的节点的根节点时,就能一步找到根节点了。下面就是路径压缩后的查找根节点算法:
int findRoot(int x){
int a = x;
while(x != father[x]){
x = father[x];
}
//此时x节点存放的是根节点
//在第一次查找时,将要查找的节点之前所有节点都挂在根节点上
//步骤:1、保存节点a,防止往前遍历时,变量a被其父亲覆盖
//2、节点a往根节点进行遍历,保证a之前的节点都能挂在根节点上
//3、将节点a挂在根节点上
while(a != father[a]){
int z = a;
a = father[a];//从节点a处往根节点方向遍历
father[z] = x;//将z的父亲节点设为x,也就是设为根节点
}
return x;
}
实现好查找根节点的函数后,我们就可以实现合并函数了:
查找节点a和节点b的根节点,如果两个根节点不相同,说明他们不在同一集合,将a的根节点的父亲节点设为b的根节点,合并两个集合,如果相同,说明两个节点在一个集合不用操作任何事情。
void Union(int a, int b){
int RoA = findRoot(a);
int RoB = findRoot(b);
if(RoA != RoB){
father[RoA] = RoB;
}
}
数组A里存放的是输入的左列,数组B里面是输入的右列,但是不包括第一行的m和n。
语句1:初始化,将n个人的父节点都设为自己,说明n个人都没有朋友。
语句2:因为输入的左右是好朋友,所以将他们合并到一个集合。
比如之前的7个人,1和2是好朋友,所以Union(1, 2),1的根节点是1,2的根节点是2,所以将1的父节点设为2。将所有两两关系合并后,得到下面数组:
语句3:本题是最终目的就是找到有几个集合,从语句2所得到的结果可以看出:只要找到根节点的个数,就能找到集合的个数了,巧了,已经实现了找根节点的函数来,接下来定义一个和father数组大小一样的bool类型数组(初始值都是false)isRoot,用来标记哪个节点是根节点。可以看出,1、2、3、4的根节点都是4,所以4的位置标记为true,5和6的根节点为6,所以6的位置标记为true,7的根节点为7,所以7的位置标记为true。
语句4:最后遍历isRoot数组,找出其中为true的个数即可。
int findfriend(int m, int n, vector<int>& A, vector<int>& B){
//语句1
init(n);
//语句2
for(int i = 0; i < m; i++){
Union(A[i], B[i]);
}
//语句3
for(int i = 1; i <= n; i++){
isRoot[findRoot(i)] = true;
}
//语句4
int ans = 0;
for(int i = 0; i <= n; i++){
ans = ans + isRoot[i];
}
return ans;
}
其实可以发现并查集的最主要的就是找根节点函数和合并函数,实现这两个函数。最后,本文所写的程序整体代码如下:
#include <iostream>
#include <vector>
using namespace std;
int N = 110 ;
vector<int> father(N, 0);
vector<bool> isRoot(N, false);
//father[2] = 1,索引2是元素,1为元素2的父亲节点
//查找根节点函数
int findRoot(int x){
int a = x;
while(x != father[x]){
x = father[x];
}
//此时x节点存放的是根节点
//在第一次查找时,将要查找的节点之前所有节点都挂在根节点上
//步骤:1、保存节点a,防止往前遍历时,变量a被其父亲覆盖
//2、节点a往根节点进行遍历,保证a之前的节点都能挂在根节点上
//3、将节点a挂在根节点上
while(a != father[a]){
int z = a;
a = father[a];//从节点a处往根节点方向遍历
father[z] = x;//将z的父亲节点设为x,也就是设为根节点
}
return x;
}
//合并函数
void Union(int a, int b){
int RoA = findRoot(a);
int RoB = findRoot(b);
if(RoA != RoB){
father[RoA] = RoB;
}
}
void init(int n){
N = n;
for(int i = 1; i <= n; i++){
father[i] = i;
isRoot[i] = false;
}
}
int findfriend(int m, int n, vector<int>& A, vector<int>& B){
init(n);
for(int i = 0; i < m; i++){
Union(A[i], B[i]);
}
for(int i = 1; i <= n; i++){
isRoot[findRoot(i)] = true;
}
int ans = 0;
for(int i = 0; i <= n; i++){
ans = ans + isRoot[i];
}
return ans;
}
int main(void){
/*int n, m, a, b;
cin>>n>>m;
vector<int> A;
vector<int> B;
for(int i = 0; i < m; i++){
cin>>a>>b;
A.push_back(a);
B.push_back(b);
}*/
int m = 5;
int n = 7;
vector<int> A = {
1, 2, 3, 1, 5};
vector<int> B = {
2, 3, 1, 4, 6};
cout<<findfriend(m, n , A, B)<<endl;
return 0;
}
可以根据上述解法解华为4.7号的机试第一题(两题基本相同)
题目来自于牛客网
题目描述:幼儿园老师安排小朋友做游戏,现在需要安排给N个小朋友分组,老师让每个同学写一个名字,代表这个小朋友想和谁分到一组。请问老师在满足所有小朋友意愿的情况下,最多可以将班级分为几组?
输入描述:
第一行输入N,0 < N <= 10000
接下来是N行代表小朋友希望和谁分到一组,如"john jack",代表john希望和jack分为一组,两个名字之间以空格分割,名字本身不存在空格。
输出描述:
分组的最多数量
示例1
输入:
6
jack tom
alice john
jessica leonie
tom alice
john jack
leonie jessica
输出;
2
代码:
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, string> father;
map<string,bool> flag;
void init(vector<string>& vs1){
for(int i = 0; i < vs1.size(); i++){
father[vs1[i]] = vs1[i];
flag[vs1[i]] = false;
}
}
string findRoot(string& s){
string a = s;
while(s != father[s]){
s = father[s];
}
while(a != father[a]){
string z = a;
a = father[a];
father[z] = s;
}
return s;
}
void Union(string& s1, string& s2){
string s1Root = findRoot(s1);
string s2Root = findRoot(s2);
if(s1Root != s2Root){
father[s1Root] = s2Root;
}
}
int myfun(vector<string>& vs1, vector<string>& vs2){
int cnt = 0;
init(vs1);
for(int i = 0; i < vs1.size(); i++){
Union(vs1[i],vs2[i]);
}
for(auto n: father){
flag[findRoot(n.second)] = true;
}
for(auto n : flag){
if(n.second == true){
cnt++;
}
}
return cnt;
}
int main() {
/*int n;
cin>>n;
string s1;
string s2;
vector<string> vs1;
vector<string> vs2;
for(int i = 0; i < n; i++){
cin>>s1>>s2;
vs1.push_back(s1);
vs2.push_back(s2);
}*/
vector<string> vs1 = {
"jack","alice","jessia","tom","john","leonie","l","y","f"};
vector<string> vs2 = {
"tom","john","leonie","alice","jack","jessia","y","f","l"};
cout<<myfun(vs1,vs2)<<endl;
return 0;
}
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法