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

Commit62dc111

Browse files
authored
Merge pull request6boris#82 from kylesliu/develop
update some stock problem solution
2 parents6e118ee +34c5cc6 commit62dc111

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
funcmaxSubArray(nums []int)int {
3238
dp,ans:=make([]int,len(nums)), nums[0]
3339
dp[0] = nums[0]
3440

3541
fori:=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+
funcmaxSubArray(nums []int)int {
66+
returncalc(0,len(nums)-1, nums)
67+
}
68+
69+
funccalc(l,rint,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+
fori:= mid; i >=1; i-- {
77+
lsum += nums[i]
78+
lmax =max(lmax, lsum)
79+
}
80+
81+
fori:= mid +1; i <= r; i++ {
82+
rsum += nums[i]
83+
rmax =max(rmax, rsum)
84+
}
85+
86+
returnmax(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
fori:=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
returnans
1313
}
1414

15-
funcMax(x,yint)int {
15+
funcmax(x,yint)int {
1616
ifx>y {
1717
returnx
1818
}
1919
returny
2020
}
21+
22+
funcmaxSubArray2(nums []int)int {
23+
returncalc(0,len(nums)-1,nums)
24+
}
25+
26+
funccalc(l,rint,nums []int)int {
27+
ifl==r {
28+
returnnums[l]
29+
}
30+
mid:= (l+r)>>1
31+
lmax,lsum,rmax,rsum:=nums[mid],0,nums[mid+1],0
32+
33+
fori:=mid;i>=1;i-- {
34+
lsum+=nums[i]
35+
lmax=max(lmax,lsum)
36+
}
37+
38+
fori:=mid+1;i<=r;i++ {
39+
rsum+=nums[i]
40+
rmax=max(rmax,rsum)
41+
}
42+
43+
returnmax(max(calc(l,mid,nums),calc(mid+1,r,nums)),lmax+rmax)
44+
}
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
funcTestSolution(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-
ifgot!=want {
10-
t.Error("GOT:",got,"WANT:",want)
11-
}
12-
})
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
expectint
15+
}{
16+
{"TestCase", []int{-2,1,-3,4,-1,2,1,-5,4},6},
17+
}
18+
19+
//开始测试
20+
fori,c:=rangecases {
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+
funcTestSolution2(t*testing.T) {
32+
//测试用例
33+
cases:= []struct {
34+
namestring
35+
inputs []int
36+
expectint
37+
}{
38+
{"TestCase", []int{-2,1,-3,4,-1,2,1,-5,4},6},
39+
}
40+
41+
//开始测试
42+
fori,c:=rangecases {
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+
funcBenchmarkSolution(b*testing.B) {
55+
56+
}
57+
58+
//使用案列
59+
funcExampleSolution() {
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 twobinary strings, return their sum (also a binary string).
5+
Given twowords 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+
funcmaxProfit2(prices []int)int {
39+
profit,low:=0, prices[0]
40+
fori:=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+
funcmin(x,yint)int {
48+
if x > y {
49+
return y
50+
}
51+
return x
52+
}
53+
54+
funcmax(x,yint)int {
55+
if x > y {
56+
return x
57+
}
58+
return y
59+
}
3560
```
3661

3762
###思路2

0 commit comments

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