Skip to content

Commit 5fac31e

Browse files
linwtlinwt
committed
买卖股票的最佳时机系列
1 parent cb720f7 commit 5fac31e

File tree

7 files changed

+437
-3
lines changed

7 files changed

+437
-3
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,8 @@
3333
105. 从前序与中序遍历序列构造二叉树
3434
114. 二叉树展开为链表
3535
121. 买卖股票的最佳时机
36+
122. 买卖股票的最佳时机 II
37+
123. 买卖股票的最佳时机 III
3638
130. 被围绕的区域
3739
131. 分割回文串
3840
136. 只出现一次的数字
@@ -44,6 +46,7 @@
4446
155. 最小栈
4547
160. 相交链表
4648
169. 多数元素
49+
188. 买卖股票的最佳时机 IV
4750
200. 岛屿数量
4851
206. 反转链表
4952
216. 组合总和 III
@@ -55,6 +58,7 @@
5558
300. 最长上升子序列
5659
303. 区域和检索 - 数组不可变
5760
304. 二维区域和检索 - 矩阵不可变
61+
309. 最佳买卖股票时机含冷冻期
5862
322. 零钱兑换
5963
338. 比特位计数
6064
406. 根据身高重建队列
@@ -75,6 +79,7 @@
7579
617. 合并二叉树
7680
695. 岛屿的最大面积
7781
698. 划分为k个相等的子集
82+
714. 买卖股票的最佳时机含手续费
7883
1020. 飞地的数量
7984
1254. 统计封闭岛屿的数目
8085
1905. 统计子岛屿

‎leetcode_Java/Solution0121.java

Lines changed: 46 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,54 @@
11
// 121. 买卖股票的最佳时机
22

33

