长沙网站建设有限公司,新乡市建设工程网站,化妆品网站程序,贵阳做网站的公司文章目录1. 题目2. 解题1. 题目
在一个由 m 个用户组成的社交网络里#xff0c;我们获取到一些用户之间的好友关系。 两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数 n #xff0c;数组 languages 和数组 friendships #xff0c;它们的含义如下我们获取到一些用户之间的好友关系。 两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
会做但是比赛的时候一个变量写错了一直过不去。。。 先把每种语言会的人放在一起检查关系列表看每对关系之间是否能交流枚举每种语言跳过能沟通的两个人不会这种语言的就学习计数1
class Solution {
public:int minimumTeachings(int n, vectorvectorint languages, vectorvectorint friendships) {int p languages.size(); // 人数unordered_mapint, unordered_setint lang_peoples;//语言 - 会的人集合for(int i 0; i p; i) {for(auto l : languages[i])lang_peoples[l].insert(i);}vectorbool canspeak(friendships.size(), false);//能沟通吗for(int i 0; i friendships.size(); i){int a friendships[i][0]-1, b friendships[i][1]-1;for(auto lp : lang_peoples){if(lp.second.count(a) lp.second.count(b)){canspeak[i] true;break;}}}// 这里比赛的时候写成了 n-1, 我哭了我就说逻辑没错啊。。。int teach p-1, count 0; //至少要教 p-1个人for(auto lp : lang_peoples){ // 遍历语言count 0;for(int i 0; i friendships.size(); i){ // 遍历关系int a friendships[i][0]-1, b friendships[i][1]-1;if(canspeak[i])//能沟通的忽略continue;if(!lp.second.count(a)){ //不能沟通且不会这种语言学习lp.second.insert(a);count;}if(!lp.second.count(b)){ //不能沟通且不会这种语言学习lp.second.insert(b);count;}}teach min(teach, count);}return teach;}
};812 ms 142.8 MB C
or
不能沟通的人数减去这群人里说的最多的语言的人数就是最少要教的人
class Solution {
public:int minimumTeachings(int n, vectorvectorint languages, vectorvectorint friendships) {int p languages.size(); // 人数unordered_mapint, unordered_setint lang_peoples;//语言 - 会的人集合for(int i 0; i p; i) {for(auto l : languages[i])lang_peoples[l].insert(i);}vectorbool canspeak(friendships.size(), false);//能沟通吗for(int i 0; i friendships.size(); i){int a friendships[i][0]-1, b friendships[i][1]-1;for(auto lp : lang_peoples){if(lp.second.count(a) lp.second.count(b)){canspeak[i] true;break;}}}vectorint lang_people_can_say(n,0);unordered_setint pp;//不能沟通的人们for(int i 0; i friendships.size(); i){ // 遍历关系if(canspeak[i])//能沟通的忽略continue;int a friendships[i][0]-1, b friendships[i][1]-1;if(!pp.count(a)){pp.insert(a);for(auto l : languages[a])lang_people_can_say[l-1];//统计不能沟通的人会说的语言}if(!pp.count(b)){pp.insert(b);for(auto l : languages[b])lang_people_can_say[l-1];//统计不能沟通的人会说的语言}}return pp.size() - *max_element(lang_people_can_say.begin(),lang_people_can_say.end());}
};648 ms 138.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
