- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: https://leetcode.com/problems/accounts-merge/description/
Given a list accounts
, each element accounts[i]
is a list of strings, where the first element accounts[i][0]
is a name, and the rest of the elements are emails representing emails of the account.
Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.
After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.
Example 1:
Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation:
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'],
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.
Note:
1、 Thelengthofaccountswillbeintherange[1,1000].;
2、 Thelengthofaccounts[i]willbeintherange[1,10].;
3、 Thelengthofaccounts[i][j]willbeintherange[1,30].;
给出一个账户列表,其中每一个账户由多个字符串组成,第一个字符串为姓名,其余的字符串为在该姓名下注册的邮箱地址。由于同一个人可能有两个不同的账户,判别是否是同一个人所拥有的账户方法就是在不同的账户中发现是否有相同的邮箱地址,如果有相同的邮箱地址,则可判定两个账户为同一人所拥有。现在要做的就是,对给定账户列表中同一个人所拥有的账户进行合并,合并结果为一个人只拥有一个账户,并且该账户包含其所有的邮箱并且不重复。 Note:同一人的账户可能有多个重名邮箱地址,输出的时候要对这部分进行处理去掉冗余部分,并且进行字典序排列。
这个题的解法是并查集,LeetCode 721. Accounts Mergeopen in new window对这个题有非常详细的讲解,包括并查集的知识,我就不班门弄斧了。另外,我把这个c++代码用python实现了一遍,时间复杂度应该比c++还要低一点,可是通过不了啊……尴尬。
这个问题本质上是对不同的集合进行处理,因此暴力求解法在这里几乎不可能成功。求解这个问题的方法最经典的思路就是并查集。
那么在本题所涉及的条件下,我们应该满足两个要求。
去除重复元素,并且有序排序
对于这个条件,很容易想到set集合(结合中没有重复元素,而且元素在插入的时候保持字典序),因此在实现的过程中,必要的一步就是将原有的邮箱列表装载到一个set集合中,然后进行如下的操作。
对含有相同元素的集合,进行合并。
这个步骤中,就要我们的刚学的并查集登场了。
代码如下,并没有通过OJ.
class Solution(object):
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
n = len(accounts)
self.par = [x for x in range(n)]
nameMap = collections.defaultdict(list)
for i, account in enumerate(accounts):
nameMap[account[0]].append(i)
for i in range(n):
for j in nameMap[accounts[i][0]]:
if (not self.same(i, j)) and (set(accounts[i][1:]) & set(accounts[j][1:])):
self.union(i, j)
res = [set() for _ in range(n)]
for i in range(n):
self.par[i] = self.find(i)
res[self.par[i]] |= set(accounts[i][1:])
ans = []
for i in range(n):
if self.par[i] == i:
person = list()
person.append(accounts[i][0])
person.extend(sorted(res[i]))
ans.append(person)
return ans
def find(self, x):
if x == self.par[x]:
return self.par[x]
parent = self.find(self.par[x])
self.par[x] = parent
return parent
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
self.par[x] = y
def same(self, x, y):
return self.find(x) == self.find(y)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
使用原文的c++代码能通过,时间是1204ms,这个对于c++来说已经很慢了。
const int N = 1000 + 5;
int n, par[N];
int find(int x) {
return par[x] == x ? x : (par[x] = find(par[x]));
}
void unit(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
par[x] = y;
}
bool same(int x, int y) {
return find(x) == find(y);
}
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
n = accounts.size();
for (int i = 0; i < n; i++) par[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) if (!same(i, j)) {
for (int k = 1; k < accounts[i].size(); k++) for (int t = 1; t < accounts[j].size(); t++) {
if (accounts[i][k] == accounts[j][t]) unit(i, j);
}
}
}
vector<set<string> > res; res.resize(n);
for (int i = 0; i < n; i++) {
par[i] = find(i);
for (int j = 1; j < accounts[i].size(); j++) res[par[i]].insert(accounts[i][j]);
}
vector<vector<string> > ret;
for (int i = 0; i < n; i++) if (par[i] == i) {
vector<string> cur;
cur.push_back(accounts[i][0]);
for (auto str : res[i]) cur.push_back(str);
ret.push_back(cur);
}
return ret;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
使用官方解答的并查集代码也能通过,说明在优化不够好的情况下,c++速度确实比python快了很多。
class Solution(object):
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
dsu = DSU()
em_to_name = dict()
em_to_id = dict()
i = 0
for acc in accounts:
name = acc[0]
for email in acc[1:]:
em_to_name[email] = name
if email not in em_to_id:
em_to_id[email] = i
i += 1
dsu.union(em_to_id[acc[1]], em_to_id[email])
ans = collections.defaultdict(list)
for email in em_to_name:
ans[dsu.find(em_to_id[email])].append(email)
return [[em_to_name[v[0]]] + sorted(v) for v in ans.values()]
class DSU:
def __init__(self):
self.par = range(10001)
def find(self, x):
if x != self.par[x]:
self.par[x] = self.find(self.par[x])
return self.par[x]
def union(self, x, y):
self.par[self.find(x)] = self.find(y)
def same(self, x, y):
return self.find(x) == self.find(y)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
参考资料:
https://blog.csdn.net/likewind1993/article/details/78473302 https://leetcode.com/articles/accounts-merge/
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我从一个 Mercurial 存储库开始,它有多个我试图 merge 到其中的子存储库,就好像它们一直是主存储库的一部分一样。它们从一开始就不应该是子存储库。 我整理了一个将旧历史转换为单个存储库的过
假设我有一个主线分支和一个功能分支。我已经多次将主线分支 merge 到功能分支中,但只有少数非常小的 merge 冲突。我想清理历史,以便最后只有一个 merge 。执行此操作的最佳方法是什么? 最
首先我使用heapq.merge创建了a&b的两个结果,但是在mergea&b之后,我发现a的列表是空的。 >>> a=merge([1,2],[3,4]) >>> b=merge([4,5],[6,
我和我的团队正在使用远离主轨道 (origin/dev) 的远程分支 (origin/our_feature_branch) 开发一项功能。 Gerrit用于审查等。 使用 git merge ori
这个问题在这里已经有了答案: Is there a way to merge with Strategy "ours" without producing a new commit? (1 个回答)
GitLab 无法自动 merge 请求。所有 merge 请求都会收到消息“此 merge 请求包含必须解决的 merge 冲突。您可以在命令行上手动尝试” 消息似乎不正确,我通过使用“git br
git 有没有办法在不 merge 文件的情况下 merge 两个分支?换句话说就是绘制 merge 箭头。 假设我有分支 A 和 B。我需要将分支 B merge 到 A,但不需要 B 中的所有更改
我想使用提供 git 集成的流行的开源问题跟踪器 (Redmine)。不幸的是,跟踪器中的每个项目只能与一个 git repo 相关联。在跟踪器中创建多个项目不是我理想的设置。 考虑到这一点,我尝试使
在我们的存储库中,我们遵循基于 git-flow 的工作流程。我们有一个已完成的发布(安装在生产环境中),因此发布分支已 merge 到主分支中。 B---C---D---E [release
git merge 命令有一个执行快进 merge 的选项,但这不是我想要的,因为如果它不能执行快进 merge ,它会使用普通 merge . 是否有一个 git 命令仅执行快进 merge (从跟
尝试合并 TFS2008 时出现此错误。源分支或目标分支上都没有挂起的更改。 TF14083: The item {0} has a pending merge from the current me
为了更好地理解这些操作,我想知道 github 或 gitlab 到底是如何 merge 这些请求的。当压缩、 rebase 、 merge ......时详细执行哪些 git 命令? 最佳答案 PR
为了更好地理解这些操作,我想知道 github 或 gitlab 到底是如何 merge 这些请求的。当压缩、 rebase 、 merge ......时详细执行哪些 git 命令? 最佳答案 PR
我试图将提交的一部分从默认分支(不是所有文件和其他文件的部分) merge 到一个命名分支。我试过 graft ,但它只需要整个提交,而没有给我选择的机会。这将如何完成? 例子: A---B---C-
我正在进行 merge ,此时我已准备好提交,但我在 TortoiseHg 中的提交对话框显示许多文件已修改,但是当我与 parent 进行比较时,它说所有文件都是二进制相等的。 我没有也从未有过 e
我已经尝试了以下几种变体,但我仍然遇到错误。有什么办法可以解决这个问题。 DB2 10.1(DB2 for z/OS V10) 对于以下 MERGE INTO TRGT t USING SRC s O
我的数据库模型有用户和 MAC 地址。一个用户可以有多个MAC地址,但一个MAC只能属于一个用户。如果某个用户设置了他的 MAC,并且该 MAC 已经链接到另一个用户,则现有关系将被删除,并在新所有者
假设我有一个新功能,所以我创建了一个新分支。这个分支是一个会持续很长时间的副项目,所以我最终将 master merge 回它以使其保持最新状态。这已经发生了 50 次,因为我一直在更新它并消除该功能
过去几个小时我在 Mercurial 中进行了一次巨大的 merge 。 merge 131 个文件后,我的 merge 工具 meld 崩溃,显示 python 回溯。在尝试退出 meld 时,我无
我有一个关于 git merge 的问题。假设我的存储库中有两个分支(本地和远程):master 和 test。当我在测试分支上工作时,主分支被其他人更新了。在终端中,我写: git checkout
我是一名优秀的程序员,十分优秀!