10000 添加 problem 721 · DontFearAlgorithms/LeetCode-Go@91a574c · GitHub
[go: up one dir, main page]
Skip to content

Commit 91a574c

Browse files
halfrosthalfrost
committed
添加 problem 721
1 parent ffd6ee3 commit 91a574c

File tree

2 files changed

+161
-0
lines changed

2 files changed

+161
-0
lines changed

‎Algorithms/0721. Accounts Merge/721. Accounts Merge.go

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package leetcode
2+
3+
import "sort"
4+
5+
// 解法一 并查集优化搜索解法
6+
func accountsMerge(accounts [][]string) (r [][]string) {
7+
uf := UnionFind{}
8+
uf.init(len(accounts))
9+
// emailToID 将所有的 email 邮箱都拆开，拆开与 id(数组下标) 对应
10+
// idToName 将 id(数组下标) 与 name 对应
11+
// idToEmails 将 id(数组下标) 与整理好去重以后的 email 组对应
12+
emailToID, idToName, idToEmails, res := make(map[string]int), make(map[int]string), make(map[int][]string), [][]string{}
13+
for id, acc := range accounts {
14+
idToName[id] = acc[0]
15+
for i := 1; i < len(acc); i++ {
16+
pid, ok := emailToID[acc[i]]
17+
if ok {
18+
uf.union(id, pid)
19+
}
20+
emailToID[acc[i]] = id
21+
}
22+
}
23+
for email, id := range emailToID {
24+
pid := uf.find(id)
25+
idToEmails[pid] = append(idToEmails[pid], email)
26+
}
27+
for id, emails := range idToEmails {
28+
name := idToName[id]
29+
sort.Strings(emails)
30+
res = append(res, append([]string{name}, emails...))
31+
}
32+
return res
33+
}
34+
35+
// 解法二 并查集暴力解法
36+
func accountsMerge1(accounts [][]string) [][]string {
37+
if len(accounts) == 0 {
38+
return [][]string{}
39+
}
40+
uf, res, visited := UnionFind{}, [][]string{}, map[int]bool{}
41+
uf.init(len(accounts))
42+
for i := 0; i < len(accounts); i++ {
43+
for j := i + 1; j < len(accounts); j++ {
44+
if accounts[i][0] == accounts[j][0] {
45+
tmpA, tmpB, flag := accounts[i][1:], accounts[j][1:], false
46+
for j := 0; j < len(tmpA); j++ {
47+
for k := 0; k < len(tmpB); k++ {
48+
if tmpA[j] == tmpB[k] {
49+
flag = true
50+
break
51+
}
52+
}
53+
if flag {
54+
break
55+
}
56+
}
57+
if flag {
58+
uf.union(i, j)
59+
}
60+
}
61+
}
62+
}
63+
for i := 0; i < len(accounts); i++ {
64+
if visited[i] {
65+
continue
66+
}
67+
emails, account, tmpMap := accounts[i][1:], []string{accounts[i][0]}, map[string]string{}
68+
for j := i + 1; j < len(accounts); j++ {
69+
if uf.find(j) == uf.find(i) {
70+
visited[j] = true
71+
for _, v := range accounts[j][1:] {
72+
tmpMap[v] = v
73+
}
74+
}
75+
}
76+
for _, v := range emails {
77+
tmpMap[v] = v
78+
}
79+
emails = []string{}
80+
for key := range tmpMap {
81+
emails = append(emails, key)
82+
}
83+
sort.Strings(emails)
84+
account = append(account, emails...)
85+
res = append(res, account)
86+
}
87+
return res
88+
}

‎Algorithms/0721. Accounts Merge/721. Accounts Merge_test.go

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question721 struct {
9+
para721
10+
ans721
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para721 struct {
16+
w [][]string
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans721 struct {
22+
one [][]string
23+
}
24+
25+
func Test_Problem721(t *testing.T) {
26+
27+
qs := []question721{
28+
29+
question721{
30+
para721{[][]string{[]string{"John", "johnsmith@mail.com", "john00@mail.com"},
31+
[]string{"John", "johnnybravo@mail.com"},
32+
[]string{"John", "johnsmith@mail.com", "john_newyork@mail.com"},
33+
[]string{"Mary", "mary@mail.com"}}},
34+
ans721{[][]string{[]string{"John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"},
35+
[]string{"John", "johnnybravo@mail.com"},
36+
[]string{"Mary", "mary@mail.com"}}},
37+
},
38+
39+
question721{
40+
para721{[][]string{[]string{"Alex", "Alex5@m.co", "Alex4@m.co", "Alex0@m.co"},
41+
[]string{"Ethan", "Ethan3@m.co", "Ethan3@m.co", "Ethan0@m.co"},
42+
[]string{"Kevin", "Kevin4@m.co", "Kevin2@m.co", "Kevin2@m.co"},
43+
[]string{"Gabe", "Gabe0@m.co", "Gabe3@m.co", "Gabe2@m.co"},
44+
[]string{"Gabe", "Gabe3@m.co", "Gabe4@m.co", "Gabe2@m.co"}}},
45+
ans721{[][]string{[]string{"Alex", "Alex0@m.co", "Alex4@m.co", "Alex5@m.co"},
46+
[]string{"Ethan", "Ethan0@m.co", "Ethan3@m.co"},
47+
[]string{"Gabe", "Gabe0@m.co", "Gabe2@m.co", "Gabe3@m.co", "Gabe4@m.co"},
48+
[]string{"Kevin", "Kevin2@m.co", "Kevin4@m.co"}}},
49+
},
50+
51+
question721{
52+
para721{[][]string{[]string{"David", "David0@m.co", "David4@m.co", "David3@m.co"},
53+
[]string{"David", "David5@m.co", "David5@m.co", "David0@m.co"},
54+
[]string{"David", "David1@m.co", "David4@m.co", "David0@m.co"},
55+
[]string{"David", "David0@m.co", "David1@m.co", "Da 9AC1 vid3@m.co"},
56+
[]string{"David", "David4@m.co", "David1@m.co", "David3@m.co"}}},
57+
ans721{[][]string{[]string{"David", "David0@m.co", "David1@m.co", "David3@m.co", "David4@m.co", "David5@m.co"}}},
58+
},
59+
60+
question721{
61+
para721{[][]string{}},
62+
ans721{[][]string{}},
63+
},
64+
}
65+
66+
fmt.Printf("------------------------Leetcode Problem 721------------------------\n")
67+
68+
for _, q := range qs {
69+
_, p := q.ans721, q.para721
70+
fmt.Printf("【input】:%v 【output】:%v\n", p, accountsMerge(p.w))
71+
}
72+
fmt.Printf("\n\n\n")
73+
}

0 commit comments

Comments
 (0)
0