铜梁城乡建设网站,网站电话素材,个人怎样做网站,百度云账号登录每年#xff0c;政府都会公布一万个最常见的婴儿名字和它们出现的频率#xff0c;也就是同名婴儿的数量。有些名字有多种拼法#xff0c;例如#xff0c;John 和 Jon 本质上是相同的名字#xff0c;但被当成了两个名字公布出来。给定两个列表#xff0c;一个是名字及对应…每年政府都会公布一万个最常见的婴儿名字和它们出现的频率也就是同名婴儿的数量。有些名字有多种拼法例如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)”]
代码
class Solution {int[] strFa;public void strInit()//并查集操作{for(int i0;istrFa.length;i)strFa[i]i;}public int strFind(int x){if(x!strFa[x])strFa[x]strFind(strFa[x]);return strFa[x];}public void strUnion(int x,int y){xstrFind(x);ystrFind(y);if(xy) return;if(map.get(y).compareTo(map.get(strFa[x]))0)//按字典序确定父节点strFa[x]y;else strFa[y]x;} MapInteger,Stringmapnew HashMap();public String[] trulyMostPopular(String[] names, String[] synonyms) {int nnames.length;strFanew int[n];strInit();MapString,Integermap2new HashMap(); int[] resnew int[n];for(int i0;in;i)//将名字和对应的编号用map记录{String[] namenames[i].split([()]);map.put(i,name[0]);map2.put(name[0],i);res[i]Integer.parseInt(name[1]);}ListString listnew ArrayList();for(String s:synonyms)//构建并查集{String name1s.substring(1,s.indexOf(,));String name2s.substring(s.indexOf(,)1,s.length()-1);if(map2.containsKey(name1)map2.containsKey(name2))strUnion(map2.get(name1),map2.get(name2));}for(int i0;in;i)//将子节点的值累加到父节点{if(strFa[i]!i) res[strFind(i)]res[i];}for(int i0;in;i)//返回所有的不相交的父节点if(strFa[i]i){list.add(map.get(i)(res[i]));}String[] retnew String[list.size()];for(int i0;ilist.size();i)ret[i]list.get(i);return ret;}
}
