8000 Merge pull request #62 from kylesliu/develop · folai/awesome-golang-leetcode@be9a2a1 · GitHub
[go: up one dir, main page]
Skip to content

Commit be9a2a1

Browse files
6boris6boris
authored
Merge pull request 6boris#62 from kylesliu/develop
Add some solution
2 parents 7fa2135 + 5daa7d8 commit be9a2a1

File tree

22 files changed

+666
-6
lines changed

22 files changed

+666
-6
lines changed

‎.gitignore

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,4 +17,5 @@
1717
coverage.txt
1818
node_modules/
1919
/gitbook
20-
.env.yml
20+
.env.yml
21+
/python

‎lib/heap.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package Solution
2+
3+
type IntMinHeap []int
4+
5+
func (h IntMinHeap) Len() int { return len(h) }
6+
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
7+
func (h IntMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
8+
9+
func (h *IntMinHeap) Push(x interface{}) {
10+
*h = append(*h, x.(int))
11+
}
12+
13+
func (h *IntMinHeap) Pop() interface{} {
14+
old := *h
15+
n := len(old)
16+
x := old[n-1]
17+
*h = old[0 : n-1]
18+
return x
19+
}
20+
21+
type IntMaxHeap []int
22+
23+
func (h IntMaxHeap) Len() int { return len(h) }
24+
func (h IntMaxHeap) Less(i, j int) bool { return h[i] > h[j] }
25+
func (h IntMaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
26+
27+
func (h *IntMaxHeap) Push(x interface{}) {
28+
*h = append(*h, x.(int))
29+
}
30+
31+
func (h *IntMaxHeap) Pop() interface{} {
32+
old := *h
33+
n := len(old)
34+
x := old[n-1]
35+
*h = old[0 : n-1]
36+
return x
37+
}

‎lib/heap_test.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+
"container/heap"
5+
"fmt"
6+
"testing"
7+
)
8+
9+
func TestIntHeap_Less(t *testing.T) {
10+
h := &IntMaxHeap{}
11+
heap.Init(h)
12+
heap.Push(h, 7)
13+
heap.Push(h, 3)
14+
heap.Push(h, 2)
15+
heap.Push(h, 1)
16+
heap.Push(h, 5)
17+
heap.Push(h, 5)
18+
heap.Push(h, 6)
19+
heap.Push(h, 7)
20+
fmt.Printf("minimum: %d\n", (*h))
21+
22+
23+
for h.Len() > 0 {
24+
fmt.Printf("%d ", heap.Pop(h))
25+
}
26+
//fmt.Printf("minimum: %d\n", (*h))
27+
//fmt.Printf("minimum: %d\n", (*h)[2])
28+
}

‎src/0000.Demo/Solution_test.go

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ package Solution
22

33
import (
44
"reflect"
5+
"strconv"
56
"testing"
67
)
78

@@ -12,14 +13,14 @@ func TestSolution(t *testing.T) {
1213
inputs bool
1314
expect bool
1415
}{
15-
{"TestCase 1", true, true},
16-
{"TestCase 2", true, true},
17-
{"TestCase 3", false, false},
16+
{"TestCase", true, true},
17+
{"TestCase", true, true},
18+
{"TestCase", false, false},
1819
}
1920

2021
// 开始测试
21-
for _, c := range cases {
22-
t.Run(c.name, func(t *testing.T) {
22+
for 10000 i, c := range cases {
23+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
2324
got := Solution(c.inputs)
2425
if !reflect.DeepEqual(got, c.expect) {
2526
t.Fatalf("expected: %v, but got: %v, with inputs: %v",

‎src/0115.Distinct-Subsequences/README.md

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# [115. Distinct Subsequences][title]
2+
3+
## Description
4+
5+
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
6+
7+
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
8+
**Example 1:**
9+
10+
```
11+
Input: S = "rabbbit", T = "rabbit"
12+
Output: 3
13+
Explanation:
14+
15+
As shown below, there are 3 ways you can generate "rabbit" from S.
16+
(The caret symbol ^ means the chosen letters)
17+
18+
rabbbit
19+
^^^^ ^^
20+
rabbbit
21+
^^ ^^^^
22+
rabbbit
23+
^^^ ^^^
24+
```
25+
26+
**Example 2:**
27+
28+
```
29+
Output: 5
30+
Explanation:
31+
32+
As shown below, there are 5 ways you can generate "bag" from S.
33+
(The caret symbol ^ means the chosen letters)
34+
35+
babgbag
36+
^^ ^
37+
babgbag
38+
^^ ^
39+
babgbag
40+
^ ^^
41+
babgbag
42+
^ ^^
43+
babgbag
44+
^^^
45+
```
46+
47+
**Tags:** Math, String
48+
49+
## 题意
50+
> 求2数之和
51+
52+
## 题解
53+
54+
### 思路1
55+
> 。。。。
56+
57+
```go
58+
59+
```
60+
61+
### 思路2
62+
> 思路2
63+
```go
64+
65+
```
66+
67+
## 结语
68+
69+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
70+
71+
[title]: https://leetcode.com/problems/two-sum/description/
72+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0115.Distinct-Subsequences/Solution.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package Solution
2+
3+
func numDistinct(word1 string, word2 string) int {
4+
dp := make([][]int, len(word1)+1)
5+
for i := 0; i < len(word1)+1; i++ {
6+
dp[i] = make([]int, len(< F438 span class=pl-s1>word2)+1)
7+
}
8+
for i := 0; i < len(word1)+1; i++ {
9+
dp[i][0] = i
10+
}
11+
for i := 0; i < len(word2)+1; i++ {
12+
dp[0][i] = i
13+
}
14+
for i := 1; i < len(word1)+1; i++ {
15+
for j := 1; j < len(word2)+1; j++ {
16+
if word1[i-1] == word2[j-1] {
17+
dp[i][j] = dp[i-1][j-1]
18+
} else {
19+
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
20+
}
21+
}
22+
}
23+
return dp[len(word1)][len(word2)]
24+
}
25+
26+
func min(x int, y int, z int) int {
27+
if x > y {
28+
x = y
29+
}
30+
if x > z {
31+
x = z
32+
}
33+
return x
34+
}

‎src/0115.Distinct-Subsequences/Solution_test.go

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

‎src/0198.House-Robber/README.md

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,20 @@ Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (m
4141
.
4242
.
4343
f(n) = max(nums[n] + f(n-2), f(n-1))
44+
45+
[5,2,6,3,7,1]
46+
47+
dp[1] = 5
48+
dp[2] = 5
49+
dp[3] = max(dp[1] + nums[3], dp[dp[2]])
50+
= max(5 + 6, 5) = 11
51+
dp[4] = max(dp[2]+dp[4], dp[3])
52+
= max(5 + 3, 11) =1
53+
dp[5] = max(dp[3] + nums[5], dp[4])
54+
= max(11 + 1, 11) = 12
55+
dp[6] = max(dp[4] + nums[6], dp[5])
56+
= max(11 + 7, 12) = 18
57+
4458
```
4559
4660

‎src/0198.House-Robber/Solution_test.go

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ func TestSolution(t *testing.T) {
1414
}{
1515
{"TestCacse 1", []int{1, 2, 3, 1}, 4},
1616
{"TestCacse 1", []int{2, 7, 9, 3, 1}, 12},
17+
{"TestCacse 1", []int{5, 2, 6, 7, 3, 1}, 14},
1718
}
1819

1920
// 开始测试

‎src/0215.Kth-Largest-Element-in-an-Array/README.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
# [215. Kth Largest Element in an Array][title]
2+
3+
## Description
4+
5+
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
6+
**Example 1:**
7+
8+
```
9+
Input: [3,2,1,5,6,4] and k = 2
10+
Output: 5
11+
```
12+
13+
**Example 2:**
14+
15+
```
16+
Input: [3,2,3,1,2,4,5,5,6] and k = 4
17+
Output: 4
18+
```
19+
20+
**Tags:** Math, String
21+
22+
## 题意
23+
> 求2数之和
24+
25+
## 题解
26+
27+
### 思路1
28+
> 。。。。
29+
30+
```go
31+
32+
```
33+
34+
### 思路2
35+
> 思路2
36+
```go
37+
38+
```
39+
40+
## 结语
41+
42+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
43+
44+
[title]: https://leetcode.com/problems/kth-largest-element-in-an-array/
45+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0215.Kth-Largest-Element-in-an-Array/Solution.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Solution
2+
3+
import (
4+
"container/heap"
5+
"fmt"
6+
)
7+
8+
func findKthLargest(nums []int, k int) int {
9+
positive := make([]int, 10001)
10+
negative := make([]int, 10001)
11+
for i := 0; i < len(nums); i++ {
12+
if nums[i] >= 0 {
13+
positive[nums[i]]++
14+
} else {
15+
negative[-nums[i]]++
16+
}
17+
}
18+
flag := k
19+
for i := 10000; i > -1; i-- {
20+
flag -= positive[i]
21+
if flag <= 0 {
22+
return i
23+
}
24+
}
25+
for i := 0; i < 10001; i++ {
26+
flag -= negative[i]
27+
if flag <= 0 {
28+
return -i
29+
}
30+
}
31+
return 0
32+
}
33+
34+
func findKthLargest2(nums []int, k int) int {
35+
h := make(IntMinHeap, 0, len(nums))
36+
heap.Init(&h)
37+
38+
for i := 0; i < len(nums); i++ {
39+
h.Push(nums[i])
40+
heap.Init(&h)
41+
}
42+
for len(h) > 0 {
43+
fmt.Printf("%d ", h.Pop())
44+
}
45+
return 0
46+
}

0 commit comments

Comments
 (0)
0