大家好,我是道哥。
在阿里巴巴的文化中,充满了各种武侠元素。在面试阿里时,也经常会出现一些有趣的题目,今天,我们来看一道阿里巴巴面试的题目:
在武林中,朋友的朋友还是朋友,比如朋友关系如下表所示,那么周芷若、张无忌、韩小昭属于一个朋友圈,成昆和陈友谅属于一个朋友圈,杨逍和纪晓芙属于一个朋友圈。最终,不同朋友圈的个数是3.
人物 | 人物 |
关系 |
周芷若 |
张无忌 | 朋友 |
张无忌 | 韩小昭 |
朋友 |
成昆 |
陈友谅 |
朋友 |
杨逍 |
纪晓芙 |
朋友 |
(1)任意给定两个人,判断他们是否属于同一个朋友圈。
(2)编程求出不同朋友圈的个数。
题目理解
首先,我们来看看周芷若、张无忌和韩小昭长什么样子吧,还是挺可爱的。张无忌这家伙,笑得挺开心,别问为什么,懂的自然懂。
我来解释什么叫“朋友的朋友还是朋友”:周芷若和张无忌是朋友,张无忌和韩小昭是朋友。所以,他们三人是朋友,属于同一个朋友圈。趣味动图解释如下:
思路分析
在解决这个问题之前,我们得想一种合理的数据结构,然而,貌似书本上的数据结构都不合适,那怎么办呢?
我们来讲一个周芷若与并查集的故事。先来分析一下,好友关系如下:
{周芷若,张无忌}
{张无忌,韩小昭}
{成昆,陈友谅}
{杨逍,纪晓芙}
他们关系的逻辑图如下:
从上图可知,这些人属于不同的3个朋友圈,那么这3个朋友圈是怎么得出来的呢?
很显然,我们可以在每个朋友圈定义一个名义上的leader.
如果要判断两个人是否属于一个朋友圈,只需要判断他们的leader是否为同一个人,这是一个查询的过程。
如果两个人是好友关系,则需要把两个人并入同一个朋友圈,这是一个合并的过程。
这一查一并的操作,就分出了最终有多少个朋友圈,对应的数据结构就是并查集。在很多笔试面试或ACM竞赛中,并查集屡见不鲜。
编程实现
根据上述思路分析,我们用C++代码来实现并查集,并给出测试和结果。代码的注释非常详细,所以不再赘述:
#include <iostream>
#include <map>
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
很显然,周芷若和韩小昭是朋友关系,张无忌和成昆不是朋友关系,而且,朋友圈个数为3, 如上程序可以通过阿里的面试。希望大家对并查集了如指掌,顺利通过笔试、面试,拿到更好的offer.
并查集很有意思,也是经常涉及到的考点,关键还是在于思路。我们也会一步一个脚印,争取每篇文章讲清讲透一件事,也希望大家阅读后有所收获,心情愉快。最后,来看一段舞蹈吧,皆大欢喜。
你好,我是道哥,CSDN前30名,曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。欢迎点击如下名片,关注爱码有道:
欢迎加入技术交流群
欢迎通过如下二维码加我的个人微信号,我们一起在技术交流群中讨论,群里有BAT技术大牛坐镇。加好友时请备注“加群”。
本文同步分享在 博客“Big sai”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。