leetcode 笔记
题目描述
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。
示例 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']] 也是正确的。
提示：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/accounts-merge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
code
又是并查集。
每个邮箱给一个独一无二的index, 错开原有的[0, accounts.size())；用户用原有的数组下标做index。
每个邮箱找父节点，如果为自己，则父节点指定为当前用户index， 如果已属于其他用户，则当前用户的父节点指定为其他用户，从而实现合并。
kotlin, scala可以用Map<Any, Any>维护父节点关系，这样可以省掉邮箱String到Int的映射关系。
-
c++
class Solution {
private:
int find_parent(unordered_map<int, int>& par, int x) {
if (!par.count(x)) return par[x] = x;
return par[x] = par[x] == x ? x : find_parent(par, par[x]);
}
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
unordered_map<string, int> s_index;
unordered_map<int, int> par;
auto get_index = [&](const string& x) -> int {
return s_index.count(x) ? s_index[x] : (s_index[x] = -s_index.size() - 1);
};
for (int i = 0; i < accounts.size(); i++)
for (int j = 1, pre = i; j < accounts[i].size(); j++) {
int si = get_index(accounts[i][j]);
int p = find_parent(par, si);
if (p == si)
par[si] = pre;
else{
par[pre] = p;
pre = p;
}
}
unordered_map<int, set<string>> mp;
for (auto& i : s_index) mp[find_parent(par, i.second)].insert(i.first);
vector<vector<string>> res;
for (auto& i : mp) {
res.push_back({accounts[i.first][0]});
for (auto& j : i.second) res.back().push_back(j);
}
return res;
}
};
-
kotlin
一刀流
fun accountsMerge(accounts: List<List<String>>): List<List<String>> = accounts.foldIndexed(mutableMapOf<Any, Any>()) { index, par, list -> (1..list.lastIndex).forEach { i -> when (val p = par.findParent(list[i])) {list[i] -> par[p] = par.findParent(index);else -> par[par.findParent(index)] = p } };par }.let { par -> par.entries.fold(mutableMapOf<Int, MutableList<String>>()) { acc, (k, v) -> if (k is String) acc.getOrPut(par.findParent(v) as Int) { mutableListOf() } += k;acc }.entries.fold(mutableListOf()) { acc, (k, v) -> acc.apply { add(listOf(accounts[k].first()) + v.sorted()) } } }
class Solution {
private tailrec fun MutableMap<Any, Any>.findParent(x: Any): Any =
if (this.getOrPut(x) { x } != x) findParent(this[x]!!) else x
fun accountsMerge(accounts: List<List<String>>): List<List<String>> =
accounts.foldIndexed(mutableMapOf<Any, Any>()) { index, par, list ->
(1..list.lastIndex).forEach { i ->
when (val p = par.findParent(list[i])) {
list[i] -> par[p] = par.findParent(index)
else -> par[par.findParent(index)] = p
}
}
par
}.let { par ->
par.entries.fold(mutableMapOf<Int, MutableList<String>>()) { acc, (k, v) ->
if (k is String) acc.getOrPut(par.findParent(v) as Int) { mutableListOf() } += k
acc
}.entries.fold(mutableListOf()) { acc, (k, v) ->
acc.apply { add(listOf(accounts[k].first()) + v.sorted()) }
}
}
}
-
scala
import scala.annotation.tailrec
import scala.collection.mutable
object Solution {
@tailrec
private def findParent(par: mutable.Map[Any, Any], x: Any): Any = if (par.getOrElseUpdate(x, x) != x) findParent(par, par(x)) else x
def accountsMerge(accounts: List[List[String]]): List[List[String]] = {
val par = accounts.indices.foldLeft(mutable.Map[Any, Any]())((par, i) => {
(1 until accounts(i).length).foreach(j =>
if (findParent(par, accounts(i)(j)) == accounts(i)(j))
par(accounts(i)(j)) = findParent(par, i)
else
par(findParent(par, i)) = findParent(par, accounts(i)(j)))
par
})
par.foldLeft(mutable.Map[Int, mutable.ListBuffer[String]]())((acc, i) => {
i._1 match {
case str: String => acc.getOrElseUpdate(findParent(par, i._2).asInstanceOf[Int], mutable.ListBuffer()).addOne(str)
case _ => None
}
acc
}).foldLeft(mutable.ListBuffer[List[String]]())((acc, i) => acc.addOne(accounts(i._1).head :: i._2.sorted.toList)).toList
}
}
-
rust
use std::collections::HashMap;
impl Solution {
pub fn accounts_merge(accounts: Vec<Vec<String>>) -> Vec<Vec<String>> {
fn find_parent(par: &mut HashMap<i32, i32>, x: i32) -> i32 {
if par.entry(x).or_insert(x).clone() != x {
let p = find_parent(par, par[&x]);
par.insert(x, p);
p
} else {
x
}
};
let mut str2i: HashMap<&String, i32> = HashMap::new();
let mut par = accounts
.iter()
.enumerate()
.fold(HashMap::new(), |mut par, (i, list)| {
(1..list.len()).for_each(|j| {
let len = str2i.len() as i32;
let si = *str2i.entry(&list[j]).or_insert(-len - 1);
let p = find_parent(&mut par, si);
if p == si {
let p = find_parent(&mut par, i as i32);
par.insert(si, p);
} else {
let p2 = find_parent(&mut par, i as i32);
par.insert(p, p2);
}
});
par
});
str2i
.drain()
.fold(HashMap::new(), |mut mp, (k, v)| {
mp.entry(find_parent(&mut par, v))
.or_insert(vec![])
.push(k.clone());
mp
})
.drain()
.fold(vec![], |mut acc, (i, mut l)| {
l.sort();
l.insert(0, accounts[i as usize][0].clone());
acc.push(l);
acc
})
}
}