Skip to content

Commit 62dc111

Browse files
6boris6boris
authored
Merge pull request 6boris#82 from kylesliu/develop
update some stock problem solution
2 parents 6e118ee + 34c5cc6 commit 62dc111

File tree

18 files changed

+513
-61
lines changed

18 files changed

+513
-61
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ LeetCode of algorithms with golang solution(updating:smiley:).
4242

4343
## Community
4444

45+
* [ACWING](https://www.acwing.com/) 一些算法竞赛大佬创建的平台，挺适合入门的。
4546
* [leetbook](https://github.com/hk029/leetbook) 某位大佬写的Leetcode题解，不过已经不更新了
4647
* [LeetCode-in-Go](https://github.com/aQuaYi/LeetCode-in-Go) 某位算法大佬的Golang题解
4748

‎SUMMARY-LIST.md

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
# SUMMARY-LIST
22

33

4-
- Link List
4+
- Linked List
55
- [19. Remove Nth Node From End of List(删除从结尾数第n个结点)](https://leetcode.kyle.link/src/0019.Remove-Nth-Node-From-End-of-List/)
66
- [83. Remove Duplicates from Sorted List(删除链表中的重复元素)](https://leetcode.kyle.link/src/0083.Remove-Duplicates-from-Sorted-List/)
77
- [206. Reverse Linked List(反转链表)](https://leetcode.kyle.link/src/0206.Reverse-Linked-List/)
@@ -16,11 +16,26 @@
1616
- [148. Sort List(链表排序)](https://leetcode.kyle.link/src/0148.Sort-List/)
1717
- [146. LRU Cache (LRU缓存)](https://leetcode.kyle.link/src/0146.LRU-Cache/)
1818

19-
- DFS
19+
- Depth-first Search
2020

2121
- Tree
2222

23-
- DP
23+
- Dynamic Programming
24+
- [53. Maximum Subarray (求最大连续子序列长度)]()
25+
- [300. Longest Increasing Subsequence ()]()
26+
- [72. Edit Distance ()]()
27+
- [121. Best Time to Buy and Sell Stock()]()
28+
- [122. Best Time to Buy and Sell Stock II ()]()
29+
- [123. Best Time to Buy and Sell Stock III ()]()
30+
- [188. Best Time to Buy and Sell Stock IV ()]()
31+
- [309. Best Time to Buy and Sell Stock with Cooldown ()]()
32+
- [198. House Robber ()]()
33+
- [213. House Robber II ()]()
34+
- [312. Burst Balloons ()]()
35+
- [96. Unique Binary Search Trees()]()
36+
- [140. Word Break II()]()
37+
- [10. Regular Expression Matching ()]()
38+
2439

2540
- QUEUE/STACK
2641

‎src/0053.Maximum-Subarray/README.md

Lines changed: 54 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -18,29 +18,75 @@ If you have figured out the O(*n*) solution, try coding another solution using t
1818

1919
**Tags:** Array, Divide and Conquer, Dynamic Programming
2020

21+
## 题意
22+
> 给定一个整数数组 `nums` ，找到`和`最大的连续子序列（至少包含一个数字），返回该子序列的和
2123
2224
## 题解
2325
### 思路1
24-
> 普通DP 找到公式就好了
25-
```$xslt
26-
如果nums[0]>=0，则sum = sum + nums[1]
27-
如果nums[0]<0，则sum = nums[1]，
28-
```
26+
> (动态规划) O(n)
27+
28+
- 1.设 dp(i)dp(i) 表示以第`i`y个数字为结尾的最大连续子序列的`和`是多少。
29+
- 2.初始化 dp(0)=nums[0]dp(0)=nums[0]。
30+
- 3.转移方程 dp(i)=max(dp(i−1)+nums[i],nums[i])dp(i)=max(dp(i−1)+nums[i],nums[i])。可以理解为当前有两种决策，一种是将第`i`个数字和前边的数字拼接起来；另一种是第`i`个数字单独作为一个新的子序列的开始。
31+
- 4.最终答案为ans=max(dp(k)),0≤k<n。
32+
33+
> 时间复杂度
34+
- 状态数为 O(n)，决策数为 O(1)，故总时间复杂度为 O(n)。
2935

3036
```go
3137
func maxSubArray(nums []int) int {
3238
dp, ans := make([]int, len(nums)), nums[0]
3339
dp[0] = nums[0]
3440

3541
for i := 1; i < len(nums); i++ {
36-
dp[i] = Max(nums[i], nums[i]+dp[i-1])
37-
ans = Max(ans, dp[i])
42+
dp[i] = max(nums[i], nums[i]+dp[i-1])
43+
ans = max(dp[i], ans)
3844
}
39-
4045
return ans
4146
}
4247
```
4348
### 思路2
49+
> (分治) O(nlogn)
50+
51+
- 考虑区间 `[l, r]` 内的答案如何计算，令 `mid = (l + r) / 2`，则该区间的答案由三部分取最大值，分别是：
52+
- (1). 区间 `[l, mid]` 内的答案（递归计算）。
53+
- (2). 区间 `[mid + 1, r]` 内的答案（递归计算）。
54+
- (3). 跨越 mid和mid+1 的连续子序列。
55+
- 其中，第(3)部分只需要从 `mid` 开始向 `l` 找连续的最大值，以及从 `mid+1` 开始向 `r` 找最大值即可，在线性时间内可以完成。
56+
- 递归终止条件显然是 l==r ，此时直接返回` nums[l]`。
57+
58+
> 时间复杂度
59+
60+
- 由递归主定理 S(n)=2S(n/2)+O(n)，解出总时间复杂度为 O(nlogn)。
61+
- 或者每一层时间复杂度是 O(n)，总共有 O(logn) 层，故总时间复杂度是 O(nlogn)。
62+
63+
> Code
64+
```go
65+
func maxSubArray(nums []int) int {
66+
return calc(0, len(nums)-1, nums)
67+
}
68+
69+
func calc(l, r int, nums []int) int {
70+
if l == r {
71+
return nums[l]
72+
}
73+
mid := (l + r) >> 1
74+
lmax, lsum, rmax, rsum := nums[mid], 0, nums[mid+1], 0
75+
76+
for i := mid; i >= 1; i-- {
77+
lsum += nums[i]
78+
lmax = max(lmax, lsum)
79+
}
80+
81+
for i := mid + 1; i <= r; i++ {
82+
rsum += nums[i]
83+
rmax = max(rmax, rsum)
84+
}
85+
86+
return max(max(calc(l, mid, nums), calc(mid+1, r, nums)), lmax+rmax)
87+
}
88+
89+
```
4490

4591

4692
## 结语

‎src/0053.Maximum-Subarray/Solution.go

Lines changed: 28 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,16 +5,40 @@ func maxSubArray(nums []int) int {
55
dp[0] = nums[0]
66

77
for i := 1; i < len(nums); i++ {
8-
dp[i] = Max(nums[i], nums[i]+dp[i-1])
9-
ans = Max(ans, dp[i])
8+
dp[i] = max(nums[i], nums[i]+dp[i-1])
9+
ans = max(dp[i], ans)
10+
//fmt.Println(i, ans, dp, nums)
1011
}
11-
1212
return ans
1313
}
1414

15-
func Max(x, y int) int {
15+
func max(x, y int) int {
1616
if x > y {
1717
return x
1818
}
1919
return y
2020
}
21+
22+
func maxSubArray2(nums []int) int {
23+
return calc(0, len(nums)-1, nums)
24+
}
25+
26+
func calc(l, r int, nums []int) int {
27+
if l == r {
28+
return nums[l]
29+
}
30+
mid := (l + r) >> 1
31+
lmax, lsum, rmax, rsum := nums[mid], 0, nums[mid+1], 0
32+
33+
for i := mid; i >= 1; i-- {
34+
lsum += nums[i]
35+
lmax = max(lmax, lsum)
36+
}
37+
38+
for i := mid + 1; i <= r; i++ {
39+
rsum += nums[i]
40+
rmax = max(rmax, rsum)
41+
}
42+
43+
return max(max(calc(l, mid, nums), calc(mid+1, r, nums)), lmax+rmax)
44+
}

‎src/0053.Maximum-Subarray/Solution_test.go

Lines changed: 55 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,61 @@
11
package Solution
22

3-
import "testing"
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
48

59
func TestSolution(t *testing.T) {
6-
t.Run("Test-1", func(t *testing.T) {
7-
got := maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})
8-
want := 6
9-
if got != want {
10-
t.Error("GOT:", got, "WANT:", want)
11-
}
12-
})
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs []int
14+
expect int
15+
}{
16+
{"TestCase", []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, 6},
17+
}
18+
19+
// 开始测试
20+
for i, c := range cases {
21+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
22+
got := maxSubArray(c.inputs)
23+
if !reflect.DeepEqual(got, c.expect) {
24+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
25+
c.expect, got, c.inputs)
26+
}
27+
})
28+
}
29+
}
30+
31+
func TestSolution2(t *testing.T) {
32+
// 测试用例
33+
cases := []struct {
34+
name string
35+
inputs []int
36+
expect int
37+
}{
38+
{"TestCase", []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, 6},
39+
}
40+
41+
// 开始测试
42+
for i, c := range cases {
43+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
44+
got := maxSubArray2(c.inputs)
45+
if !reflect.DeepEqual(got, c.expect) {
46+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
47+
c.expect, got, c.inputs)
48+
}
49+
})
50+
}
51+
}
52+
53+
// 压力测试
54+
func BenchmarkSolution(b *testing.B) {
55+
56+
}
57+
58+
// 使用案列
59+
func ExampleSolution() {
1360

1461
}

