各大公司公开了的笔试面试题练习之网易游戏2016“运营开发工程师”在线测评题friend set解答;
全部代码下载:
Github链接:https://github.com/wpeace1212/Coder/tree/master/Code/netease
写文章不易,欢迎大家采我的文章,以及给出有用的评论,当然大家也可以关注一下我的github;多谢;
##题目3 : friend set 时间限制: 5000ms 单点时限: 1000ms 内存限制: 256MB
-
8 1 2 2 3 5 4 3 4 6 7 8 6 9 10 10 11
样例输出 -
5 3 3
描述
现在存有大量一对好友的列表,好友的好友也是好友,所有有好友关系的形成一个圈子,请找出圈子中的人数。输入
第一行是N,表示好友对的数量(1<= N <= 100000)。之后N行每行是两个数字,代表玩家代号,用空格分隔。玩家代号是整数且<= 1000000000。输出
将每个圈子中的人数按降序排列。
样例输入
2.我的理解:
- 朋友圈的建立
关键点,建立一个存放set的list集合,然后操作list中的集合
集合中没有这一对好友中的任意一个,新建set集合
只有一个集合与该对好友组成好友关系,将数据添加到对应set集合
有两个集合与该对好友构成关系,将两个集合合成一个
- 规模排序
排序相对来说简答,详见代码
3.我的代码:
package com.netease.yunyin;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Friend {
public static void main(String[] args) {
//获得输入
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//存储所有的朋友圈
List<Set<Integer>>list=new ArrayList<>();
try {
//获得行数
int len=Integer.parseInt(br.readLine());
//循环
while(len-->){
//获得每行的整数
String string=br.readLine();
if(string==null||"".equals(string))break;
String[] strings = string.split("\\s");
int a[]=new int[]{Integer.parseInt(strings[]),
Integer.parseInt(strings[])};
/*count
* 进行判断:
* 0 :带表集合中没有这一对好友中的任意一个,新建set集合
* 1 :代表只有一个与该对好友组成好友关系,
* 2 :代表有两个集合,与该对好友构成关系,将两个集合合成一个
* 不会大雨2
*/
int count=;
//索引:存储list中的索引,该索引对应的集合与该对好友存在关系
int index[]=new int[];
//索引计数
int n=;
//遍历存在的朋友圈
for(Set<Integer>s:list){
//判断关系
if(s.contains(a[])||s.contains(a[]))
{
//有关系则加入
s.add(a[]);
s.add(a[]);
//保存索引
index[count++]=n;
}
n++;
//为2的话即可以跳出循环
if(count==)break;
}
//不存在关系,则新建集合
if(count==)
{
Set<Integer>s=new HashSet<>();
s.add(a[]);
s.add(a[]);
list.add(s);
}
//存在两个,则合并
else if(count==){
Set<Integer> set1 = list.get(index[]);
Set<Integer> set2 = list.get(index[]);
set1.addAll(set2);
list.remove(index[]);
}
}
//按集合的规模排序
Collections.sort(list, new Comparator<Set<Integer>>() {
@Override
public int compare(Set<Integer> o1, Set<Integer> o2) {
if(o1.size()>o2.size())
return -;
return ;
}
});
//遍历输出规模
for(Set<Integer>s:list){
System.out.println(s.size());
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
4.我的测试结果:
好的本章介绍到这里
来自伊豚wpeace(rlovep.com)