#yyds干货盘点# 解决名企真题：火眼金睛

2 years ago

source link: https://blog.51cto.com/u_15488507/5453639
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

#yyds干货盘点# 解决名企真题：火眼金睛

原创

97的风 2022-07-08 10:36:24 博主文章分类：面试题 ©著作权

文章标签 i++ 数据 java 文章分类 Java 编程语言 阅读数226

1.简述：

描述

现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。

输入描述：

每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，后面则为所有回答人的ID。(ID均为0-1000000的整数)

输出描述：

第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。

示例1

3
1 1 2
2 1 1
3 2 1 2

2.代码实现：

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int N = in.nextInt();//问题数
int[] askId = new int[N];//提问人ID
int[] ansNum = new int[N];//回答人的人数
int[][] map = new int[N + 1][N + 1];
for (int i = 0; i < N; i++) {
askId[i] = in.nextInt();
ansNum[i] = in.nextInt();
for (int j = 0; j < ansNum[i]; j++) {//具体回答问题的人的ID
int ansId = in.nextInt();
//map[i][j] = 1：j回答了i的问题。最后map长度为n，宽度为ansNum[i]，每一行的宽度可能不一样
map[askId[i]][ansId] = 1;
}
}
//判断是否作弊
List<Integer> list = new ArrayList<>();//作弊清单
for (int i = 0; i <= N; i++) {
int count = 0;//对于每一个用户，记录作弊的人数
for (int j = 0; j <= N; j++) {
if (map[i][j] == 1 && map[j][i] == 1 && i != j) {//两人互相回答了对方的问题
if (!list.contains(i)) {//加入清单，如果已存在就不重复添加了
list.add(i);
count++;
}
}
if (map[i][j] == 1 && i != j && list.contains(j)) {//作弊用户回答了i的问题，i也判为作弊
count++;
}
if (count >= 2) {//对于每一个用户，如果回答人数超过2个，且这两个人都作弊了，那么这个人也判作弊
if (!list.contains(i)) {
list.add(i);
}
}
}
}
Collections.sort(list);
if (list.size() == 0){
System.out.println(0);
}else {
System.out.println(list.size());
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
}
}
}
}