网站的风格主要包括,恩施市网站建设,网站建站网站jp586 vip,中国菲律宾男篮直播1. 题目
每年#xff0c;政府都会公布一万个最常见的婴儿名字和它们出现的频率#xff0c;也就是同名婴儿的数量。 有些名字有多种拼法#xff0c;例如#xff0c;John 和 Jon 本质上是相同的名字#xff0c;但被当成了两个名字公布出来。
给定两个列表#xff0c;一个…1. 题目
每年政府都会公布一万个最常见的婴儿名字和它们出现的频率也就是同名婴儿的数量。 有些名字有多种拼法例如John 和 Jon 本质上是相同的名字但被当成了两个名字公布出来。
给定两个列表一个是名字及对应的频率另一个是本质相同的名字对。 设计一个算法打印出每个真实名字的实际频率。 注意如果 John 和 Jon 是相同的并且 Jon 和 Johnny 相同则 John 与 Johnny 也相同即它们有传递和对称性。
在结果列表中选择字典序最小的名字作为真实名字。
示例
输入names [John(15),Jon(12),Chris(13),Kris(4),Christopher(19)],
synonyms [(Jon,John),(John,Johnny),(Chris,Kris),(Chris,Christopher)]
输出[John(27),Chris(36)]提示
names.length 100000来源力扣LeetCode 链接https://leetcode-cn.com/problems/baby-names-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
参考并查集Disjoint-Set
相关题目 LeetCode 959. 由斜杠划分区域并查集 LeetCode 1202. 交换字符串中的元素并查集
class Solution {unordered_mapstring,string father;//并查集unordered_mapstring,int m;//名称频次
public:vectorstring trulyMostPopular(vectorstring names, vectorstring synonyms) {string name, name1, name2, p;int i, count;for(string n : names){i n.find(();name n.substr(0,i);count 0;while(i n.size()-1)count 10*countn[i]-0;m[name] count;//获取每个名字的次数father[name] name;//并查集初始化}for(auto n : synonyms){ //这里可能有上面不存在的name再添加一遍i n.find(,);name1 n.substr(1,i-1);name2 n.substr(i1,n.size()-i-2);father[name1] name1;//并查集初始化father[name2] name2;//并查集初始化}for(auto n : synonyms){i n.find(,);name1 n.substr(1,i-1);name2 n.substr(i1,n.size()-i-2);merge(name1,name2);//全部进行合并和路径压缩}unordered_mapstring,vectorstring fatherSet;for(auto f : father)//压缩后的f(只有两层)所有边的顶层字典序最小的{name f.first;p uniFind(name);fatherSet[p].push_back(name);}vectorstring ans;for(auto f : fatherSet){ //所有的等效名字count 0;for(auto v : f.second)//它底下包含的namecount m[v];//加上他的计数ans.push_back(f.first(to_string(count)));}return ans;}string uniFind(string x){if(x father[x])return x;return father[x] uniFind(father[x]);//等式为路径压缩操作}void merge(string x, string y){string fatherx uniFind(x);string fathery uniFind(y);if(fatherx ! fathery){if(fatherx fathery)swap(fatherx, fathery);//x的字典序大father[fatherx] fathery;//字典序小的y做代表}}
};写的比较差效率比较低
