LeetCode——1733. 需要教语言的最少人数(Minimum Number of People to Teach)——分析及代码(Java)

LeetCode——1733. 需要教语言的最少人数[Minimum Number of People to Teach]——分析及代码[Java]

一、题目

在一个由 m 个用户组成的社交网络里,我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数 n ,数组 languages 和数组 friendships ,它们的含义如下:

  • 总共有 n 种语言,编号从 1 到 n。
  • languages[i] 是第 i 位用户掌握的语言集合。
  • friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。

你可以选择 一门 语言并教会一些用户,使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
请注意,好友关系没有传递性,也就是说如果 x 和 y 是好友,且 y 和 z 是好友, x 和 z 不一定是好友。

示例 1:

输入:n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出:1
解释:你可以选择教用户 1 第二门语言,也可以选择教用户 2 第一门语言。

示例 2:

输入:n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出:2
解释:教用户 1 和用户 3 第三门语言,需要教 2 名用户。

提示:

  • 2 <= n <= 500
  • languages.length == m
  • 1 <= m <= 500
  • 1 <= languages[i].length <= n
  • 1 <= languages[i][j] <= n
  • 1 <= ui < vi <= languages.length
  • 1 <= friendships.length <= 500
  • 所有的好友关系 (ui, vi) 都是唯一的。
  • languages[i] 中包含的值互不相同。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-number-of-people-to-teach
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、分析及代码

1. 遍历

(1)思路

由于好友关系没有传递性,无需使用并查集等方法,可以直接遍历求解。
先确定目前无法相互沟通的好友对,然后分别计算每种语言需要教会的人数,求出答案。

(2)代码

class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        boolean[][] lang = new boolean[m][n + 1];//记录各人语言掌握情况
        for (int i = 0; i < m; i++)
            for (int j = 0; j <= n; j++)
                lang[i][j] = false;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < languages[i].length; j++)
                lang[i][languages[i][j]] = true;
        
        //记录已经可以相互沟通的好友对
        boolean[] teach = new boolean[friendships.length];
        for (int i = 0; i < friendships.length; i++)
            teach[i] = (needTeach(languages, lang, friendships[i][0] - 1, friendships[i][1] - 1)) ? true : false;
        
        int ans = m;
        for (int i = 1; i <= n; i++) {
            int need = 0;//当前语言需要教会的人数
            boolean[] thisLang = new boolean[m];//当前语言已学会的人
            for (int j = 0; j < m; j++)
                thisLang[j] = lang[j][i];
            for (int k = 0; k < friendships.length; k++) {
                if (teach[k] == true) {
                    int p1 = friendships[k][0] - 1, p2 = friendships[k][1] - 1;
                    if (thisLang[p1] == false) {
                        need++;
                        thisLang[p1] = true;
                    }
                    if (thisLang[p2] == false) {
                        need++;
                        thisLang[p2] = true;
                    }
                }
            }
            ans = Math.min(ans, need);
        }
        return ans;
    }
    
    public boolean needTeach(int[][]languages, boolean[][] lang, int p1, int p2) {
        for (int i = 0; i < languages[p2].length; i++)
            if (lang[p1][languages[p2][i]] == true)
                return false;
        return true;
    }
}

(3)结果

执行用时 :16 ms,在所有 Java 提交中击败了 89.87% 的用户;
内存消耗 :50.5 MB,在所有 Java 提交中击败了 94.94% 的用户。

三、其他

暂无。

上一篇:【Java学习】Java 初始化List的5种方式


下一篇:还原工具mysqldump