一道有趣的阿里面试题
Hollis
共 1923字,需浏览 4分钟
· 2022-04-26
人物 | 人物 | 关系 |
周芷若 | 张无忌 | 朋友 |
张无忌 | 韩小昭 | 朋友 |
成昆 | 陈友谅 | 朋友 |
杨逍 | 纪晓芙 | 朋友 |
题目理解
首先,我们来看看周芷若、张无忌和韩小昭长什么样子吧,还是挺可爱的。
思路分析
在解决这个问题之前,我们得想一种合理的数据结构,然而,貌似书本上的数据结构都不合适,那怎么办呢?
我们来讲一个周芷若与并查集的故事。先来分析一下,好友关系如下:
{周芷若,张无忌}
{杨逍,纪晓芙}
从上图可知,这些人属于不同的 3 个朋友圈,那么这 3 个朋友圈是怎么得出来的呢?
很显然,我们可以在每个朋友圈定义一个名义上的 leader。
如果要判断两个人是否属于一个朋友圈,只需要判断他们的 leader 是否为同一个人,这是一个查询的过程。
如果两个人是好友关系,则需要把两个人并入同一个朋友圈,这是一个合并的过程。
这一查一并的操作,就分出了最终有多少个朋友圈,对应的数据结构就是并查集。在很多笔试面试或 ACM 竞赛中,并查集屡见不鲜。
编程实现
根据上述思路分析,我们用 C++ 代码来实现并查集,并给出测试和结果。代码的注释非常详细,所以不再赘述:
using namespace std;
map<string, string> leader;
// 每一行表示一对朋友关系
string input[] =
{
"周芷若", "张无忌",
"张无忌", "韩小昭",
"成昆", "陈友谅",
"杨逍", "纪晓芙",
};
// 测试每行的两个人是否为朋友
string test[] =
{
"周芷若", "韩小昭",
"张无忌", "成昆",
};
// 初始化
void setLeader()
{
int i = 1;
int totalPerson = 8;
for(i = 0; i < totalPerson; i++)
{
leader[input[i]] = input[i]; // 将自己初始化为自己的领导
}
}
// 查找领导,看看究竟是谁
string findLeader(string s)
{
string r = s;
while(leader[r] != r)
{
r = leader[r]; // 没找到的话,一直往上找
}
return r;
}
// 将两个领导的朋友圈合并,从此,leaderX和leaderY是一个朋友圈了
void uniteSet(string leaderX, string leaderY)
{
leader[leaderX] = leaderY;
}
int main()
{
int numberOfSets = 7; // 最开始有7个不重复的人
// 初始化领导
setLeader();
int i = 0;
int j = 0;
int n = 4; // 人物关系的数组有4行
for(j = 0; j < n; j++)
{
string u = input[i++];
string v = input[i++];
// 找领导
u = findLeader(u);
v = findLeader(v);
// 领导不相等,则合并两个朋友圈
if(u != v)
{
uniteSet(u, v);
numberOfSets--;
}
}
i = 0;
n = 2; // 待测试人物关系的数组有2行
for(j = 0; j < n; j++)
{
string u = test[i++];
string v = test[i++];
// 找领导
u = findLeader(u);
v = findLeader(v);
// 如果领导不相同,则不属于一个朋友圈
if(u != v)
{
cout << "NO" << endl;
}
else // 如果两个领导相同,则肯定属于一个朋友圈
{
cout << "YES" << endl;
}
}
cout << numberOfSets << endl;
return 0;
}
YES
NO
3
并查集很有意思,也是经常涉及到的考点,关键还是在于思路。希望大家对并查集了如指掌,顺利通过笔试、面试,拿到更好的 offer。
完
往期推荐
5.4万Star全部归零,项目作者:十分后悔
突发!联想被责令立即开展全面整改
Git 各指令的本质,真是通俗易懂啊
有道无术,术可成;有术无道,止于术
欢迎大家关注Java之道公众号
好文章,我在看❤️
评论
真高!比亚迪员工爆料比亚迪在越南的薪资水平:基本工资480万,全勤奖35万,交通补助20万,餐补110万,每周6天,每天10小时
上一篇:某大公司为逼迫员工离职,竟然把他的工位安排到厕所旁,没想到他直接开始记录领导的如厕时间,还发到公司大群...对此,你怎么看?--完--PS:欢迎在留言区留下你的观点,一起讨论提高。如果今天的文章让你有新的启发,欢迎转发分享给更多人。全文完,感谢你的耐心阅读。如果你还想看到我的文章,请一定给本
开发者全社区
0
太敢穿了!透视纱裙!性感火辣的身材
绝了呀今天的厂花:吴宣仪1995年1月26日,吴宣仪出生于海南省海口市,中国内地流行乐女歌手、影视演员。2016年2月,吴宣仪随宇宙少女发行首张迷你专辑正式出道。2018年4月,她参加《创造101》综艺选秀,获得第二名,成功加入火箭少女101组合。吴宣仪的颜值一直备受称赞,她的五官立体精致,皮肤白皙
逆锋起笔
0
某大公司为逼迫员工离职,竟然把他的工位安排到厕所旁,没想到他直接开始记录领导的如厕时间,还发到公司大群...
上一篇:字节的跳动职级与薪资(2024年)我们与公司间的合作,宛如两艘船只在茫茫大海上相互依靠,共同抵御风浪,携手驶向成功的彼岸。然而,当航向开始产生分歧,或是波涛汹涌的风浪改变了我们的初衷,我们或许应当冷静地选择和平分手,而非在风雨中硬撑。最近,一位网友的遭遇引起了广大职场人的关注和热议。这位网友
开发者全社区
0
金融研究 | 使用Python测量关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0
我看阿里的年终奖总算发了!
到4月底了,这两天看朋友圈,发现阿里的年终奖终于发了,问了问老同学,也从网上检索了不少信息,基本搞清楚了阿里今年的年终奖情况。近来来阿里一些集团对绩效等级做了较大的调整,以前的旧绩效系统中,绩效分为3.25、3.5、3.75、4和5五个等级,其中4和5是较高绩效等级,较少见。而且之前3.5绩效内部划
公子龙
0
CVPR 2024|大视觉模型的开山之作!无需任何语言数据即可打造大视觉模型
↑ 点击蓝字 关注极市平台作者丨科技猛兽编辑丨极市平台极市导读 本文提出一种序列建模 (sequential modeling) 的方法,不使用任何语言数据,训练大视觉模型。>>加入极市CV技术交流群,走在计算机视觉的最前沿本文目录1 序列建模打造大视觉模型(来自 U
极市平台
1
金融研究(更新) | 使用Python构建关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0
字节的跳动职级与薪资(2024年)
上一篇:阿里公布年终奖,P7, 3.5+,22W年终奖,还有35W长期现金激励,真香字节跳动自2012年3月成立以来,已经迅速成长为一个全球性的科技公司。其产品和服务已经遍布全球150多个国家与地区,并且支持超过75种不同的语言。在字节跳动的官方网站上,列出了一系列引人注目的产品和服务,包括但不限于
开发者全社区
0