笔试刷题-拼多多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);
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,899评论 18 399
  • 鼠标粗描淡写,人物在粗糙中也活灵活现。
    清秋朗月阅读 3,471评论 0 2