Skip to content

Commit 830c662

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0714. Best Time to Buy and Sell
Stock with Transaction Fee
1 parent 5892695 commit 830c662

File tree

14 files changed

+178
-39
lines changed

14 files changed

+178
-39
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -175,6 +175,7 @@
175175
- [买卖股票的最佳时机](./solution/0100-0199/0121.Best%20Time%20to%20Buy%20and%20Sell%20Stock/README.md)
176176
- [买卖股票的最佳时机 II](./solution/0100-0199/0122.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II/README.md)
177177
- [最佳买卖股票时机含冷冻期](./solution/0300-0399/0309.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown/README.md)
178+
- [买卖股票的最佳时机含手续费](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README.md)
178179
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
179180
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
180181
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,6 +169,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
169169
- [Best Time to Buy and Sell Stock](./solution/0100-0199/0121.Best%20Time%20to%20Buy%20and%20Sell%20Stock/README_EN.md)
170170
- [Best Time to Buy and Sell Stock II](./solution/0100-0199/0122.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II/README_EN.md)
171171
- [Best Time to Buy and Sell Stock with Cooldown](./solution/0300-0399/0309.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown/README_EN.md)
172+
- [Best Time to Buy and Sell Stock with Transaction Fee](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README_EN.md)
172173
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
173174
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
174175
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/README.md

