#yyds干货盘点# 名企真题专题:火眼金睛

2022-12-09 18:13:26 来源:51CTO博客


(相关资料图)

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

输入:

31 1 22 1 13 2 1 2

输出:

31 2 3

2.代码实现:

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 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();            }        }    }}

标签: 我们需要 小于等于 火眼金睛

上一篇:环球热文:配置静态路由,默认路由
下一篇:资讯:异构混排在vivo互联网的技术实践