今天继续进行并查集的应用训练
题目
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，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)"]
分析
本题仍然是一道判断连通性的题目，不同姓名通过synonyms来表示了连通关系，因为最终的结果返回的是存在连通关系的姓名所对应数量的总和，所以，使用并查集将存在连通关系的名字合并并存储，最终统计每颗树下的名字总量即可。
并查集在本题中如何使用
- 分量是什么？
本题中分量即为不同的名字 - 结果返回什么？
题目要求结果同名的全部数量， 即并查集中每颗树的名字总量
并查集中树的定义
将有合并关系的名字合并倒一棵树中，最终有多少棵树，就应该返回多少个结果。
合并操作的前置判断
在给入的synonyms数组中，如果两个名字判断相同，则需要把两个分量合并
注意点一
本题相较于以往不同的地方在于，没有办法直接通过数组下标与数组值的关系来维护树的归属关系，原因有二
1、因为数组下标为整型，而姓名为String；
2、全量的名字总数没办法一次获取到，需要遍历两个入参来获取。
所以，这里采用一个Map来维护父子关系
注意点二
树的父子关系不能简单通过权重来比较，而应该通过字符串的字典顺序，在合并分量时需要通过String的CompareTo方法来判断字段顺序。
注意点三
最终返回的结果是返回每棵树的姓名总量，并查集从下至上寻找比较容易，从上之下寻找比较繁琐，所以在合并操作的时候，将姓名数量直接累加到根节点上，最终直接获取总量即可。
解题步骤
1、改造并查集，通过两个map标识父子关系，和名字所对应的数量。
2、解析names，将姓名和姓名数量初始化到并查集中。
3、解析synonyms，需要注意synonyms中可能会出现names未出现的姓名，需要判断并初始化到并查集中。
4、合并存在连通关系的name，需要注意此处要根据字典顺序建立父子关系。
5、构建结果集，返回根节点的姓名及姓名数量。
代码书写
并查集改造
class trulyMostPopularUnionFind {
// 因为是字符串分量,而且不能初始化大小,存储采用map
Map<String, String> name2ParentNameMap;
// 存储分量名字数量
Map<String, Integer> name2NameCountMap;
public trulyMostPopularUnionFind() {
// 初始化分量map
this.name2ParentNameMap = new HashMap<>();
// 初始化分量对应数量mmap
this.name2NameCountMap = new HashMap<>();
}
String find(String name) {
if (name2ParentNameMap.get(name).equals(name)) return name;
// 路径压缩
String parentName = find(name2ParentNameMap.get(name));
name2ParentNameMap.put(name, parentName);
return parentName;
}
void union(String name1, String name2) {
// 找到分量对应的标识
String p1 = find(name1);
String p2 = find(name2);
if (p1.equals(p2)) {
// 如果两个分量在同一颗树中,不需要合并
return;
}
// 采用字典顺序标识父子关系
// 同时将分量对应的名字数量增加到父节点上
if (p1.compareTo(p2) < 0) {
name2ParentNameMap.put(p2, p1);
name2NameCountMap.put(p1, name2NameCountMap.get(p1) + name2NameCountMap.get(p2));
} else {
name2ParentNameMap.put(p1, p2);
name2NameCountMap.put(p2, name2NameCountMap.get(p1) + name2NameCountMap.get(p2));
}
}
int getCount(String name) {
// 返回父节点的名字数量
String parentName = find(name);
return name2NameCountMap.get(parentName);
}
public Map<String, String> getName2ParentNameMap() {
return name2ParentNameMap;
}
public void setName2ParentNameMap(Map<String, String> name2ParentNameMap) {
this.name2ParentNameMap = name2ParentNameMap;
}
public Map<String, Integer> getName2NameCountMap() {
return name2NameCountMap;
}
public void setName2NameCountMap(Map<String, Integer> name2NameCountMap) {
this.name2NameCountMap = name2NameCountMap;
}
}
算法代码书写
class Solution {
public String[] trulyMostPopular(String[] names, String[] synonyms) {
trulyMostPopularUnionFind uf = new trulyMostPopularUnionFind();
List<String> trueNameList = new ArrayList<>();
for (String name : names) {
int indexCountStart = name.indexOf('(');
int indexCountEnd = name.indexOf(')');
String trueName = name.substring(0, indexCountStart);
trueNameList.add(trueName);
int count = Integer.valueOf(name.substring(indexCountStart + 1, indexCountEnd));
// 初始化时,每个分量的父节点指向自己
uf.name2ParentNameMap.put(trueName, trueName);
// 初始化时,每个分量的名字数量
uf.name2NameCountMap.put(trueName, count);
}
// 合并操作
for (String synonym : synonyms) {
String[] twoNames = synonym.substring(1, synonym.length() - 1).split(",");
// 待合并的分量可能不存在于names中,需要判断并初始化
for (String twoName : twoNames) {
if (!uf.name2ParentNameMap.containsKey(twoName)) {
uf.name2ParentNameMap.put(twoName, twoName);
}
if (!uf.name2NameCountMap.containsKey(twoName)) {
uf.name2NameCountMap.put(twoName, 0);
}
}
uf.union(twoNames[0], twoNames[1]);
}
// 统计根节点姓名,并拼装数量返回
List<String> res = new ArrayList<>();
for (String trueName : trueNameList) {
// 只有根节点才处理
String parentName = uf.find(trueName);
if (trueName.equals(parentName)) {
String resString = parentName + "(" + uf.getCount(parentName) + ")";
res.add(resString);
}
}
return res.toArray(new String[res.size()]);
}
}
网友评论