网易笔试第三题最少语言数求助

第三题最少语言数,只能过13%,有佬帮忙看看哪里有问题吗

思路是用HashSet统计每个语言会的人

然后根据不同语言是否有同一个人会来构建图的边

最后DFS求联通分量

中间统计没有人会的语言(甲骨文)和一门语言都不会的人(笨蛋)

结果是联通分量-1

自己写完测了一个小时感觉没问题,写的很恼火,第4题都不想看就交卷了

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            HashSet<Integer>[] languages = new HashSet[m];
            Node[] Nodes = new Node[m];
            for (int i = 0; i < m; i++) {
                languages[i] = new HashSet<>();
                Nodes[i] = new Node(i, new ArrayList<Integer>());
            }
            int noLanguage = 0;
            for (int i = 0; i < n; i++) {
                int k = in.nextInt();
                if (k == 0) {
                    noLanguage++;
                    continue;
                }
                for (int j = 0; j < k; j++) {
                    int language = in.nextInt();
                    languages[language-1].add(i);
                }
            }
            int noOne = 0;
            for (int i = 0; i < m; i++) {
                if (languages[i].size() == 0) {
                    noOne++;
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    if (!judge(languages[i], languages[j])) {
                        Nodes[i].edges.add(j);
                    }
                }
            }
            int count = 0;
            boolean[] isReached = new boolean[m];
            for (int i = 0; i < m; i++) {
                if (!isReached[i]) {
                    dfs(Nodes, i, isReached);
                    count++;
                }
            }
            if (noLanguage == n) {
                System.out.println(n);
            }else {
                System.out.println(count - 1 - noOne + noLanguage);
            }
        }
    }

    public static void dfs(Node[] nodes, int index, boolean[] isReached) {
        isReached[index] = true;
        Node node = nodes[index];
        for (int i : node.edges) {
            if (!isReached[i]) {
                isReached[i] = true;
                dfs(nodes, i, isReached);
            }
        }
    }

    public static boolean judge(HashSet<Integer> set1, HashSet<Integer> set2) {
        for (int i :set1) {
            if (set2.contains(i)) {
                return false;
            }
        }
        return true;
    }
}

class Node{
    int index;
    ArrayList<Integer> edges;

    public Node(int index, ArrayList<Integer> edges) {
        this.index = index;
        this.edges = edges;
    }
}

全部评论
这个应该就是并差集吧,然后特判一下那种所有人都不会一门语言的情况就行了
点赞 回复 分享
发布于 2023-10-20 09:58 美国
这个有没有差不多的题呀,感觉这个东西不好说
点赞 回复 分享
发布于 2023-10-15 13:08 湖北

相关推荐

点赞 评论 收藏
分享
07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务