LeetCode
面试题 17.07.婴儿名字
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，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 {
public String[] trulyMostPopular(String[] names, String[] synonyms) {
Map<String, Integer> map = new HashMap<>();
Map<String, String> unionMap = new HashMap<>(); //并查集， key(子孙)->value(祖宗)
for (String name : names)
{ //统计频率
int idx1 = name.indexOf('(');
int idx2 = name.indexOf(')');
int frequency = Integer.valueOf(name.substring(idx1 + 1, idx2));
map.put(name.substring(0, idx1), frequency);
}
for (String pair : synonyms)
{ //union同义词
int idx = pair.indexOf(',');
String name1 = pair.substring(1, idx);
String name2 = pair.substring(idx + 1, pair.length() - 1);
while (unionMap.containsKey(name1))
{ //找name1祖宗
name1 = unionMap.get(name1);
}
while (unionMap.containsKey(name2))
{ //找name2祖宗
name2 = unionMap.get(name2);
}
if(!name1.equals(name2))
{ //祖宗不同，要合并
int frequency = map.getOrDefault(name1, 0) + map.getOrDefault(name2, 0); //出现次数是两者之和
String trulyName = name1.compareTo(name2) < 0 ? name1 : name2;
String nickName = name1.compareTo(name2) < 0 ? name2 : name1;
unionMap.put(nickName, trulyName); //小名作为大名的分支，即大名是小名的祖宗
map.remove(nickName); //更新一下数据
map.put(trulyName, frequency);
}
}
String[] res = new String[map.size()];
int index = 0;
for (String name : map.keySet())
{
StringBuilder sb = new StringBuilder(name);
sb.append('(');
sb.append(map.get(name));
sb.append(')');
res[index++] = sb.toString();
}
return res;
}
}
解法来源
作者：accountofjizhiwei
链接：https://leetcode-cn.com/problems/baby-names-lcci/solution/bing-cha-ji-si-lu-yong-hashmapzuo-95ms-by-accounto/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
感想
在做这道题时，其实我的思路还是挺清晰的，但是太执着于用parent数组来实现并查集，没想到还可以用哈希表来当做并查集的树，学到了
