Leetcode(1700-1799)

leetcode1733

在一个由 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] 中包含的值互不相同。

解答

1. 找到所有无法交流的好友对
2. 遍历每个语言，尝试为无法交流的好友加上这个语言，统计需要的最少人数

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    
    /**
     * 计算最少需要教多少个人某种语言，使得所有朋友之间能够交流
     */
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        List<int[]> uncommunicativePairs = new ArrayList<>();
        
        for (int i = 0; i < friendships.length; i++) {
            int userA = friendships[i][0];
            int userB = friendships[i][1];
            int[] languagesA = languages[userA - 1];
            int[] languagesB = languages[userB - 1];
            
            // 正确调用：非静态方法调用非静态方法
            if (!hasCommonLanguage(languagesA, languagesB)) {
                uncommunicativePairs.add(new int[]{userA, userB});
            }
        }
        
        int minTeachings = Integer.MAX_VALUE;
        
        for (int targetLanguage = 1; targetLanguage <= n; targetLanguage++) {
            int teachingCount = 0;
            int[] taughtUsers = new int[languages.length + 1];
            
            for (int[] pair : uncommunicativePairs) {
                int userA = pair[0];
                int userB = pair[1];
                
                List<Integer> languagesOfA = Arrays.stream(languages[userA - 1])
                        .boxed()
                        .toList();
                List<Integer> languagesOfB = Arrays.stream(languages[userB - 1])
                        .boxed()
                        .toList();
                
                if (!languagesOfA.contains(targetLanguage) && taughtUsers[userA] != 1) {
                    teachingCount++;
                    taughtUsers[userA] = 1;
                }
                
                if (!languagesOfB.contains(targetLanguage) && taughtUsers[userB] != 1) {
                    teachingCount++;
                    taughtUsers[userB] = 1;
                }
            }
            
            minTeachings = Math.min(minTeachings, teachingCount);
        }
        
        return minTeachings;
    }
    
    /**
     * 检查两个语言数组是否有共同语言
     * 保持为非静态方法以匹配调用方式
     */
    private boolean hasCommonLanguage(int[] languagesA, int[] languagesB) {
        for (int langA : languagesA) {
            for (int langB : languagesB) {
                if (langA == langB) {
                    return true;
                }
            }
        }
        return false;
    }
}