‎src/0072.Edit-Distance/README.md

Lines changed: 37 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,62 @@
1-
# [1. Add Sum][title]
1+
# [72. Edit Distance][title]
22

33
## Description
44

5-
Given two binary strings, return their sum (also a binary string).
5+
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
66

7-
The input strings are both **non-empty** and contains only characters `1` or `0`.
7+
You have the following 3 operations permitted on a word:
8+
9+
- Insert a character
10+
- Delete a character
11+
- Replace a character
812

913
**Example 1:**
1014

1115
```
12-
Input: a = "11", b = "1"
13-
Output: "100"
16+
Input: word1 = "horse", word2 = "ros"
17+
Output: 3
18+
Explanation:
19+
horse -> rorse (replace 'h' with 'r')
20+
rorse -> rose (remove 'r')
21+
rose -> ros (remove 'e')
1422
```
1523

1624
**Example 2:**
1725

1826
```
19-
Input: a = "1010", b = "1011"
20-
Output: "10101"
27+
Input: word1 = "intention", word2 = "execution"
28+
Output: 5
29+
Explanation:
30+
intention -> inention (remove 't')
31+
inention -> enention (replace 'i' with 'e')
32+
enention -> exention (replace 'n' with 'x')
33+
exention -> exection (replace 'n' with 'c')
34+
exection -> execution (insert 'u')
2135
```
2236

