Skip to content

Commit 5be4309

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0721
No.0721.Accounts Merge
1 parent 6baeda7 commit 5be4309

File tree

7 files changed

+214
-58
lines changed

7 files changed

+214
-58
lines changed

‎solution/0200-0299/0200.Number of Islands/README.md

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -53,15 +53,19 @@
5353

5454
<!-- 这里可写通用的实现逻辑 -->
5555

56-
BFS、DFS、并查集均可。
56+
Flood fill，或者并查集。
57+
58+
Flood fill 算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。
59+
60+
最简单的实现方法是采用 DFS 的递归方法，也可以采用 BFS 的迭代来实现。
5761

5862
<!-- tabs:start -->
5963

6064
### **Python3**
6165

6266
<!-- 这里可写当前语言的特殊实现逻辑 -->
6367

64-
DFS：
68+
DFS - Flood Fill 算法：
6569

6670
```python
6771
class Solution:
@@ -135,7 +139,7 @@ class Solution:
135139

136140
<!-- 这里可写当前语言的特殊实现逻辑 -->
137141

138-
DFS：
142+
DFS - Flood Fill 算法：
139143

140144
```java
141145
class Solution {
@@ -173,7 +177,7 @@ class Solution {
173177
}
174178
```
175179

176-
BFS：
180+
BFS - Flood Fill 算法：
177181

178182
```java
179183
class Solution {
@@ -266,7 +270,7 @@ class Solution {
266270

267271
### **TypeScript**
268272

269-
DFS：
273+
DFS - Flood Fill 算法：
270274

271275
```ts
272276
function numIslands(grid: string[][]): number {
@@ -296,7 +300,7 @@ function numIslands(grid: string[][]): number {
296300
}
297301
```
298302

299-
BFS：
303+
BFS - Flood Fill 算法：
300304

301305
```ts
302306
function numIslands(grid: string[][]): number {
@@ -375,7 +379,7 @@ function numIslands(grid: string[][]): number {
375379

376380
### **C++**
377381

378-
DFS：
382+
DFS - Flood Fill 算法：
379383

380384
```cpp
381385
class Solution {
@@ -411,7 +415,7 @@ public:
411415
};
412416
```
413417

414-
BFS：
418+
BFS - Flood Fill 算法：
415419

416420
```cpp
417421
class Solution {
@@ -502,7 +506,7 @@ public:
502506
503507
### **Go**
504508
505-
DFS：
509+
DFS - Flood Fill 算法：
506510
507511
```go
508512
func numIslands(grid [][]byte) int {
@@ -531,7 +535,7 @@ func numIslands(grid [][]byte) int {
531535
}
532536
```
533537

534-
BFS：
538+
BFS - Flood Fill 算法：
535539

536540
```go
537541
func numIslands(grid [][]byte) int {

‎solution/0200-0299/0200.Number of Islands/README_EN.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,10 @@
4343

4444
## Solutions
4545

46+
DFS, BFS or Union find.
47+
48+
> Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color.
49+
4650
<!-- tabs:start -->
4751

4852
### **Python3**

‎solution/0700-0799/0721.Accounts Merge/README.md

Lines changed: 67 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -114,34 +114,32 @@ d[find(a)] = distance
114114
```python
115115
class Solution:
116116
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
117-
n = len(accounts)
118-
p = list(range(n))
119-
120117
def find(x):
121118
if p[x] != x:
122119
p[x] = find(p[x])
123120
return p[x]
124121

122+
n = len(accounts)
123+
p = list(range(n))
125124
email_id = {}
126-
for i in range(n):
127-
name = accounts[i][0]
128-
for email in accounts[i][1:]:
125+
for i, account in enumerate(accounts):
126+
name = account[0]
127+
for email in account[1:]:
129128
if email in email_id:
130129
p[find(i)] = find(email_id[email])
131130
else:
132131
email_id[email] = i
133-
134132
mp = defaultdict(set)
135-
for i in range(n):
136-
pa = find(i)
137-
for email in accounts[i][1:]:
138-
mp[pa].add(email)
139-
res = []
133+
for i, account in enumerate(accounts):
134+
for email in account[1:]:
135+
mp[find(i)].add(email)
136+
137+
ans = []
140138
for i, emails in mp.items():
141139
t = [accounts[i][0]]
142140
t.extend(sorted(emails))
143-
res.append(t)
144-
return res
141+
ans.append(t)
142+
return ans
145143
```
146144

147145
### **Java**
@@ -173,11 +171,10 @@ class Solution {
173171
}
174172
Map<Integer, Set<String>> mp = new HashMap<>();
175173
for (int i = 0; i < n; ++i) {
176-
int pa = find(i);
177174
List<String> account = accounts.get(i);
178175
for (int j = 1; j < account.size(); ++j) {
179176
String email = account.get(j);
180-
mp.computeIfAbsent(pa, k -> new HashSet<>()).add(email);
177+
mp.computeIfAbsent(find(i), k -> new HashSet<>()).add(email);
181178
}
182179
}
183180
List<List<String>> res = new ArrayList<>();
@@ -200,6 +197,60 @@ class Solution {
200197
}
201198
```
202199

200+
### **C++**
201+
202+
```cpp
203+
class Solution {
204+
public:
205+
vector<int> p;
206+
207+
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
208+
int n = accounts.size();
209+
p.resize(n);
210+
for (int i = 0; i < n; ++i) p[i] = i;
211+
unordered_map<string, int> emailId;
212+
for (int i = 0; i < n; ++i)
213+
{
214+
auto account = accounts[i];
215+
auto name = account[0];
216+
for (int j = 1; j < account.size(); ++j)
217+
{
218+
string email = account[j];
219+
if (emailId.count(email)) p[find(i)] = find(emailId[email]);
220+
else emailId[email] = i;
221+
}
222+
}
223+
unordered_map<int, unordered_set<string>> mp;
224+
for (int i = 0; i < n; ++i)
225+
{
226+
auto account = accounts[i];
227+
for (int j = 1; j < account.size(); ++j)
228+
{
229+
string email = account[j];
230+
mp[find(i)].insert(email);
231+
}
232+
}
233+
vector<vector<string>> ans;
234+
for (auto& [i, emails] : mp)
235+
{
236+
vector<string> t;
237+
t.push_back(accounts[i][0]);
238+
for (string email : emails) t.push_back(email);
239+
sort(t.begin() + 1, t.end());
240+
ans.push_back(t);
241+
}
242+
return ans;
243+
}
244+
245+
int find(int x) {
246+
if (p[x] != x) {
247+
p[x] = find(p[x]);
248+
}
249+
return p[x];
250+
}
251+
};
252+
```
253+
203254
### **...**
204255

205256
```

‎solution/0700-0799/0721.Accounts Merge/README_EN.md

Lines changed: 67 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -50,34 +50,32 @@ We could return these lists in any order, for example the answer [[&#39;Mary&#39
5050
```python
5151
class Solution:
5252
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
53-
n = len(accounts)
54-
p = list(range(n))
55-
5653
def find(x):
5754
if p[x] != x:
5855
p[x] = find(p[x])
5956
return p[x]
6057

58+
n = len(accounts)
59+
p = list(range(n))
6160
email_id = {}
62-
for i in range(n):
63-
name = accounts[i][0]
64-
for email in accounts[i][1:]:
61+
for i, account in enumerate(accounts):
62+
name = account[0]
63+
for email in account[1:]:
6564
if email in email_id:
6665
p[find(i)] = find(email_id[email])
6766
else:
6867
email_id[email] = i
69-
7068
mp = defaultdict(set)
71-
for i in range(n):
72-
pa = find(i)
73-
for email in accounts[i][1:]:
74-
mp[pa].add(email)
75-
res = []
69+
for i, account in enumerate(accounts):
70+
for email in account[1:]:
71+
mp[find(i)].add(email)
72+
73+
ans = []
7674
for i, emails in mp.items():
7775
t = [accounts[i][0]]
7876
t.extend(sorted(emails))
79-
res.append(t)
80-
return res
77+
ans.append(t)
78+
return ans
8179
```
8280

8381
### **Java**
@@ -107,11 +105,10 @@ class Solution {
107105
}
108106
Map<Integer, Set<String>> mp = new HashMap<>();
109107
for (int i = 0; i < n; ++i) {
110-
int pa = find(i);
111108
List<String> account = accounts.get(i);
112109
for (int j = 1; j < account.size(); ++j) {
113110
String email = account.get(j);
114-
mp.computeIfAbsent(pa, k -> new HashSet<>()).add(email);
111+
mp.computeIfAbsent(find(i), k -> new HashSet<>()).add(email);
115112
}
116113
}
117114
List<List<String>> res = new ArrayList<>();
@@ -134,6 +131,60 @@ class Solution {
134131
}
135132
```
136133

134+
### **C++**
135+
136+
```cpp
137+
class Solution {
138+
public:
139+
vector<int> p;
140+
141+
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
142+
int n = accounts.size();
143+
p.resize(n);
144+
for (int i = 0; i < n; ++i) p[i] = i;
145+
unordered_map<string, int> emailId;
146+
for (int i = 0; i < n; ++i)
147+
{
148+
auto account = accounts[i];
149+
auto name = account[0];
150+
for (int j = 1; j < account.size(); ++j)
151+
{
152+
string email = account[j];
153+
if (emailId.count(email)) p[find(i)] = find(emailId[email]);
154+
else emailId[email] = i;
155+
}
156+
}
157+
unordered_map<int, unordered_set<string>> mp;
158+
for (int i = 0; i < n; ++i)
159+
{
160+
auto account = accounts[i];
161+
for (int j = 1; j < account.size(); ++j)
162+
{
163+
string email = account[j];
164+
mp[find(i)].insert(email);
165+
}
166+
}
167+
vector<vector<string>> ans;
168+
for (auto& [i, emails] : mp)
169+
{
170+
vector<string> t;
171+
t.push_back(accounts[i][0]);
172+
for (string email : emails) t.push_back(email);
173+
sort(t.begin() + 1, t.end());
174+
ans.push_back(t);
175+
}
176+
return ans;
177+
}
178+
179+
int find(int x) {
180+
if (p[x] != x) {
181+
p[x] = find(p[x]);
182+
}
183+
return p[x];
184+
}
185+
};
186+
```
187+
137188
### **...**
138189

139190
```

‎solution/0700-0799/0721.Accounts Merge/Solutioin.java

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,11 +22,10 @@ public List<List<String>> accountsMerge(List<List<String>> accounts) {
2222
}
2323
Map<Integer, Set<String>> mp = new HashMap<>();
2424
for (int i = 0; i < n; ++i) {
25-
int pa = find(i);
2625
List<String> account = accounts.get(i);
2726
for (int j = 1; j < account.size(); ++j) {
2827
String email = account.get(j);
29-
mp.computeIfAbsent(pa, k -> new HashSet<>()).add(email);
28+
mp.computeIfAbsent(find(i), k -> new HashSet<>()).add(email);
3029
}
3130
}
3231
List<List<String>> res = new ArrayList<>();

0 commit comments

Comments
 (0)