Skip to content

Commit 654bfec

Browse files
6boris6boris
authored
Merge pull request 6boris#74 from kylesliu/develop
Develop
2 parents 4bd022f + 417be87 commit 654bfec

File tree

15 files changed

+674
-3
lines changed

15 files changed

+674
-3
lines changed

‎README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,11 @@ LeetCode of algorithms with golang solution(updating:smiley:).
3535

3636
[![Stargazers over time](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode.svg)](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode)
3737

38+
## Community
39+
40+
* [leetbook](https://github.com/hk029/leetbook) 某位大佬写的Leetcode题解，不过已经不更新了
41+
* [LeetCode-in-Go](https://github.com/aQuaYi/LeetCode-in-Go) 某位算法大佬的Golang题解
42+
3843
## Contributors
3944

4045
Thanks goes to these wonderful people ([emoji key](https://github.com/all-contributors/all-contributors#emoji-key)):

‎src/0045.Jump-Game-II/Solution.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package Solution
22

33
import (
4+
"fmt"
45
"math"
56
)
67

@@ -54,6 +55,34 @@ func jump2(nums []int) int {
5455
return res
5556
}
5657

58+
/**
59+
1
60+
61+
*/
62+
func jump3(nums []int) int {
63+
// 如果数组小于2，则说明不用跳跃返回0
64+
if len(nums) < 2 {
65+
return 0
66+
}
67+
// 当前可达到的最远位置，遍历过程中可达到最远位置，最小步数
68+
current_max_index, pre_max_max_index, jump_min := nums[0], nums[0], 1
69+
70+
for i := 1; i < len(nums); i++ {
71+
// 如果无法向前移动才进行跳跃
72+
if i > current_max_index {
73+
jump_min++
74+
// 更新当前可以到达的最远位置
75+
current_max_index = pre_max_max_index
76+
}
77+
if pre_max_max_index < nums[i]+i {
78+
// 跟新最远位置
79+
pre_max_max_index = nums[i] + i
80+
}
81+
fmt.Println("i:", i, current_max_index, pre_max_max_index, jump_min)
82+
}
83+
return jump_min
84+
}
85+
5786
func Min(x, y int) int {
5887
if x > y {
5988
return y

‎src/0045.Jump-Game-II/Solution_test.go

Lines changed: 29 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -36,9 +36,10 @@ func TestSolution2(t *testing.T) {
3636
inputs []int
3737
expect int
3838
}{
39-
{"TestCacse 1", []int{2, 3, 1, 1, 4}, 2},
40-
{"TestCacse 1", []int{2}, 0},
41-
{"TestCacse 1", []int{10, 3, 4}, 1},
39+
{"TestCase 1", []int{2, 3, 1, 1, 4}, 2},
40+
{"TestCase 1", []int{2}, 0},
41+
{"TestCase 1", []int{10, 3, 4}, 1},
42+
{"TestCase 4", []int{4, 1, 1, 3, 1, 1, 1}, 2},
4243
}
4344

4445
// 开始测试
@@ -53,6 +54,31 @@ func TestSolution2(t *testing.T) {
5354
}
5455
}
5556

57+
func TestSolution3(t *testing.T) {
58+
// 测试用例
59+
cases := []struct {
60+
name string
61+
inputs []int
62+
expect int
63+
}{
64+
{"TestCase 1", []int{2, 3, 1, 1, 4}, 2},
65+
{"TestCase 2", []int{2}, 0},
66+
{"TestCase 3", []int{10, 3, 4}, 1},
67+
{"TestCase 4", []int{4, 1, 1, 3, 1, 1, 1}, 2},
68+
}
69+
70+
// 开始测试
71+
for _, c := range cases {
72+
t.Run(c.name, func(t *testing.T) {
73+
ret := jump3(c.inputs)
74+
if !reflect.DeepEqual(ret, c.expect) {
75+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
76+
c.expect, ret, c.inputs)
77+
}
78+
})
79+
}
80+
}
81+
5682
// 压力测试
5783
func BenchmarkSolution(b *testing.B) {
5884

‎src/0128.Longest-Consecutive-Sequence/Solution.go

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package Soluation
2+
3+
var p map[int]int
4+
var rank map[int]int
5+
6+
func longestConsecutive(nums []int) int {
7+
l := len(nums)
8+
if l < 1 {
9+
return 0
10+
}
11+
p, rank = initialize(nums)
12+
hash := make(map[int]int)
13+
for _, v := range nums {
14+
hash[v] = 1
15+
if _, ok := hash[v-1]; ok {
16+
union(v, v-1)
17+
}
18+
if _, ok := hash[v+1]; ok {
19+
union(v, v+1)
20+
}
21+
}
22+
23+
ans := 0
24+
for _, v := range rank {
25+
if v > ans {
26+
ans = v
27+
}
28+
}
29+
return ans
30+
}
31+
32+
func initialize(nums []int) (map[int]int, map[int]int) {
33+
p, rank = make(map[int]int), make(map[int]int)
34+
for _, v := range nums {
35+
p[v] = v
36+
rank[v] = 1
37+
}
38+
return p, rank
39+
}
40+
41+
func find(x int) int {
42+
if p[x] != x {
43+
p[x] = find(p[x])
44+
}
45+
return p[x]
46+
}
47+
48+
func union(x, y int) {
49+
x = find(x)
50+
y = find(y)
51+
if x != y {
52+
if rank[x] >= rank[y] {
53+
rank[x] += rank[y]
54+
p[y] = x
55+
} else {
56+
rank[y] += rank[x]
57+
p[x] = y
58+
}
59+
}
60+
}

‎src/0128.Longest-Consecutive-Sequence/Solution_test.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package Soluation
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func TestSolution(t *testing.T) {
9+
// 测试用例
10+
cases := []struct {
11+
name string
12+
inputs []int
13+
expect int
14+
}{
15+
{
16+
"TestCases 1",
17+
[]int{100, 4, 200, 1, 3, 2},
18+
4,
19+
},
20+
}
21+
22+
// 开始测试
23+
for _, c := range cases {
24+
t.Run(c.name, func(t *testing.T) {
25+
got := longestConsecutive(c.inputs)
26+
if !reflect.DeepEqual(got, c.expect) {
27+
t.Fatalf("expected: %v, but got: %v, with inputs: %v", c.expect, got, c.inputs)
28+
}
29+
})
30+
}
31+
}
32+
33+
// 压力测试
34+
func BenchmarkSolution(b *testing.B) {
35+
36+
}
37+
38+
// 使用案列
39+
func ExampleSolution() {
40+
41+
}

‎src/0128.Longest-Consecutive-Sequence/readme.md

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
# [128. Longest Consecutive Sequence][title]
2+
3+
## Description
4+
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
5+
6+
Your algorithm should run in O(n) complexity.
7+
8+
**Example:**
9+
10+
```
11+
Input: [100, 4, 200, 1, 3, 2]
12+
Output: 4
13+
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
14+
```
15+
16+
## 题意
17+
> 给定一个未排序的整数数组，找出最长连续序列的长度。
18+
19+
20+
## 题解
21+
22+
### 思路1
23+
> 使用并查集，将相邻的元素合并，找到元素最多的集合。
24+
25+
```go
26+
var p map[int]int
27+
var rank map[int]int
28+
29+
func longestConsecutive(nums []int) int {
30+
l := len(nums)
31+
if l < 1 {
32+
return 0
33+
}
34+
p, rank = initialize(nums)
35+
hash := make(map[int]int)
36+
for _, v := range nums {
37+
hash[v] = 1
38+
if _, ok := hash[v-1]; ok {
39+
union(v, v-1)
40+
}
41+
if _, ok := hash[v+1]; ok {
42+
union(v, v+1)
43+
}
44+
}
45+
46+
ans := 0
47+
for _, v := range rank {
48+
if v > ans {
49+
ans = v
50+
}
51+
}
52+
fmt.Println(rank)
53+
return ans
54+
}
55+
56+
func initialize(nums []int) (map[int]int, map[int]int) {
57+
p, rank = make(map[int]int), make(map[int]int)
58+
for _, v := range nums {
59+
p[v] = v
60+
rank[v] = 1
61+
}
62+
return p, rank
63+
}
64+
65+
func find(x int) int {
66+
if p[x] != x {
67+
p[x] = find(p[x])
68+
}
69+
return p[x]
70+
}
71+
72+
func union(x, y int) {
73+
x = find(x)
74+
y = find(y)
75+
if x != y {
76+
if rank[x] >= rank[y] {
77+
rank[x] += rank[y]
78+
p[y] = x
79+
} else {
80+
rank[y] += rank[x]
81+
p[x] = y
82+
}
83+
}
84+
}
85+
```
86+
87+
### 思路2
88+
> 思路2
89+
```go
90+
91+
```
92+
93+
## 结语
94+
95+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
96+
97+
[title]: https://leetcode.com/problems/longest-consecutive-sequence/description/
98+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/README.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# [452. Minimum Number of Arrows to Burst Balloons][title]
2+
3+
## Description
4+
5+
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
6+
7+
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
8+
**Example 1:**
9+
10+
```
11+
Input:
12+
[[10,16], [2,8], [1,6], [7,12]]
13+
14+
Output:
15+
2
16+
Explanation:
17+
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
18+
19+
```
20+
21+
**Example 2:**
22+
23+
```
24+
Input: a = "1010", b = "1011"
25+
Output: "10101"
26+
```
27+
28+
**Tags:** Math, String
29+
30+
## 题意
31+
> 求2数之和
32+
33+
## 题解
34+
35+
### 思路1
36+
> 。。。。
37+
38+
```go
39+
40+
```
41+
42+
### 思路2
43+
> 思路2
44+
```go
45+
46+
```
47+
48+
## 结语
49+
50+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
51+
52+
[title]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
53+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/Solution.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package Solution
2+
3+
import (
4+
"sort"
5+
)
6+
7+
func findMinArrowShots(points [][]int) int {
8+
if len(points) == 0 {
9+
return 0
10+
}
11+
sort.Sort(ByLen(points))
12+
13+
res := 0
14+
end := -1<<31 - 1
15+
for _, interval := range points {
16+
if interval[0] > end {
17+
res += 1
18+
end = interval[1]
19+
}
20+
}
21+
return res
22+
}
23+
24+
type ByLen [][]int
25+
26+
func (a ByLen) Len() int { return len(a) }
27+
func (a ByLen) Less(i, j int) bool { return a[i][1] < a[j][1] }
28+
func (a ByLen) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

0 commit comments

Comments
 (0)