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

Commitedd9ed4

Browse files
Update
1 parentca15f4f commitedd9ed4

7 files changed

+448
-19
lines changed
50.8 KB
Loading
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
2+
#思路
3+
4+
##暴力
5+
6+
这道题目最直观的想法，就是暴力，找优间距了。
7+
8+
```
9+
class Solution {
10+
public:
11+
int maxProfit(vector<int>& prices) {
12+
int result = 0;
13+
for (int i = 0; i < prices.size(); i++) {
14+
for (int j = i + 1; j < prices.size(); j++){
15+
result = max(result, prices[j] - prices[i]);
16+
}
17+
}
18+
return result;
19+
}
20+
};
21+
```
22+
23+
* 时间复杂度：O(n^2)
24+
* 空间复杂度：O(1)
25+
26+
当然该方法超时了。
27+
28+
29+
##贪心
30+
31+
因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
32+
33+
C++代码如下：
34+
35+
```C++
36+
classSolution {
37+
public:
38+
int maxProfit(vector<int>& prices) {
39+
int low = INT_MAX;
40+
int result = 0;
41+
for (int i = 0; i < prices.size(); i++) {
42+
low = min(low, prices[i]); // 取最左最小价格
43+
result = max(result, prices[i] - low); // 直接取最大区间利润
44+
}
45+
return result;
46+
}
47+
};
48+
```
49+
50+
## 动态规划
51+
52+
dp[i][0] 表示第i天持有股票所得现金
53+
dp[i][1] 表示第i天不持有股票所得现金
54+
55+
```
56+
class Solution {
57+
public:
58+
int maxProfit(vector<int>& prices) {
59+
int n = prices.size();
60+
if (n == 0) return 0;
61+
vector<vector<int>> dp(n, vector<int>(2, 0));
62+
dp[0][0] -= prices[0]; // 持股票
63+
for (int i = 1; i < n; i++) {
64+
dp[i][0] = max(dp[i - 1][0], -prices[i]); // 买入
65+
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]); // 卖出
66+
}
67+
return dp[n - 1][1];
68+
}
69+
};
70+
```
71+
Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
#思路
2+
3+
这道题目相对 121.买卖股票的最佳时机 和 122.买卖股票的最佳时机II 难了不少。
4+
5+
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
6+
7+
接来下我用动态规划五部曲详细分析一下：
8+
9+
###确定dp数组以及下标的含义
10+
11+
一天一共就有五个状态，
12+
0. 没有操作
13+
1. 第一次买入
14+
2. 第一次卖出
15+
3. 第二次买入
16+
4. 第二次卖出
17+
18+
dp[i][j]中 i表示第i天，j为[0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
19+
20+
###确定递推公式
21+
22+
dp[i][0] = dp[i - 1][0];
23+
24+
需要注意：dp[i][1]，**表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区**。
25+
26+
达到dp[i][1]状态，有两个具体操作：
27+
28+
* 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
29+
* 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][0]
30+
31+
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][0]呢？
32+
33+
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][0]);
34+
35+
同理dp[i][2]也有两个操作：
36+
37+
* 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][i] + prices[i]
38+
* 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
39+
40+
所以dp[i][2] = max(dp[i - 1][i] + prices[i], dp[i][2])
41+
42+
同理可推出剩下状态部分：
43+
44+
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
45+
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
46+
47+
48+
###dp数组如何初始化
49+
50+
51+
第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
52+
53+
第0天做第一次买入的操作，dp[0][1] = -prices[0];
54+
55+
第0天做第一次卖出的操作，这个初始值应该是多少呢？
56+
57+
首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
58+
59+
从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
60+
61+
所以dp[0][2] = 0;
62+
63+
第0天第二次买入操作，初始值应该是多少呢？
64+
65+
不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少。
66+
67+
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
68+
69+
同理第二次卖出初始化dp[0][4] = 0;
70+
71+
###确定遍历顺序
72+
73+
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
74+
75+
76+
###举例推导dp数组
77+
78+
以输入[1,2,3,4,5]为例
79+
80+
81+
![123.买卖股票的最佳时机III](https://img-blog.csdnimg.cn/20201228181724295.png)
82+
83+
红色为最终求解。
84+
85+
因为利润最大一定是卖出的状态，所以最终最大利润是max(dp[4][2], dp[4][4]);
86+
87+
###C++代码
88+
89+
以上五步都分析完了，不难写出如下代码：
90+
91+
```
92+
class Solution {
93+
public:
94+
int maxProfit(vector<int>& prices) {
95+
if (prices.size() == 0) return 0;
96+
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
97+
dp[0][0] = 0;
98+
dp[0][1] = -prices[0];
99+
dp[0][3] = -prices[0];
100+
for (int i = 1; i < prices.size(); i++) {
101+
dp[i][0] = dp[i - 1][0];
102+
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
103+
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
104+
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
105+
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
106+
}
107+
return max(dp[prices.size() - 1][2], dp[prices.size() - 1][4]);
108+
109+
}
110+
};
111+
```
112+
113+
* 时间复杂度：O(n)
114+
* 空间复杂度：O(n * 5)
115+
116+
117+
118+
当然，大家在网上看到的题解还有一种优化空间写法，如下：
119+
120+
```
121+
class Solution {
122+
public:
123+
int maxProfit(vector<int>& prices) {
124+
if (prices.size() == 0) return 0;
125+
vector<int> dp(5, 0);
126+
dp[0] = 0;
127+
dp[1] = -prices[0];
128+
dp[3] = -prices[0];
129+
for (int i = 1; i < prices.size(); i++) {
130+
dp[1] = max(dp[1], dp[0] - prices[i]);
131+
dp[2] = max(dp[2], dp[1] + prices[i]);
132+
dp[3] = max(dp[3], dp[2] - prices[i]);
133+
dp[4] = max(dp[4], dp[3] + prices[i]);
134+
}
135+
return max(dp[2], dp[4]);
136+
137+
}
138+
};
139+
```
140+
但这种写法，dp[2] 利用的是当天的dp[1]，我还没有理解为什么这种写法也可以通过，网上的题解也没有做出解释，可能这就是神代码吧，欢迎大家来讨论一波！
Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
2+
#思路
3+
4+
这道题目可以说是123.买卖股票的最佳时机III的进阶版， 这里要求至多有k次交易。
5+
6+
在123.买卖股票的最佳时机III中，我是定义了一个二维dp数组，本题其实依然可以用一个二维dp数组。
7+
8+
动规五部曲，分析如下：
9+
10+
###确定dp数组以及下标的含义
11+
12+
使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
13+
14+
j的状态表示为：
15+
16+
* 0 表示不操作
17+
* 1 第一次买入
18+
* 2 第一次卖出
19+
* 3 第一次买入
20+
* 4 第一次卖出
21+
.....
22+
23+
大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。
24+
25+
题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。
26+
27+
所以二维dp数组的C++定义为：
28+
29+
```
30+
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
31+
```
32+
33+
###确定递推公式
34+
35+
在123.买卖股票的最佳时机III中
36+
37+
需要注意：dp[i][1]，**表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区**。
38+
39+
达到dp[i][1]状态，有两个具体操作：
40+
41+
* 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
42+
* 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][0]
43+
44+
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][0]呢？
45+
46+
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][0]);
47+
48+
同理dp[i][2]也有两个操作：
49+
50+
* 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][i] + prices[i]
51+
* 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
52+
53+
所以dp[i][2] = max(dp[i - 1][i] + prices[i], dp[i][2])
54+
55+
同理可推出剩下状态部分：
56+
57+
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
58+
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
59+
60+
* dp数组如何初始化
61+
* 确定遍历顺序
62+
* 举例推导dp数组
63+
64+
```
65+
class Solution {
66+
public:
67+
int maxProfit(int k, vector<int>& prices) {
68+
69+
if (prices.size() == 0) return 0;
70+
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
71+
for (int j = 1; j < 2 * k; j += 2) {
72+
dp[0][j] = -prices[0];
73+
}
74+
for (int i = 1;i < prices.size(); i++) {
75+
for (int j = 0; j < 2 * k - 1; j += 2) { // 注意这里是等于
76+
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
77+
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
78+
}
79+
}
80+
int result = 0;
81+
for (int j = 2; j <= 2 * k; j += 2) {
82+
result = max(result, dp[prices.size() - 1][j]);
83+
}
84+
return result;
85+
}
86+
};
87+
```
88+
89+
```
90+
class Solution {
91+
public:
92+
int maxProfit(int k, vector<int>& prices) {
93+
const int n = prices.size();
94+
if (n == 0) return 0;
95+
vector<int> dp(2 * k + 1, 0);
96+
for (int i = 1;i < 2 * k;i += 2)
97+
dp[i] = -prices[0];
98+
for (int i = 1;i < n;++i) {
99+
for (int j = 0;j < 2 * k;j += 2) {
100+
dp[j] = max(dp[j], dp[j + 1] + prices[i]);
101+
dp[j + 1] = max(dp[j + 1], dp[j + 2] - prices[i]);
102+
}
103+
}
104+
return dp[0];
105+
}
106+
};
107+
108+
109+
class Solution {
110+
public:
111+
int maxProfit(vector<int>& prices) {
112+
if (prices.size() == 0) return 0;
113+
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
114+
dp[0][0] = 0;
115+
dp[0][1] = -prices[0];
116+
dp[0][3] = -prices[0];
117+
for (int i = 1; i < prices.size(); i++) {
118+
dp[i][0] = dp[i - 1][0];
119+
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
120+
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
121+
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
122+
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
123+
}
124+
return max(dp[prices.size() - 1][2], dp[prices.size() - 1][4]);
125+
126+
}
127+
};

‎problems/0205.同构字符串.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@ https://leetcode-cn.com/problems/isomorphic-strings/
44

55
##思路
66

7+
字符串没有说都是小写字母之类的，所以用数组不合适了，用map来做映射。
8+
79
使用两个map 保存 s[i] 到 t[j] 和 t[j] 到 s[i] 的映射关系，如果发现对应不上，立刻返回 false
810

911
##C++代码

0 commit comments

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