1 / 8
文档名称:

网易2016实习研发工程师编程题及答案(1).pdf

格式:pdf   大小:895KB   页数:8页
下载后只包含 1 个 PDF 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

网易2016实习研发工程师编程题及答案(1).pdf

上传人:蒙查查 2021/5/11 文件大小:895 KB

下载得到文件列表

网易2016实习研发工程师编程题及答案(1).pdf

相关文档

文档介绍

文档介绍:小明陪小红去看钻石,他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻
石的重量各不相同。在他们们比较了一段时间后,它们看中了两颗钻石 g1 和 g2。
现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。
给定两颗钻石的编号 g1,g2,编号从 1 开始,同时给定关系数组 vector,其中元素为
一些二元组,第一个元素为一次比较中较重的钻石的编号,第二个元素为较轻的钻
石的编号。最后给定之前的比较次数 n。请返回这两颗钻石的关系,若 g1 更重返回
1,g2 更重返回-1,无法判断返回 0。输入数据保证合法,不会有矛盾情况出现。
测试样例:
2,3,[[1,2],[2,4],[1,3],[4,3]],4
返回
: 1
1 //就是一个森林,关系存在就是以 g2 为根节点的树下面的节点中有 g1,
2 //或者以 g1 为根节点的树的下面的节点包含 g2
3 //我们采取层序遍历的方式遍历以 g1 开头的整棵树,和以 g2 开头的整棵树.
4 #include<unordered_map>
5 class Cmp {
6 bool judge(int g1,int g2,unordered_map<int,vector<int>> ans){
7 //查找 g1 是否比 g2 重.
8 queue<int>q;
9 unordered_map<int, bool>mark;//用于标记当前节点是否遍历过
10 (g1);
11 while (!()) {
12 int cur = ();
13 ();
14 mark[cur] = true;
15 if(cur==g2)
16 return true;
17 for(int i=0;i<ans[cur].size();++i){
18 if(!mark[ans[cur][i]])//没有遍历过
19 (ans[cur][i]);
20