8000 添加 problem 128 · DontFearAlgorithms/LeetCode-Go@ffd6ee3 · GitHub
[go: up one dir, main page]
Skip to content

Commit ffd6ee3

Browse files
halfrosthalfrost
committed
添加 problem 128
1 parent 50c9c63 commit ffd6ee3

File tree

2 files changed

+159
-0
lines changed

2 files changed

+159
-0
lines changed
Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package leetcode
2+
3+
// 解法一 map，时间复杂度 O(n)
4+
func longestConsecutive(nums []int) int {
5+
res, numMap := 0, map[int]int{}
6+
for _, num := range nums {
7+
if numMap[num] == 0 {
8+
left, right, sum := 0, 0, 0
9+
if numMap[num-1] > 0 {
10+
left = numMap[num-1]
11+
} else {
12+
left = 0
13+
}
14+
if numMap[num+1] > 0 {
15+
right = numMap[num+1]
16+
} else {
17+
right = 0
18+
}
19+
// sum: length of the sequence n is in
20+
sum = left + right + 1
21+
numMap[num] = sum
22+
// keep track of the max length
23+
res = max(res, sum)
24+
// extend the length to the boundary(s) of the sequence
25+
// will do nothing if n has no neighbors
26+
numMap[num-left] = sum
27+
numMap[num+right] = sum
28+
} else {
29+
continue
30+
}
31+
}
32+
return res
33+
}
34+
35+
// 解法二 并查集
36+
func longestConsecutive1(nums []int) int {
37+
if len(nums) == 0 {
38+
return 0
39+
}
40+
numMap, countMap, lcs, uf := map[int]int{}, map[int]int{}, 0, UnionFind{}
41+
uf.init(len(nums))
42+
for i := 0; i < len(nums); i++ {
43+
countMap[i] = 1
44+
}
45+
for i := 0; i < len(nums); i++ {
46+
if _, ok := numMap[nums[i]]; ok {
47+
continue
48+
}
49+
numMap[nums[i]] = i
50+
if _, ok := numMap[nums[i]+1]; ok {
51+
uf.union(i, numMap[nums[i]+1])
52+
}
53+
if _, ok := numMap[nums[i]-1]; ok {
54+
uf.union(i, numMap[nums[i]-1])
55+
}
56+
}
57+
for key := range countMap {
58+
parent := uf.find(key)
59+
if parent != key {
60+
countMap[parent]++
61+
}
62+
if countMap[parent] > lcs {
63+
lcs = countMap[parent]
64+
}
65+
}
66+
return lcs
67+
}
68+
69+
// 解法三 暴力解法，时间复杂度 O(n^2)
70+
func longestConsecutive2(nums []int) int {
71+
if len(nums) == 0 {
72+
return 0
73+
}
74+
numMap, length, tmp, lcs := map[int]bool{}, 0, 0, 0
75+
for i := 0; i < len(nums); i++ {
76+
numMap[nums[i]] = true
77+
}
78+
for key := range numMap {
79+
if !numMap[key-1] && !numMap[key+1] {
80+
delete(numMap, key)
81+
}
82+
}
83+
if len(numMap) == 0 {
84+
return 1
85+
}
86+
for key := range numMap {
87+
if !numMap[key-1] && numMap[key+1] {
88+
length, tmp = 1, key+1
89+
for numMap[tmp] {
90+
length++
91+
tmp++
92+
}
93+
lcs = max(lcs, length)
94+
}
95+
}
96+
return max(lcs, length)
97+
}

‎Algorithms/0128. Longest Consecutive Sequence/128. Longest Consecutive Sequence_test.go

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question128 struct {
9+
para128
10+
ans128
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para128 struct {
16+
one []int
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans128 struct {
22+
one int
23+
}
24+
25+
func Test_Problem128(t *testing.T) {
26+
27+
qs := []question128{
28+
29+
question128{
30+
para128{[]int{}},
31+
ans128{0},
32+
},
33+
34+
question128{
35+
para128{[]int{0}},
36+
ans128{1},
37+
},
38+
39+
question128{
40+
para128{[]int{9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6}},
41+
ans128{7},
42+
},
43+
44+
question128{
45+
para128{[]int{2147483646, -2147483647, 0, 2, 2147483644, -2147483645, 2147483645}},
46+
ans128{3},
47+
},
48+
49+
question128{
50+
para128{[]int{100, 4, 200, 1, 3, 2}},
51+
ans128{4},
52+
},
53+
}
54+
55+
fmt.Printf("------------------------Leetcode Problem 128------------------------\n")
56+
57+
for _, q := range qs {
58+
_, p := q.ans128, q.para128
59+
fmt.Printf("【input】:%v 【output】:%v\n", p, longestConsecutive(p.one))
60+
}
61+
fmt.Printf("\n\n\n")
62+
}

0 commit comments

Comments
 (0)
0