4+
/*
5+
动态规划：
6+
1、定义dp数组：
7+
dp[i][0] 表示第i天交易结束后不持有股票的最大利润
8+
dp[i][1] 表示第i天交易结束后持有股票的最大利润
9+
2、状态转移方程
10+
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
11+
第i天不持有股票 前一天不持有股票 前一天持有股票且今天卖出
12+
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); // 注意：只能买卖一次，所以买入时的利润为-prices[i]
13+
第i天持有股票 前一天持有股票 今天买入
14+
3、初始化
15+
dp[0][0] = 0 表示第0天不持有股票，最大利润为0。创建数组时默认为0，可省略
16+
dp[0][1] = -prices[0] 表示第0天持有股票，最大利润为-prices[0]
17+
4、遍历dp数组填表：一个for循环遍历数组，根据状态转移方程直接取dp数组的已知结果计算未知结果
18+
5、返回结果：最后一个不持有股票的状态就是结果
19+
20+
二维dp数组更新过程
21+
prices = [7,1,5,3,6,4]
22+
0 -7
23+
0 -1
24+
4 -1
25+
4 -1
26+
5 -1
27+
5 -1
28+
*/
29+
class Solution {
30+
public int maxProfit(int[] prices) {
31+
int n = prices.length;
32+
int[][] dp = new int[n][2];
33+
dp[0][0] = 0;
34+
dp[0][1] = -prices[0];
35+
for (int i = 1; i < n; i++) {
36+
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
37+
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
38+
}
39+
return dp[n - 1][0];
40+
}
41+
}
42+
43+
444
/*
545
动态规划思路：
6-
1、dp[i]表示前i+1天可获得的最大利润
7-
2、初始条件：dp[0] = 0，第1天的最大利润为0
8-
3、状态转移方程：dp[i] = Math.max(dp[i - 1], prices[i] - minPrice)
46+
1、定义dp数组：dp[i]表示第i天交易结束后可获得的最大利润（天数从0开始，与索引对应，方便理解）
47+
2、状态转移方程：dp[i] = Math.max(dp[i - 1], prices[i] - minPrice)
48+
第i-1天可获得的最大利润 第i天卖出可获得的最大利润
49+
3、初始化：dp[0] = 0，第0天的最大利润为0
50+
4、遍历dp数组填表：一个for循环遍历数组，根据状态转移方程直接取dp数组的已知结果计算未知结果
51+
5、返回结果：最后一个状态就是结果
952
*/
1053
class Solution {
1154
public int maxProfit(int[] prices) {

‎leetcode_Java/Solution0122.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
// 122. 买卖股票的最佳时机 II
2+
3+
4+
/*
5+
动态规划：
6+
1、定义dp数组：
7+
dp[i][0] 表示第i天交易结束后不持有股票的最大利润
8+
dp[i][1] 表示第i天交易结束后持有股票的最大利润
9+
2、状态转移方程
10+
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
11+
第i天不持有股票 前一天不持有股票 前一天持有股票且今天卖出
12+
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 注意：可以买卖多次，所以买入时的利润包含之前所得利润，即dp[i - 1][0] - prices[i]
13+
第i天持有股票 前一天持有股票 前一天不持有股票且今天买入
14+
3、初始化
15+
dp[0][0] = 0 表示第0天不持有股票，最大利润为0。创建数组时默认为0，可省略
16+
dp[0][1] = -prices[0] 表示第0天持有股票，最大利润为-prices[0]
17+
4、遍历dp数组填表：一个for循环遍历数组，根据状态转移方程直接取dp数组的已知结果计算未知结果
18+
5、返回结果：最后一个不持有股票的状态就是结果
19+
20+
二维dp数组更新过程
21+
prices = [7,1,5,3,6,4]
22+
0 -7
23+
0 -1
24+
4 -1
25+
4 1
26+
7 1
27+
7 3
28+
*/
29+
class Solution {
30+
public int maxProfit(int[] prices) {
31+
int n = prices.length;
32+
int[][] dp = new int[n][2];
33+
dp[0][0] = 0;
34+
dp[0][1] = -prices[0];
35+
for (int i = 1; i < n; i++) {
36+
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
37+
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
38+
}
39+
return dp[n - 1][0];
40+
}
41+
}
42+
43+
44+
/*
45+
动态规划
46+
1、状态压缩：每一天的状态只与前一天的状态有关，使用变量存储状态 dp[i][0]、dp[i][1]
47+
2、定义状态：
48+
dp0 表示第i天交易结束后不持有股票的最大利润
49+
dp1 表示第i天交易结束后持有股票的最大利润
50+
*/
51+
class Solution {
52+
public int maxProfit(int[] prices) {
53+
int n = prices.length;
54+
int dp0 = 0, dp1 = -prices[0];
55+
for (int i = 1; i < n; i++) {
56+
int newDp0 = Math.max(dp0, dp1 + prices[i]);
57+
int newDp1 = Math.max(dp1, dp0 - prices[i]);
58+
dp0 = newDp0;
59+
dp1 = newDp1;
60+
}
61+
return dp0;
62+
}
63+
}
64+
65+
66+
/*
67+
贪心：根据股票价格画出折线图，由于交易次数不限，因此把每次上涨差值累加就是最大利润
68+
*/
69+
class Solution {
70+
public int maxProfit(int[] prices) {
71+
int res = 0;
72+
for (int i = 1; i < prices.length; i++) {
73+
res += Math.max(0, prices[i] - prices[i - 1]);
74+
}
75+
return res;
76+
}
77+
}

‎leetcode_Java/Solution0123.java

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
// 123. 买卖股票的最佳时机 III
2+
3+
4+
/*
5+
与 188.买卖股票的最佳时机IV 解法相同，将k值设置为2即可
6+
*/
7+
class Solution {
8+
public int maxProfit(int[] prices) {
9+
int n = prices.length;
10+
if (n <= 1) {
11+
return 0;
12+
}
13+
int[][][] dp = new int[n][3][2];
14+
for (int j = 1; j <= 2; j++) {
15+
dp[0][j][0] = 0;
16+
dp[0][j][1] = -prices[0];
17+
}
18+
for (int i = 1; i < n; i++) {
19+
for (int j = 1; j <= 2; j++) {
20+
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
21+
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
22+
}
23+
}
24+
return dp[n - 1][2][0];
25+
}
26+
}
27+
28+
29+
/*
30+
状态压缩，去掉天数的维度，交易次数和是否持有股票构成的二维数组变成滚动数组
31+
*/
32+
class Solution {
33+
public int maxProfit(int[] prices) {
34+
int n = prices.length;
35+
if (n <= 1) {
36+
return 0;
37+
}
38+
int[][] dp = new int[3][2];
39+
for (int j = 1; j <= 2; j++) {
40+
dp[j][0] = 0;
41+
dp[j][1] = -prices[0];
42+
}
43+
for (int i = 1; i < n; i++) {
44+
for (int j = 1; j <= 2; j++) {
45+
dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
46+
dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);
47+
}
48+
}
49+
return dp[2][0];
50+
}
51+
}
52+
53+
54+
/*
55+
动态规划，多个一维dp数组，记录多种状态
56+
*/
57+
class Solution {
58+
public int maxProfit(int[] prices) {
59+
int n = prices.length;
60+
int[] buy1 = new int[n];
61+
int[] sell1 = new int[n];
62+
int[] buy2 = new int[n];
63+
int[] sell2 = new int[n];
64+
buy1[0] = -prices[0]; sell1[0] = 0;
65+
buy2[0] = -prices[0]; sell2[0] = 0;
66+
for (int i = 1; i < n; i++) {
67+
buy1[i] = Math.max(buy1[i - 1], -prices[i]);
68+
sell1[i] = Math.max(sell1[i - 1], buy1[i - 1] + prices[i]);
69+
buy2[i] = Math.max(buy2[i - 1], sell1[i - 1] - prices[i]);
70+
sell2[i] = Math.max(sell2[i - 1], buy2[i - 1] + prices[i]);
71+
}
72+
return sell2[n-1];
73+
}
74+
}
75+
76+
77+
/*
78+
动态规划：
79+
1、将多个一维数组写成一个二维数组，行表示天数，四列表示四种状态
80+
2、定义dp数组：
81+
dp[i][0] 表示第i天交易结束后，进行过第一次买入，获取的最大利润
82+
dp[i][1] 表示第i天交易结束后，进行过第一次卖出，获取的最大利润
83+
dp[i][2] 表示第i天交易结束后，进行过第二次买入，获取的最大利润
84+
dp[i][3] 表示第i天交易结束后，进行过第二次卖出，获取的最大利润
85+
*/
86+
class Solution {
87+
public int maxProfit(int[] prices) {
88+
int n = prices.length;
89+
int[][] dp = new int[n][4];
90+
dp[0][0] = dp[0][2] = -prices[0];
91+
dp[0][1] = dp[0][3] = 0;
92+
for (int i = 1; i < n; i++) {
93+
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
94+
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
95+
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
96+
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
97+
}
98+
return dp[n - 1][3];
99+
}
100+
}
101+
102+
103+
/*
104+
动态规划：状态压缩
105+
1、状态定义：由于最多可以完成两笔交易，因此在任意一天结束之后，会处于以下五个状态中的一种
106+
1）没有操作。利润为0，不用记录
107+
2）buy1：第一次买入，获取的最大利润
108+
3）sell1：第一次卖出，获取的最大利润
109+
4）buy2：第二次买入，获取的最大利润
110+
5）sell2：第二次卖出，获取的最大利润
111+
2、状态转移：
112+
buy1 = Math.max(buy1, -prices[i]); // 在第i天没有操作，取前一天buy1的状态。或者在没有操作的前提下以prices[i]的价格买入股票
113+
sell1 = Math.max(sell1, buy1 + prices[i]); // 在第i天没有操作，取前一天sell1的状态。或者在第一次买入的前提下以prices[i]的价格卖出股票
114+
buy2 = Math.max(buy2, sell1 - prices[i]); // 在第i天没有操作，取前一天buy2的状态。或者在第一次卖出的前提下以prices[i]的价格买入股票
115+
sell2 = Math.max(sell2, buy2 + prices[i]); // 在第i天没有操作，取前一天sell2的状态。或者在第二次买入的前提下以prices[i]的价格卖出股票
116+
3、初始化：第0天的状态
117+
buy1 = -prices[0] 表示以prices[0]的价格买入股票
118+
sell1 = 0 表示在同一天买入并且卖出，利润为0
119+
buy2 = -prices[0] 表示以prices[0]的价格买入股票
120+
sell2 = 0 表示在同一天买入并且卖出，利润为0
121+
4、遍历更新状态：一个for循环遍历数组，根据状态转移方程直接取dp数组的已知结果计算未知结果
122+
5、返回结果：直接返回sell2
123+
1）无交易情况，sell2为0，返回sell2
124+
2）只完成交易一次，由于存在同一天买卖的情况，所以sell1可以转移到sell2，返回sell2
125+
3）完成两次交易，返回sell2
126+
*/
127+
class Solution {
128+
public int maxProfit(int[] prices) {
129+
int n = prices.length;
130+
int buy1 = -prices[0], sell1 = 0;
131+
int buy2 = -prices[0], sell2 = 0;
132+
for (int i = 1; i < n; i++) {
133+
buy1 = Math.max(buy1, -prices[i]);
134+
sell1 = Math.max(sell1, buy1 + prices[i]);
135+
buy2 = Math.max(buy2, sell1 - prices[i]);
136+
sell2 = Math.max(sell2, buy2 + prices[i]);
137+
}
138+
return sell2;
139+
}
140+
}

‎leetcode_Java/Solution0188.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
// 188. 买卖股票的最佳时机 IV
2+
3+
4+
/*
5+
动态规划：
6+
1、定义dp数组：
7+
1）存在三种「状态」：天数、交易次数、是否持有股票，因此定义三维dp
8+
2）dp[i][j][0] 表示第i天，已经进行了j次交易，不持有股票，获取的最大利润
9+
dp[i][j][1] 表示第i天，已经进行了j次交易，持有股票，获取的最大利润
10+
2、状态转移方程
11+
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
12+
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
13+
3、初始化：
14+
dp[0][j][0] = 0 表示第0天，不持有股票，任意交易次数，获取的最大利润都为0。创建数组时默认为0，可省略
15+
dp[0][j][1] = -prices[0] 表示第0天，持有股票，任意交易次数，获取的最大利润都为-prices[0]
16+
4、遍历dp数组填表：第一层遍历天数，第二层遍历交易次数，根据状态转移方程填表。计算当前状态只跟前一天有关，所以两个for循环顺序先后都可以。
17+
5、返回结果：最后一个状态就是结果。即最后一天，已经进行了k次交易，不持有股票，获取的最大利润
18+
6、其他细节：
19+
1）数组至少包含两个元素，即至少有两天才能完成一次交易，否则返回0
20+
2）一次交易需要买入和卖出共两天，最大交易次数为数组长度的一半，所以交易次数进行比较取最小值即可
21+
3）dp数组定义时k+1，因为交易次数可能为0-k次，或者说计算状态时j-1可能为0，要用到交易次数为0的状态，所以总共有k+1个状态
22+
4）[买,卖][买,卖]... 将买入股票时作为一次交易，也就是在买入股票的时候交易次数加1，所以 dp[i - 1][j - 1][0] - prices[i] 买入时前一天的交易次数为j-1，买入后交易次数为j
23+
24+
三维数组更新过程，左上角表示天数，行表示交易次数，列表示是否持有股票
25+
k = 2, prices = [3,2,6,5,0,3]
26+
0 1 2 3 4 5
27+
0 0 0 0 0 0 0 0 0 0 0 0
28+
0 -3 0 -2 4 -2 4 -2 4 0 4 0
29+
0 -3 0 -2 0 -2 4 -1 4 4 7 4
30+
*/
31+
class Solution {
32+
public int maxProfit(int k, int[] prices) {
33+
int n = prices.length;
34+
if (n <= 1) {
35+
return 0;
36+
}
37+
k = Math.min(k, n / 2);
38+
int[][][] dp = new int[n][k + 1][2];
39+
for (int j = 1; j <= k; j++) {
40+
dp[0][j][0] = 0;
41+
dp[0][j][1] = -prices[0];
42+
}
43+
for (int i = 1; i < n; i++) {
44+
for (int j = 1; j <= k; j++) {
45+
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
46+
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
47+
}
48+
}
49+
return dp[n - 1][k][0];
50+
}
51+
}
52+
53+
54+
/*
55+
动态规划，状态压缩，去掉天数的维度，交易次数和是否持有股票构成的二维数组变成滚动数组
56+
*/
57+
class Solution {
58+
public int maxProfit(int k, int[] prices) {
59+
int n = prices.length;
60+
if (n <= 1) {
61+
return 0;
62+
}
63+
k = Math.min(k, n / 2);
64+
int[][] dp = new int[k + 1][2];
65+
for (int j = 1; j <= k; j++) {
66+
dp[j][0] = 0;
67+
dp[j][1] = -prices[0];
68+
}
69+
for (int i = 1; i < n; i++) {
70+
for (int j = 1; j <= k; j++) {
71+
dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
72+
dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);
73+
}
74+
}
75+
return dp[k][0];
76+
}
77+
}

0 commit comments

Comments
 (0)