马鞍山建设集团有限公司网站,网站建设文字表达,营销策略有哪些方面,种子搜索神器1 题目#xff1a;账户合并
官方标定难度#xff1a;中
给定一个列表 accounts#xff0c;每个元素 accounts[i] 是一个字符串列表#xff0c;其中第一个元素 accounts[i][0] 是 名称 (name)#xff0c;其余元素是 emails 表示该账户的邮箱地址。
现在#xff0c;我们…1 题目账户合并
官方标定难度中
给定一个列表 accounts每个元素 accounts[i] 是一个字符串列表其中第一个元素 accounts[i][0] 是 名称 (name)其余元素是 emails 表示该账户的邮箱地址。
现在我们想合并这些账户。如果两个账户都有一些共同的邮箱地址则两个账户必定属于同一个人。请注意即使两个账户具有相同的名称它们也可能属于不同的人因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户但其所有账户都具有相同的名称。
合并账户后按以下格式返回账户每个账户的第一个元素是名称其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
示例 1
输入accounts [[“John”, “johnsmithmail.com”, “john00mail.com”], [“John”, “johnnybravomail.com”], [“John”, “johnsmithmail.com”, “john_newyorkmail.com”], [“Mary”, “marymail.com”]] 输出[[“John”, ‘john00mail.com’, ‘john_newyorkmail.com’, ‘johnsmithmail.com’], [“John”, “johnnybravomail.com”], [“Mary”, “marymail.com”]] 解释 第一个和第三个 John 是同一个人因为他们有共同的邮箱地址 “johnsmithmail.com”。 第二个 John 和 Mary 是不同的人因为他们的邮箱地址没有被其他帐户使用。 可以以任何顺序返回这些列表例如答案 [[‘Mary’‘marymail.com’][‘John’‘johnnybravomail.com’] [‘John’‘john00mail.com’‘john_newyorkmail.com’‘johnsmithmail.com’]] 也是正确的。
示例 2
输入accounts [[“Gabe”,“Gabe0m.co”,“Gabe3m.co”,“Gabe1m.co”],[“Kevin”,“Kevin3m.co”,“Kevin5m.co”,“Kevin0m.co”],[“Ethan”,“Ethan5m.co”,“Ethan4m.co”,“Ethan0m.co”],[“Hanzo”,“Hanzo3m.co”,“Hanzo1m.co”,“Hanzo0m.co”],[“Fern”,“Fern5m.co”,“Fern1m.co”,“Fern0m.co”]] 输出[[“Ethan”,“Ethan0m.co”,“Ethan4m.co”,“Ethan5m.co”],[“Gabe”,“Gabe0m.co”,“Gabe1m.co”,“Gabe3m.co”],[“Hanzo”,“Hanzo0m.co”,“Hanzo1m.co”,“Hanzo3m.co”],[“Kevin”,“Kevin0m.co”,“Kevin3m.co”,“Kevin5m.co”],[“Fern”,“Fern0m.co”,“Fern1m.co”,“Fern5m.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) 是有效的邮箱地址
2 solution
将每一个 email 映射成账户 index如果该 email 之前出现过就将 index 合并将合并的 index 进行 email 的合并并保证升序排列将账户名加入到结果中
代码
class Solution {/** 存在邮箱相同就进行合并* map: email index**/vectorint f;int find(int x) {return f[x] x ? x : (f[x] find(f[x]));}public:vectorvectorstring accountsMerge(vectorvectorstring accounts) {unordered_mapstring, int mapp;int n accounts.size();f vectorint(n);for (int i 0; i n; i) f[i] i;for (int i 0; i n; i) {for (int j 1; j accounts[i].size(); j) {if (mapp.count(accounts[i][j])) {f[find(i)] find(mapp[accounts[i][j]]);} else {mapp[accounts[i][j]] find(i);}}}unordered_mapint, setstring s;for (int i 0; i n; i) {for (int j 1; j accounts[i].size(); j) {s[find(i)].insert(accounts[i][j]);}}vectorvectorstring res;for (int i 0; i n; i) {if (find(i) i) {res.push_back({accounts[i][0]});for (auto x: s[i])res.back().push_back(x);}}return res;}
};结果
