Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit654bfec

Browse files
authored
Merge pull request6boris#74 from kylesliu/develop
Develop
2 parents4bd022f +417be87 commit654bfec

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
returnres
5556
}
5657

58+
/**
59+
1
60+
61+
*/
62+
funcjump3(nums []int)int {
63+
//如果数组小于2，则说明不用跳跃返回0
64+
iflen(nums)<2 {
65+
return0
66+
}
67+
//当前可达到的最远位置，遍历过程中可达到最远位置，最小步数
68+
current_max_index,pre_max_max_index,jump_min:=nums[0],nums[0],1
69+
70+
fori:=1;i<len(nums);i++ {
71+
//如果无法向前移动才进行跳跃
72+
ifi>current_max_index {
73+
jump_min++
74+
//更新当前可以到达的最远位置
75+
current_max_index=pre_max_max_index
76+
}
77+
ifpre_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+
returnjump_min
84+
}
85+
5786
funcMin(x,yint)int {
5887
ifx>y {
5988
returny

‎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
expectint
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+
funcTestSolution3(t*testing.T) {
58+
//测试用例
59+
cases:= []struct {
60+
namestring
61+
inputs []int
62+
expectint
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:=rangecases {
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
funcBenchmarkSolution(b*testing.B) {
5884

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package Soluation
2+
3+
varpmap[int]int
4+
varrankmap[int]int
5+
6+
funclongestConsecutive(nums []int)int {
7+
l:=len(nums)
8+
ifl<1 {
9+
return0
10+
}
11+
p,rank=initialize(nums)
12+
hash:=make(map[int]int)
13+
for_,v:=rangenums {
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:=rangerank {
25+
ifv>ans {
26+
ans=v
27+
}
28+
}
29+
returnans
30+
}
31+
32+
funcinitialize(nums []int) (map[int]int,map[int]int) {
33+
p,rank=make(map[int]int),make(map[int]int)
34+
for_,v:=rangenums {
35+
p[v]=v
36+
rank[v]=1
37+
}
38+
returnp,rank
39+
}
40+
41+
funcfind(xint)int {
42+
ifp[x]!=x {
43+
p[x]=find(p[x])
44+
}
45+
returnp[x]
46+
}
47+
48+
funcunion(x,yint) {
49+
x=find(x)
50+
y=find(y)
51+
ifx!=y {
52+
ifrank[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+
}
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+
funcTestSolution(t*testing.T) {
9+
// 测试用例
10+
cases:= []struct {
11+
namestring
12+
inputs[]int
13+
expectint
14+
}{
15+
{
16+
"TestCases 1",
17+
[]int{100,4,200,1,3,2},
18+
4,
19+
},
20+
}
21+
22+
// 开始测试
23+
for_,c:=rangecases {
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+
funcBenchmarkSolution(b*testing.B) {
35+
36+
}
37+
38+
//使用案列
39+
funcExampleSolution() {
40+
41+
}
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+
varpmap[int]int
27+
varrankmap[int]int
28+
29+
funclongestConsecutive(nums []int)int {
30+
l:=len(nums)
31+
if l <1 {
32+
return0
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+
funcinitialize(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+
funcfind(xint)int {
66+
if p[x] != x {
67+
p[x] =find(p[x])
68+
}
69+
return p[x]
70+
}
71+
72+
funcunion(x,yint) {
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
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
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+
funcfindMinArrowShots(points [][]int)int {
8+
iflen(points)==0 {
9+
return0
10+
}
11+
sort.Sort(ByLen(points))
12+
13+
res:=0
14+
end:=-1<<31-1
15+
for_,interval:=rangepoints {
16+
ifinterval[0]>end {
17+
res+=1
18+
end=interval[1]
19+
}
20+
}
21+
returnres
22+
}
23+
24+
typeByLen [][]int
25+
26+
func (aByLen)Len()int {returnlen(a) }
27+
func (aByLen)Less(i,jint)bool {returna[i][1]<a[j][1] }
28+
func (aByLen)Swap(i,jint) {a[i],a[j]=a[j],a[i] }

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp