字节跳动第三次面试——抖音红人java版

参考leetcode #851，貌似比那个还简单些

大致的思想就是创建一个ArrayList数组放置用户的直接粉丝，Set（HashSet）数组放置用户的所有粉丝。

详细见代码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class RedMan {static ArrayList<Integer>[]graph;static Set<Integer>[]ct;public static void main(String[]args) {Scanner in=new Scanner(System.in);int N=in.nextInt();int M=in.nextInt();int[][]conn=new int[M][2];graph=new ArrayList[N+1];ct=new Set[N+1];//用户编号1开始，故创建N+1大小的数组for(int i=0;i<M;i++) {for(int j=0;j<2;j++) {conn[i][j]=in.nextInt();}}for(int i=0;i<N+1;i++) {graph[i]=new ArrayList<Integer>();ct[i]=new HashSet<Integer>();}//为每个List/Collection分配内存for(int[]edge:conn) graph[edge[1]].add(edge[0]);//将关系数组填充至graphint count=0;for(int []person:conn) {if(count_fans(person[1])==N) count++;}System.out.println(count);}//统计用户粉丝数public static int count_fans(int node) {ct[node].add(node);int count=1;//统计用户直接粉丝for(int fans:graph[node]) {if(!ct[node].contains(fans)) {//ct[node].add(fans);count++;}}//统计用户间接粉丝for(int fans:graph[node]) {for(int rfans:graph[fans]) {if(!ct[node].contains(rfans)) {//没放入ct的放进去并且count++；ct[node].add(rfans);count++;}}}return count;}
}