从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结
721. 账户合并
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
示例 1：
输入：accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”], [“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”, “john_newyork@mail.com”], [“Mary”, “mary@mail.com”]]
输出：[[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”, “mary@mail.com”]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com”。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail.com’]，[‘John’，‘johnnybravo@mail.com’]，
[‘John’，‘john00@mail.com’，‘john_newyork@mail.com’，‘johnsmith@mail.com’]] 也是正确的。
示例 2：
输入：accounts = [[“Gabe”,“Gabe0@m.co”,“Gabe3@m.co”,“Gabe1@m.co”],[“Kevin”,“Kevin3@m.co”,“Kevin5@m.co”,“Kevin0@m.co”],[“Ethan”,“Ethan5@m.co”,“Ethan4@m.co”,“Ethan0@m.co”],[“Hanzo”,“Hanzo3@m.co”,“Hanzo1@m.co”,“Hanzo0@m.co”],[“Fern”,“Fern5@m.co”,“Fern1@m.co”,“Fern0@m.co”]]
输出：[[“Ethan”,“Ethan0@m.co”,“Ethan4@m.co”,“Ethan5@m.co”],[“Gabe”,“Gabe0@m.co”,“Gabe1@m.co”,“Gabe3@m.co”],[“Hanzo”,“Hanzo0@m.co”,“Hanzo1@m.co”,“Hanzo3@m.co”],[“Kevin”,“Kevin0@m.co”,“Kevin3@m.co”,“Kevin5@m.co”],[“Fern”,“Fern0@m.co”,“Fern1@m.co”,“Fern5@m.co”]]
提示：
1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 由英文字母组成
accounts[i][j] (for j > 0) 是有效的邮箱地址
解题思路：
本题和用整型作为元素标记的并查集解法是一样的，数组下标表示当前元素，数组下标对应的数组值表示该元素所处的集合，是一种映射关系。这里是字符串来表示元素，对应的字符串表示该元素所处的集合，直接通过哈希表来实现了这种字符串到字符串的映射。文章来源：https://www.toymoban.com/news/detail-427018.html
首先通过哈希表建立并查集，哈希表的键值对都是字符串，然后将一个账户中所有的邮箱并查集合并；
利用一个哈希表暂时存储邮箱列表，将所有邮箱存到并查集中根元素对应的列表中;
最后进行输出，遍历上面根元素邮箱列表，进行排序和加入账户名即可。
这题和之前做的这道题是一个套路的，都是用字符串作为并查集的标记元素。文章来源地址https://www.toymoban.com/news/detail-427018.html
class Solution {
// 利用一个字符串的映射存储并查集
Map<String, String> q;
public List<List<String>> accountsMerge(List<List<String>> accounts) {
q = new HashMap<>();
// 这个映射存储每个邮箱对应账户的名字
Map<String, String> names = new HashMap<>();
// 遍历所有账户构建并查集
for(List<String> a : accounts) {
for(int i = 1; i < a.size(); i++) {
if(!q.containsKey(a.get(i))){
// 如果并查集中没有这个邮箱，则添加邮箱，其根元素就是本身
q.put(a.get(i), a.get(i));
// 添加该邮箱对应的账户名
names.put(a.get(i), a.get(0));
}
if(i > 1) {
// 并查集的合并操作，合并一个账户中的所有邮箱
q.put(find(a.get(i)), find(a.get(i - 1)));
}
}
}
// 暂时存储答案中的邮箱列表，每个键值对的键就是每个并查集集合的根元素
Map<String, List<String>> temp = new HashMap<>();
for(String email : q.keySet()) {
// 获取当前邮箱对应并查集的根元素
String root = find(email);
// 将当前邮箱放入根元素对应的列表中
if(!temp.containsKey(root)) temp.put(root, new ArrayList<>());
temp.get(root).add(email);
}
// 将答案从映射中放到列表
List<List<String>> res = new ArrayList();
for(String root : temp.keySet()) {
// 获取当前根元素对应的列表
List<String> layer = temp.get(root);
// 题目要求的排序
Collections.sort(layer);
// 添加姓名
layer.add(0, names.get(root));
// 将当前列表加入答案
res.add(layer);
}
return res;
}
// 并查集查找模板函数，这里用字符串替换了之前的整型
// find就是一个寻根归祖的方法，寻找当前元素最终将属于哪个根元素，这个根元素来表示一个联通集合
// 如果x映射的值等于x，那就可以说明x是个根元素，例如一个集合中只有一个元素，那么它当然可以代表自己
// 这样做可以让一个集合中的所有元素都能直接或者间接指向根元素，一个集合中只有一个元素的映射是本身
private String find(String x) {
// 判断x是不是就是一个根元素
if(!q.get(x).equals(x)) {
// x不是根，那就通过递归find函数来找到x映射的元素的根元素（寻根）
// 找到根元素之后，通过put方法将x直接映射到根元素，这样就免去中间的多次递归（归祖）
q.put(x, find(q.get(x)));
}
// 最终，x映射的元素就是x所在的集合的根元素，返回x的根元素
return q.get(x);
}
}
到了这里，关于Leetcode力扣秋招刷题路-0721的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
