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

Commit536a536

Browse files
committed
add 198 115 problem solution
1 parent9c7025d commit536a536

File tree

16 files changed

+531
-6
lines changed

16 files changed

+531
-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+
typeIntMinHeap []int
4+
5+
func (hIntMinHeap)Len()int {returnlen(h) }
6+
func (hIntMinHeap)Less(i,jint)bool {returnh[i]<h[j] }
7+
func (hIntMinHeap)Swap(i,jint) {h[i],h[j]=h[j],h[i] }
8+
9+
func (h*IntMinHeap)Push(xinterface{}) {
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+
returnx
19+
}
20+
21+
typeIntMaxHeap []int
22+
23+
func (hIntMaxHeap)Len()int {returnlen(h) }
24+
func (hIntMaxHeap)Less(i,jint)bool {returnh[i]>h[j] }
25+
func (hIntMaxHeap)Swap(i,jint) {h[i],h[j]=h[j],h[i] }
26+
27+
func (h*IntMaxHeap)Push(xinterface{}) {
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+
returnx
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+
funcTestIntHeap_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+
forh.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
inputsbool
1314
expectbool
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:=rangecases {
22-
t.Run(c.name,func(t*testing.T) {
22+
fori,c:=rangecases {
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",
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
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package Solution
2+
3+
funcnumDistinct(word1string,word2string)int {
4+
dp:=make([][]int,len(word1)+1)
5+
fori:=0;i<len(word1)+1;i++ {
6+
dp[i]=make([]int,len(word2)+1)
7+
}
8+
fori:=0;i<len(word1)+1;i++ {
9+
dp[i][0]=i
10+
}
11+
fori:=0;i<len(word2)+1;i++ {
12+
dp[0][i]=i
13+
}
14+
fori:=1;i<len(word1)+1;i++ {
15+
forj:=1;j<len(word2)+1;j++ {
16+
ifword1[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+
returndp[len(word1)][len(word2)]
24+
}
25+
26+
funcmin(xint,yint,zint)int {
27+
ifx>y {
28+
x=y
29+
}
30+
ifx>z {
31+
x=z
32+
}
33+
returnx
34+
}
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+
funcTestSolution(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []string
14+
expectint
15+
}{
16+
{"TestCase", []string{"rabbbit","rabbit"},3},
17+
{"TestCase", []string{"babgbag","bag"},5},
18+
}
19+
20+
//开始测试
21+
fori,c:=rangecases {
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+
funcBenchmarkSolution(b*testing.B) {
34+
35+
}
36+
37+
//使用案列
38+
funcExampleSolution() {
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
//开始测试
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
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+
funcfindKthLargest(nums []int,kint)int {
9+
positive:=make([]int,10001)
10+
negative:=make([]int,10001)
11+
fori:=0;i<len(nums);i++ {
12+
ifnums[i]>=0 {
13+
positive[nums[i]]++
14+
}else {
15+
negative[-nums[i]]++
16+
}
17+
}
18+
flag:=k
19+
fori:=10000;i>-1;i-- {
20+
flag-=positive[i]
21+
ifflag<=0 {
22+
returni
23+
}
24+
}
25+
fori:=0;i<10001;i++ {
26+
flag-=negative[i]
27+
ifflag<=0 {
28+
return-i
29+
}
30+
}
31+
return0
32+
}
33+
34+
funcfindKthLargest2(nums []int,kint)int {
35+
h:=make(IntMinHeap,0,len(nums))
36+
heap.Init(&h)
37+
38+
fori:=0;i<len(nums);i++ {
39+
h.Push(nums[i])
40+
heap.Init(&h)
41+
}
42+
forlen(h)>0 {
43+
fmt.Printf("%d ",h.Pop())
44+
}
45+
return0
46+
}

0 commit comments

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