2337
**Tags:** Math, String
2438

2539
## 题意
26-
>给你两个二进制串，求其和的二进制串。
40+
>给定两个单词 word1 和 word2 ，请问最少需要进行多少次操作可以将 word1 变成 word2 。
2741
2842
## 题解
2943

3044
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
45+
> (动态规划) O(n2)
46+
47+
经典的编辑距离问题。
48+
49+
状态表示：`f[i,j]` 表示将 `word1` 的前 `i` 个字符变成 `word2` 的前 `j` 个字符，最少需要进行多少次操作。
50+
状态转移，一共有四种情况：
51+
52+
- 将`word1[i]` 删除或在`word2[j]`后面添加`word1[i]`，则其操作次数等于`f[i−1,j]+1`；
53+
- 将`word2[j]`删除或在`word1[i]`后面添加`word2[j]`，则其操作次数等于 `f[i,j−1]+1`；
54+
- 如果`word1[i]=word2[j]`，则其操作次数等于 `f[i−1,j−1]`；
55+
- 如果`word1[i]≠word2[j]`，则其操作次数等于 `f[i−1,j−1]+1`；
56+
57+
> 时间复杂度分析：
58+
59+
- 状态数 O(n2)O(n2)，状态转移复杂度是 O(1)O(1)，所以总时间复杂度是 O(n2)O(n2)。
3260

3361
```go
3462

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

Lines changed: 28 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,40 @@ Output: "10101"
2323
**Tags:** Math, String
2424

2525
## 题意
26-
>只允许买卖一次
26+
>假设你有一个数组，其中第i个元素表示第i天某个股票的价格。
27+
如果您只允许完成至多一笔交易（即买入一只股票并卖出一只股票），则设计一种算法以找到最大利润。
28+
必须先购买股票再出售股票。
2729

2830
## 题解
2931

3032
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
33+
> 贪心
3234
33-
```go
35+
- 遍历一次即可得出结果
3436

37+
```go
38+
func maxProfit2(prices []int) int {
39+
profit, low := 0, prices[0]
40+
for i := 0; i < len(prices); i++ {
41+
profit = max(profit, prices[i]-low)
42+
low = min(low, prices[i])
43+
}
44+
return profit
45+
}
46+
47+
func min(x, y int) int {
48+
if x > y {
49+
return y
50+
}
51+
return x
52+
}
53+
54+
func max(x, y int) int {
55+
if x > y {
56+
return x
57+
}
58+
return y
59+
}
3560
```
3661

3762
### 思路2

0 commit comments

Comments
 (0)