C++刷LeetCode（1733. 需要教语言的最少人数***）【数学】

糖逗

题目描述：

1. 
   
2. 在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
   
3. 
   
4. 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
   
5. 
   
6. 总共有 n 种语言，编号从 1 到 n 。
   
7. languages[i] 是第 i 位用户掌握的语言集合。
   
8. friendships[i] = [u​​​​​​i​​​, v​​​​​​i] 表示 u​​​​​​​​​​​i​​​​​ 和 vi 为好友关系。
   
9. 你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
   
10. 
    
11. 请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
    
12. 
    
13. 
    
14. 示例 1：
    
15. 
    
16. 输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
    
17. 输出：1
    
18. 解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
    
19. 示例 2：
    
20. 
    
21. 输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
    
22. 输出：2
    
23. 解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
    
24. 
    
25. 
    
26. 提示：
    
27. 
    
28. 2 <= n <= 500
    
29. languages.length == m
    
30. 1 <= m <= 500
    
31. 1 <= languages[i].length <= n
    
32. 1 <= languages[i][j] <= n
    
33. 1 <= u&#8203;&#8203;&#8203;&#8203;&#8203;&#8203;i < v&#8203;&#8203;&#8203;&#8203;&#8203;&#8203;i <= languages.length
    
34. 1 <= friendships.length <= 500
    
35. 所有的好友关系 (u&#8203;&#8203;&#8203;&#8203;&#8203;i, v&#8203;&#8203;&#8203;&#8203;&#8203;&#8203;i) 都是唯一的。
    
36. languages[i] 中包含的值互不相同。

复制代码

1. class Solution {
   
2. public:
   
3.     //判断两个人之间是否有共同语言
   
4.     bool solution(vector<vector<int> >&language, int i, int j){
   
5.         vector<int>temp1 = language[i-1];
   
6.         vector<int>temp2 = language[j-1];
   
7.         for(auto cha1 : temp1){
   
8.             for(auto cha2 : temp2){
   
9.                 if(cha1 == cha2)return true;
   
10.             }
    
11.         }
    
12.         return false;
    
13.     }
    
14.     int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
    
15.         map<int, int>store1;
    
16.         map<int, int>store2;
    
17.         //记录每个人在自己的好友名单中，没有共同语言的好友人数
    
18.         for(int i = 0; i < friendships.size(); i++){
    
19.             if(!solution(languages, friendships[i][0], friendships[i][1])){
    
20.                 store1[friendships[i][0]]++;
    
21.                 store1[friendships[i][1]]++;
    
22.             }
    
23.         }
    
24.         //统计store1中所有人会的语言和语言数
    
25.         for (auto p: store1) {
    
26.             for (auto language: languages[p.first-1]) {
    
27.                 store2[language]++;
    
28.             }
    
29.         }
    
30.         //找到最通用的语言
    
31.         int store = 0;
    
32.         for(auto cha : store2){
    
33.             store = max(store, cha.second);
    
34.         }
    
35. 
    
36.         return store1.size() - store;
    
37.     }
    
38. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ong-tong-yu-y-eptr/

糖逗

几级石阶

这是啥大神，占个沙发观望。