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

Commit5eae084

Browse files
committed
add 0121 0123 0188 module
1 parent4a90f37 commit5eae084

File tree

13 files changed

+608
-265
lines changed

13 files changed

+608
-265
lines changed
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#[121. Best Time to Buy and Sell Stock][title]
2+
3+
##Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both**non-empty** and contains only characters`1` or`0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
##题意
26+
>只允许买卖一次
27+
28+
##题解
29+
30+
###思路1
31+
>按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
32+
33+
```go
34+
35+
```
36+
37+
###思路2
38+
>思路2
39+
```go
40+
41+
```
42+
43+
##结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]:https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
48+
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package Solution
2+
3+
import"math"
4+
5+
/**
6+
持有一股
7+
买卖一次
8+
*/
9+
10+
/**
11+
Brute Force
12+
时间复杂度O(n^2)
13+
空间复杂度O(1)
14+
*/
15+
funcmaxProfit1(prices []int)int {
16+
maxprofit:=0
17+
fori:=0;i<len(prices);i++ {
18+
forj:=i+1;j<len(prices);j++ {
19+
profit:=prices[j]-prices[i]
20+
ifprofit>maxprofit {
21+
maxprofit=profit
22+
}
23+
}
24+
}
25+
returnmaxprofit
26+
}
27+
28+
//Greedy
29+
//扫描一遍
30+
funcmaxProfit2(prices []int)int {
31+
min:=math.MaxInt32
32+
max:=0
33+
34+
fori:=0;i<len(prices);i++ {
35+
ifprices[i]<min {
36+
min=prices[i]
37+
}elseifmax<prices[i]-min {
38+
max=prices[i]-min
39+
}
40+
}
41+
42+
returnmax
43+
}
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution1(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
expectint
15+
}{
16+
{"TestCase", []int{7,1,5,3,6,4},5},
17+
{"TestCase", []int{1,2,3,4,5},4},
18+
{"TestCase", []int{7,6,4,3,1},0},
19+
}
20+
21+
//开始测试
22+
fori,c:=rangecases {
23+
t.Run(c.name+strconv.Itoa(i),func(t*testing.T) {
24+
got:=maxProfit1(c.inputs)
25+
if!reflect.DeepEqual(got,c.expect) {
26+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27+
c.expect,got,c.inputs)
28+
}
29+
})
30+
}
31+
}
32+
funcTestSolution2(t*testing.T) {
33+
//测试用例
34+
cases:= []struct {
35+
namestring
36+
inputs []int
37+
expectint
38+
}{
39+
{"TestCase", []int{7,1,5,3,6,4},5},
40+
{"TestCase", []int{1,2,3,4,5},4},
41+
{"TestCase", []int{7,6,4,3,1},0},
42+
}
43+
44+
//开始测试
45+
fori,c:=rangecases {
46+
t.Run(c.name+strconv.Itoa(i),func(t*testing.T) {
47+
got:=maxProfit2(c.inputs)
48+
if!reflect.DeepEqual(got,c.expect) {
49+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
50+
c.expect,got,c.inputs)
51+
}
52+
})
53+
}
54+
}
55+
//压力测试
56+
funcBenchmarkSolution(b*testing.B) {
57+
58+
}
59+
60+
//使用案列
61+
funcExampleSolution() {
62+
63+
}
Lines changed: 48 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,48 @@
1-
#[122. Best Time to Buy and Sell Stock II][title]
2-
3-
##Description
4-
5-
Say you have an array for which the ith element is the price of a given stock on day i.
6-
7-
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
8-
9-
10-
**Example 1:**
11-
12-
```
13-
Input: [7,1,5,3,6,4]
14-
Output: 7
15-
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
16-
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
17-
```
18-
19-
**Example 2:**
20-
21-
```
22-
Input: [1,2,3,4,5]
23-
Output: 4
24-
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
25-
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
26-
engaging multiple transactions at the same time. You must sell before buying again.
27-
```
28-
29-
**Example 3:**
30-
31-
```
32-
Input: [7,6,4,3,1]
33-
Output: 0
34-
Explanation: In this case, no transaction is done, i.e. max profit = 0.
35-
```
36-
37-
38-
[title]:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
1+
#[122. Best Time to Buy and Sell Stock II][title]
2+
3+
##Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both**non-empty** and contains only characters`1` or`0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
##题意
26+
>给你两个二进制串，求其和的二进制串。
27+
28+
##题解
29+
30+
###思路1
31+
>按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
32+
33+
```go
34+
35+
```
36+
37+
###思路2
38+
>思路2
39+
```go
40+
41+
```
42+
43+
##结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
48+
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 49 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,55 @@
11
package Solution
22

