笔试刷题-拼多多2018-08-17

题目描述：

给出一个是否为朋友的矩阵输入用逗号分隔, isFriend[i][j]==1表示为朋友，否则不是朋友；

找出一对i, j使得i, j不是直接朋友，但是i,j有共同的朋友，求这种共同的朋友数量最多的情况即可。

思路：

简单枚举计算即可。（这里用了split所以用了java）

代码如下：

package fall_2018;
 
import java.util.*;
 
public class Test03 {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N, targetId;
        N=sc.nextInt();
        targetId=sc.nextInt();
        //吃掉回车
        sc.nextLine();
        //构建朋友矩阵
        boolean[][] isFriendMatrix=new boolean[N][N];
        for(int i=0; i<N; i++){
            String friendListStr = sc.nextLine();
            String[] friendIdStrArr=friendListStr.split("\\s+");
            for(String friendIdStr:friendIdStrArr){
                int friendId=Integer.parseInt(friendIdStr);
                isFriendMatrix[i][friendId]=true;
                isFriendMatrix[friendId][i]=true;
            }
        }
        //找出与targetId共同朋友最多的人
        int resultId=-1, resultMaxCommonFriendNum=0;
        for(int uId=0; uId<N; uId++){
            if(uId==targetId)
                continue;
            //若为朋友不用
            if(isFriendMatrix[targetId][uId])
                continue;
            int commonFriendNum=0;
            for(int vId=0; vId<N; vId++){
                if(isFriendMatrix[targetId][vId] && isFriendMatrix[uId][vId]){
                    commonFriendNum++;
                }
            }
            if(commonFriendNum>resultMaxCommonFriendNum){
                resultMaxCommonFriendNum=commonFriendNum;
                resultId=uId;
            }
        }
        //输出结果
        System.out.println(resultId);
    }
}