8000 Merge pull request #55 from dumingcode/master · folai/awesome-golang-leetcode@7c69869 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7c69869

Browse files
6boris6boris
authored
Merge pull request 6boris#55 from dumingcode/master
 add 0121 0123 0188 module
2 parents 4a90f37 + 5eae084 commit 7c69869

File tree

13 files changed

+608
-265
lines changed

13 files changed

+608
-265
lines changed

‎src/0121.Best-Time-to-Buy-and-Sell-Stock/README.md

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

‎src/0121.Best-Time-to-Buy-and-Sell-Stock/Solution.go

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+
func maxProfit1(prices []int) int {
16+
maxprofit := 0
17+
for i := 0; i < len(prices); i++ {
18+
for j := i + 1; j < len(prices); j++ {
19+
profit := prices[j] - prices[i]
20+
if profit > maxprofit {
21+
maxprofit = profit
22+
}
23+
}
24+
}
25+
return maxprofit
26+
}
27+
28+
// Greedy
29+
// 扫描一遍
30+
func maxProfit2(prices []int) int {
31+
min := math.MaxInt32
32+
max := 0
33+
34+
for i := 0; i < len(prices); i++ {
35+
if prices[i] < min {
36+
min = prices[i]
37+
} else if max < prices[i]-min {
38+
max = prices[i] - min
39+
}
40+
}
41+
42+
return max
43+
}

‎src/0121.Best-Time-to-Buy-and-Sell-Stock/Solution_test.go

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+
func TestSolution1(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs []int
14+
expect int
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+
for i, c := range cases {
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+
func TestSolution2(t *testing.T) {
33+
// 测试用例
34+
cases := []struct {
35+
name string
36+
inputs []int
37+
expect int
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+
for i, c := range cases {
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+
func BenchmarkSolution(b *testing.B) {
57+
58+
}
59+
60+
// 使用案列
61+
func ExampleSolution() {
62+
63+
}

‎src/0122.Best-Time-To-Buy-And-Sell-Stock-II/README.md

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

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

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
func maxProfit(prices []int) int {
4-
maxProfit := 0
5-
for i := 0; i < len(prices)-1; i++ {
6-
if prices[i] < prices[i+1] {
7-
maxProfit += (prices[i+1] - prices[i])
14+
maxprofix := 0
15+
for i := 1; i < len(prices); i++ {
16+
if prices[i] > prices[i-1] {
17+
maxprofix += prices[i] - prices[i-1]
818
}
919
}
10-
return maxProfit
20+
return maxprofix
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+
func maxProfit2(prices []int) int {
30+
// 初始化DP
31+
n := len(prices)
32+
dp := make([][]int, 0)
33+
for i := 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+
for i := 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+
return profit_max
46+
}
47+
48+
func max(x, y int) int {
49+
if x > y {
50+
return x
51+
}
52+
return y
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-
func TestMaxProfit(t *testing.T) {
9+
func TestSolution(t *testing.T) {
10+
// 测试用例
911
cases := []struct {
1012
name string
1113
inputs []int
1214
expect int
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 := range cases {
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+
for i, c := range cases {
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+
func TestSolution2(t *testing.T) {
34+
// 测试用例
35+
cases := []struct {
36+
name string
37+
inputs []int
38+
expect int
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+
for i, c := range cases {
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+
func BenchmarkSolution(b *testing.B) {
60+
61+
}
62+
63+
// 使用案列
64+
func ExampleSolution() {
2765

2866
}

0 commit comments

Comments
 (0)
0