3+
import (
4+
"math"
5+
)
6+
7+
/**
8+
持有一股
9+
买卖无数次
10+
*/
11+
12+
//Greedy
313
funcmaxProfit(prices []int)int {
4-
maxProfit:=0
5-
fori:=0;i<len(prices)-1;i++ {
6-
ifprices[i]<prices[i+1] {
7-
maxProfit+=(prices[i+1]-prices[i])
14+
maxprofix:=0
15+
fori:=1;i<len(prices);i++ {
16+
ifprices[i]>prices[i-1] {
17+
maxprofix+=prices[i]-prices[i-1]
818
}
919
}
10-
returnmaxProfit
20+
returnmaxprofix
1121
}
22+
23+
//DP
24+
//dp[i][0] means the maximum profit after sunset of day i with no stock in hand
25+
//dp[i][1] means the maximum profit after sunset of day i with stock in hand
26+
//dp[i][0] = max(dp[i-1][1]+price[i],dp[i-1][0]) --> Sell on day i or do nothing
27+
//dp[i][1] = max(dp[i-1][0])-price[i],dp[i-1][1]) --> Buy on day i or do nothing
28+
//dp[0][0]=0,dp[0][1]=INT_MIN
29+
funcmaxProfit2(prices []int)int {
30+
// 初始化DP
31+
n:=len(prices)
32+
dp:=make([][]int,0)
33+
fori:=0;i<=n;i++ {
34+
dp=append(dp,make([]int,2))
35+
}
36+
dp[0][0],dp[0][1]=0,math.MinInt32
37+
profit_max:=0
38+
fori:=0;i<n;i++ {
39+
dp[i+1][0]=max(dp[i][1]+prices[i],dp[i][0])
40+
dp[i+1][1]=max(dp[i][0]-prices[i],dp[i][1])
41+
42+
profit_max=max(profit_max,dp[i+1][0])
43+
profit_max=max(profit_max,dp[i+1][1])
44+
}
45+
returnprofit_max
46+
}
47+
48+
funcmax(x,yint)int {
49+
ifx>y {
50+
returnx
51+
}
52+
returny
53+
}
54+
55+
//DFS

‎src/0122.Best-Time-To-Buy-And-Sell-Stock-II/Solution_test.go

Lines changed: 47 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2,27 +2,65 @@ package Solution
22

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

8-
funcTestMaxProfit(t*testing.T) {
9+
funcTestSolution(t*testing.T) {
10+
//测试用例
911
cases:= []struct {
1012
namestring
1113
inputs []int
1214
expectint
1315
}{
14-
{"TestCase 1", []int{7,1,5,3,6,4},7},
15-
{"TestCase 2", []int{1,2,3,4,5},4},
16-
{"TestCase 3", []int{7,6,4,3,1},0},
16+
{"TestCase", []int{7,1,5,3,6,4},7},
17+
{"TestCase", []int{1,2,3,4,5},4},
18+
{"TestCase", []int{7,6,4,3,1},0},
1719
}
1820

19-
for_,testcase:=rangecases {
20-
t.Run(testcase.name,func(t*testing.T) {
21-
got:=maxProfit(testcase.inputs)
22-
if!reflect.DeepEqual(got,testcase.expect) {
23-
t.Fatalf("expected: %v, but got %v, with inputs : %v",testcase.expect,got,testcase.inputs)
21+
//开始测试
22+
fori,c:=rangecases {
23+
t.Run(c.name+strconv.Itoa(i),func(t*testing.T) {
24+
got:=maxProfit(c.inputs)
25+
if!reflect.DeepEqual(got,c.expect) {
26+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27+
c.expect,got,c.inputs)
2428
}
2529
})
2630
}
31+
}
32+
33+
funcTestSolution2(t*testing.T) {
34+
//测试用例
35+
cases:= []struct {
36+
namestring
37+
inputs []int
38+
expectint
39+
}{
40+
{"TestCase", []int{7,1,5,3,6,4},7},
41+
{"TestCase", []int{1,2,3,4,5},4},
42+
{"TestCase", []int{7,6,4,3,1},0},
43+
}
44+
45+
//开始测试
46+
fori,c:=rangecases {
47+
t.Run(c.name+strconv.Itoa(i),func(t*testing.T) {
48+
got:=maxProfit2(c.inputs)
49+
if!reflect.DeepEqual(got,c.expect) {
50+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
51+
c.expect,got,c.inputs)
52+
}
53+
})
54+
}
55+
}
56+
57+
58+
//压力测试
59+
funcBenchmarkSolution(b*testing.B) {
60+
61+
}
62+
63+
//使用案列
64+
funcExampleSolution() {
2765

2866
}

0 commit comments

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