Lines changed: 5 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -50,14 +50,12 @@ class Solution:
5050
def maxProfit(self, prices: List[int]) -> int:
5151
# 买入，卖出，继续空仓
5252
f1, f2, f3 = -prices[0], 0, 0
53-
res = f2
5453
for price in prices[1:]:
5554
pf1, pf2, pf3 = f1, f2, f3
5655
f1 = max(pf1, pf3 - price)
5756
f2 = max(pf2, pf1 + price)
5857
f3 = max(pf3, pf2)
59-
res = max(res, f2)
60-
return res
58+
return f2
6159
```
6260

6361
### **Java**
@@ -69,15 +67,13 @@ class Solution {
6967
public int maxProfit(int[] prices) {
7068
// 买入，卖出，继续空仓
7169
int f1 = -prices[0], f2 = 0, f3 = 0;
72-
int res = f2;
7370
for (int i = 1; i < prices.length; ++i) {
7471
int pf1 = f1, pf2 = f2, pf3 = f3;
7572
f1 = Math.max(pf1, pf3 - prices[i]);
7673
f2 = Math.max(pf2, pf1 + prices[i]);
7774
f3 = Math.max(pf3, pf2);
78-
res = Math.max(res, f2);
7975
}
80-
return res;
76+
return f2;
8177
}
8278
}
8379
```
@@ -89,15 +85,13 @@ class Solution {
8985
public:
9086
int maxProfit(vector<int>& prices) {
9187
int f1 = -prices[0], f2 = 0, f3 = 0;
92-
int res = f2;
9388
for (int i = 1; i < prices.size(); ++i) {
9489
int pf1 = f1, pf2 = f2, pf3 = f3;
9590
f1 = max(pf1, pf3 - prices[i]);
9691
f2 = max(pf2, pf1 + prices[i]);
9792
f3 = max(pf3, pf2);
98-
res = max(res, f2);
9993
}
100-
return res;
94+
return f2;
10195
}
10296
};
10397
```
@@ -106,15 +100,14 @@ public:
106100
107101
```go
108102
func maxProfit(prices []int) int {
109-
f1, f2, f3, res := -prices[0], 0, 0, 0
103+
f1, f2, f3 := -prices[0], 0, 0
110104
for i := 1; i < len(prices); i++ {
111105
pf1, pf2, pf3 := f1, f2, f3
112106
f1 = max(pf1, pf3-prices[i])
113107
f2 = max(pf2, pf1+prices[i])
114108
f3 = max(pf3, pf2)
115-
res = max(res, f2)
116109
}
117-
return res
110+
return f2
118111
}
119112
120113
func max(a, b int) int {

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/README_EN.md

Lines changed: 5 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -49,14 +49,12 @@
4949
class Solution:
5050
def maxProfit(self, prices: List[int]) -> int:
5151
f1, f2, f3 = -prices[0], 0, 0
52-
res = f2
5352
for price in prices[1:]:
5453
pf1, pf2, pf3 = f1, f2, f3
5554
f1 = max(pf1, pf3 - price)
5655
f2 = max(pf2, pf1 + price)
5756
f3 = max(pf3, pf2)
58-
res = max(res, f2)
59-
return res
57+
return f2
6058
```
6159

6260
### **Java**
@@ -65,15 +63,13 @@ class Solution:
6563
class Solution {
6664
public int maxProfit(int[] prices) {
6765
int f1 = -prices[0], f2 = 0, f3 = 0;
68-
int res = f2;
6966
for (int i = 1; i < prices.length; ++i) {
7067
int pf1 = f1, pf2 = f2, pf3 = f3;
7168
f1 = Math.max(pf1, pf3 - prices[i]);
7269
f2 = Math.max(pf2, pf1 + prices[i]);
7370
f3 = Math.max(pf3, pf2);
74-
res = Math.max(res, f2);
7571
}
76-
return res;
72+
return f2;
7773
}
7874
}
7975
```
@@ -85,15 +81,13 @@ class Solution {
8581
public:
8682
int maxProfit(vector<int>& prices) {
8783
int f1 = -prices[0], f2 = 0, f3 = 0;
88-
int res = f2;
8984
for (int i = 1; i < prices.size(); ++i) {
9085
int pf1 = f1, pf2 = f2, pf3 = f3;
9186
f1 = max(pf1, pf3 - prices[i]);
9287
f2 = max(pf2, pf1 + prices[i]);
9388
f3 = max(pf3, pf2);
94-
res = max(res, f2);
9589
}
96-
return res;
90+
return f2;
9791
}
9892
};
9993
```
@@ -102,15 +96,14 @@ public:
10296
10397
```go
10498
func maxProfit(prices []int) int {
105-
f1, f2, f3, res := -prices[0], 0, 0, 0
99+
f1, f2, f3 := -prices[0], 0, 0
106100
for i := 1; i < len(prices); i++ {
107101
pf1, pf2, pf3 := f1, f2, f3
108102
f1 = max(pf1, pf3-prices[i])
109103
f2 = max(pf2, pf1+prices[i])
110104
f3 = max(pf3, pf2)
111-
res = max(res, f2)
112105
}
113-
return res
106+
return f2
114107
}
115108
116109
func max(a, b int) int {

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/Solution.cpp

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,14 +2,12 @@ class Solution {
22
public:
33
int maxProfit(vector<int>& prices) {
44
int f1 = -prices[0], f2 = 0, f3 = 0;
5-
int res = f2;
65
for (int i = 1; i < prices.size(); ++i) {
76
int pf1 = f1, pf2 = f2, pf3 = f3;
87
f1 = max(pf1, pf3 - prices[i]);
98
f2 = max(pf2, pf1 + prices[i]);
109
f3 = max(pf3, pf2);
11-
res = max(res, f2);
1210
}
13-
return res;
11+
return f2;
1412
}
1513
};

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/Solution.go

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,12 @@
11
func maxProfit(prices []int) int {
2-
f1, f2, f3, res := -prices[0], 0, 0, 0
2+
f1, f2, f3 := -prices[0], 0, 0
33
for i := 1; i < len(prices); i++ {
44
pf1, pf2, pf3 := f1, f2, f3
55
f1 = max(pf1, pf3-prices[i])
66
f2 = max(pf2, pf1+prices[i])
77
f3 = max(pf3, pf2)
8-
res = max(res, f2)
98
}
10-
return res
9+
return f2
1110
}
1211

1312
func max(a, b int) int {

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/Solution.java

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,12 @@
11
class Solution {
22
public int maxProfit(int[] prices) {
33
int f1 = -prices[0], f2 = 0, f3 = 0;
4-
int res = f2;
54
for (int i = 1; i < prices.length; ++i) {
65
int pf1 = f1, pf2 = f2, pf3 = f3;
76
f1 = Math.max(pf1, pf3 - prices[i]);
87
f2 = Math.max(pf2, pf1 + prices[i]);
98
f3 = Math.max(pf3, pf2);
10-
res = Math.max(res, f2);
119
}
12-
return res;
10+
return f2;
1311
}
1412
}

‎solution/0300-0399/0309.Best Time to Buy and Sell Stock with Cooldown/Solution.py

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,9 @@
11
class Solution:
22
def maxProfit(self, prices: List[int]) -> int:
33
f1, f2, f3 = -prices[0], 0, 0
4-
res = f2
54
for price in prices[1:]:
65
pf1, pf2, pf3 = f1, f2, f3
76
f1 = max(pf1, pf3 - price)
87
f2 = max(pf2, pf1 + price)
98
f3 = max(pf3, pf2)
10-
res = max(res, f2)
11-
return res
9+
return f2

‎solution/0700-0799/0714.Best Time to Buy and Sell Stock with Transaction Fee/README.md

Lines changed: 66 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,27 +33,91 @@
3333
<li><code>0 &lt;= fee &lt; 50000</code>.</li>
3434
</ul>
3535

36-
3736
## 解法
3837

3938
<!-- 这里可写通用的实现逻辑 -->
4039

40+
动态规划法。
41+
42+
设 f1 表示当天持有股票的最大利润，f2 表示当天没持有股票的最大利润。
43+
44+
初始第 1 天结束时，`f1 = -prices[0]`，`f2 = 0`。
45+
46+
从第 2 天开始，当天结束时：
47+
48+
- 若持有，则可能是前一天持有，今天继续持有；也可能前一天没持有，今天买入，`f1 = max(f1, f2 - price)`。
49+
- 若没持有，则可能是前一天持有，今天卖出；也可能是前一天没没有，今天继续没持有，`f2 = max(f2, f1 + price - fee)`。
50+
51+
最后返回 f2 即可。
52+
4153
<!-- tabs:start -->
4254

4355
### **Python3**
4456

4557
<!-- 这里可写当前语言的特殊实现逻辑 -->
4658

4759
```python
48-
60+
class Solution:
61+
def maxProfit(self, prices: List[int], fee: int) -> int:
62+
# 持有，没持有
63+
f1, f2 = -prices[0], 0
64+
for price in prices[1:]:
65+
f1 = max(f1, f2 - price)
66+
f2 = max(f2, f1 + price - fee)
67+
return f2
4968
```
5069

5170
### **Java**
5271

5372
<!-- 这里可写当前语言的特殊实现逻辑 -->
5473

5574
```java
75+
class Solution {
76+
public int maxProfit(int[] prices, int fee) {
77+
int f1 = -prices[0], f2 = 0;
78+
for (int i = 1; i < prices.length; ++i) {
79+
f1 = Math.max(f1, f2 - prices[i]);
80+
f2 = Math.max(f2, f1 + prices[i] - fee);
81+
}
82+
return f2;
83+
}
84+
}
85+
```
86+
87+
### **C++**
88+
89+
```cpp
90+
class Solution {
91+
public:
92+
int maxProfit(vector<int>& prices, int fee) {
93+
int f1 = -prices[0], f2 = 0;
94+
for (int i = 1; i < prices.size(); ++i) {
95+
f1 = max(f1, f2 - prices[i]);
96+
f2 = max(f2, f1 + prices[i] - fee);
97+
}
98+
return f2;
99+
}
100+
};
101+
```
56102
103+
### **Go**
104+
105+
```go
106+
func maxProfit(prices []int, fee int) int {
107+
f1, f2 := -prices[0], 0
108+
for i := 1; i < len(prices); i++ {
109+
f1 = max(f1, f2-prices[i])
110+
f2 = max(f2, f1+prices[i]-fee)
111+
}
112+
return f2
113+
}
114+
115+
func max(a, b int) int {
116+
if a > b {
117+
return a
118+
}
119+
return b
120+
}
57121
```
58122

59123
### **...**

‎solution/0700-0799/0714.Best Time to Buy and Sell Stock with Transaction Fee/README_EN.md

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,13 +48,64 @@ The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
4848
### **Python3**
4949

5050
```python
51-
51+
class Solution:
52+
def maxProfit(self, prices: List[int], fee: int) -> int:
53+
f1, f2 = -prices[0], 0
54+
for price in prices[1:]:
55+
f1 = max(f1, f2 - price)
56+
f2 = max(f2, f1 + price - fee)
57+
return f2
5258
```
5359

5460
### **Java**
5561

5662
```java
63+
class Solution {
64+
public int maxProfit(int[] prices, int fee) {
65+
int f1 = -prices[0], f2 = 0;
66+
for (int i = 1; i < prices.length; ++i) {
67+
f1 = Math.max(f1, f2 - prices[i]);
68+
f2 = Math.max(f2, f1 + prices[i] - fee);
69+
}
70+
return f2;
71+
}
72+
}
73+
```
74+
75+
### **C++**
76+
77+
```cpp
78+
class Solution {
79+
public:
80+
int maxProfit(vector<int>& prices, int fee) {
81+
int f1 = -prices[0], f2 = 0;
82+
for (int i = 1; i < prices.size(); ++i) {
83+
f1 = max(f1, f2 - prices[i]);
84+
f2 = max(f2, f1 + prices[i] - fee);
85+
}
86+
return f2;
87+
}
88+
};
89+
```
5790
91+
### **Go**
92+
93+
```go
94+
func maxProfit(prices []int, fee int) int {
95+
f1, f2 := -prices[0], 0
96+
for i := 1; i < len(prices); i++ {
97+
f1 = max(f1, f2-prices[i])
98+
f2 = max(f2, f1+prices[i]-fee)
99+
}
100+
return f2
101+
}
102+
103+
func max(a, b int) int {
104+
if a > b {
105+
return a
106+
}
107+
return b
108+
}
58109
```
59110

60111
### **...**

‎solution/0700-0799/0714.Best Time to Buy and Sell Stock with Transaction Fee/Solution.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution {
2+
public:
3+
int maxProfit(vector<int>& prices, int fee) {
4+
int f1 = -prices[0], f2 = 0;
5+
for (int i = 1; i < prices.size(); ++i) {
6+
f1 = max(f1, f2 - prices[i]);
7+
f2 = max(f2, f1 + prices[i] - fee);
8+
}
9+
return f2;
10+
}
11+
};

0 commit comments

Comments
 (0)