荐 LeetCode股票问题总结java
股票问题总结java 个人博客
https://www.b2bchain.cn/6492.html
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
只能买卖一次,遍历维护当前最小值 一直更新最大利润即可
class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
if(len==0) return 0;
//只能买卖一次,遍历维护最小值 求得 最大利润即可
int minprice= prices[0];
int ans=Integer.MIN_VALUE;
for (int i = 1; i <len ; i++) {
if(prices[i]<minprice) minprice=prices[i];
if(ans<(prices[i]-minprice)) ans=prices[i]-minprice;
}
//细节
return ans==Integer.MIN_VALUE?0:ans;
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
122. 买卖股票的最佳时机 II 当天可以多次买卖 最大利润 :只需在涨的时候买,亏的时候不动就可以 贪心
class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
//当天可以多次买卖 最大利润 只需在涨的时候买,亏的时候不动就可以
int maxprofit=0;
for (int i = 1; i <len ; i++) {
if(prices[i]-prices[i-1]>0) maxprofit+=(prices[i]-prices[i-1]);
}
return maxprofit;
}
}
无限次买入卖出 DP通用方法
class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
if(len==0) return 0;
//dp[i][0] 当前持有股票 累计最大收益
//dp[i][1] 当前未持有股票 累计最大收益
int[][] dp=new int[len][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
for (int i = 1; i <len ; i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return Math.max(dp[len-1][0],dp[len-1][1]);
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
714. 买卖股票的最佳时机含手续费 无限次买入卖出 但是需要收取交易费(买入卖出只收一次)
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;
//第i天 持有或者 卖出 当前累计最大收益
int[][] dp=new int[len][2];
//统一 卖出时候 算手续费
dp[0][0]=-prices[0];
dp[0][1]=0;
for (int i = 1; i <len ; i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
}
//这个地方需要判断一下最大 最后一天是否需要卖出
return Math.max(dp[len-1][1],dp[len-1][0]);
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
309. 最佳买卖股票时机含冷冻期 无限次数买卖 中间需要一个冷冻期 需要用 二维 DP表示三种不同状态
(比上一题dp的增加状态)
class Solution {
public int maxProfit(int[] prices) {
//特殊情况
int len=prices.length;
if(len==0) return 0;
//dp创建
int[][] dp=new int[len][3];
//初始状态赋值
dp[0][0]= -prices[0];
//所有只与前一天进行交互
// dp[i][0]: 手上持有股票的最大收益(持有当天需要买入相当于 减去 )
// dp[i][1]: 手上不持有股票,并且处于冷冻期中的累计最大收益
// dp[i][2]: 手上不持有股票,并且不在冷冻期中的累计最大收益
for (int i = 1; i <len ; i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
dp[i][1]=dp[i-1][0]+prices[i];
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]);
}
//无需比较dp[len-1][0] 最后一天持有股票收益不可能是最高的,必然需要卖出
return Math.max(dp[len-1][1],dp[len-1][2]);
}
}
优化空间复杂度 当前状态只与 f[i-1][0] ,f[i-1][1] ,f[i-1][2] 有关 其他无需存储
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = Math.max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = Math.max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return Math.max(f1, f2);
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
123. 买卖股票的最佳时机 III 只能买卖俩次股票 只能俩笔交易 想到二维数组需要定义当前状态是否买入或者卖出
class Solution {
public int maxProfit(int[] prices) {
//只能俩笔交易 想到二维数组需要定义当前状态
int len=prices.length;
if(len==0) return 0;
//dp[i][0] 未买卖 累计最大收益
//dp[i][1] 第一次买入 累计最大收益
//dp[i][2] 第一次卖出 累计最大收益
//dp[i][3] 第二次买入 累计最大收益
//dp[i][4] 第二次卖出 累计最大收益
int[][] dp=new int[len][5];
dp[0][0]=0;
dp[0][1]=-prices[0];
for (int i = 0; i <len ; i++) {
dp[i][3]=Integer.MIN_VALUE;
}
for (int i = 1; i <len ; i++) {
dp[i][0]=0;//不操作永远为0
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
}
//比较当前手里 股票卖出状态即可
return Math.max(0,Math.max(dp[len-1][2],dp[len-1][4]));
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
188. 买卖股票的最佳时机 IV 最多完成 k 笔交易
将之前几题二维数组当中定义的 第一个状态天数 改为 交易次数(包含相应的买入+卖出 共计为一次)
动态规划求 第k次买入 卖出状态即可
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
此时相当于删掉了一维 第xxx天 此时修改后的第一维表示的是 交易次数
代表前一天交易次数和今天相等 比今天少一次
dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] - p);
//
class Solution {
public int maxProfit(int k, int[] prices) {
//本题要求【最多】允许买卖k次
// 将之前几题二维数组当中定义的 第一个状态天数 改为 交易次数(包含相应的买入+卖出 共计为一次)
int len=prices.length;
if(len==0) return 0;
if(k<1) return 0;
//大于则使用无限次交易
if(k>(len/2)) return allProfit(prices);
//第k次交易 买或者卖行为 此时最大利润
int[][] dp=new int[k][2];
//第k次买 时候 最大利润初始化
for (int i = 0; i <k ; i++) {
dp[i][0]=Integer.MIN_VALUE;
}
// 遍历每一天,模拟 k 次交易,计算并更新状态
for (int p : prices) {
dp[0][0] = Math.max(dp[0][0], 0 - p); // 第 1 次买
dp[0][1] = Math.max(dp[0][1], dp[0][0] + p); // 第 1 次卖
for (int i = 1; i < k; i++) {
dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] - p); // 第 i 次买
dp[i][1] = Math.max(dp[i][1], dp[i][0] + p); // 第 i 次卖
}
}
//最后返回卖出情况k-1
return dp[k-1][1];
}
//无限次数的交易
private int allProfit(int[] prices){
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
return res;
}
}
本文地址:https://blog.csdn.net/qq_27500493/article/details/107242567
推荐阅读
-
2020西安java面试问题总结
-
Java程序去调用并执行shell脚本及问题总结(推荐)
-
[LeetCode] 四数和值问题类型总结(哈希、双指针)
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
Java中生产者消费者问题总结
-
荐 LeetCode股票问题总结java
-
java BigInteger大整数类 和 BigDecimal大浮点数类 解决大数问题 常用方法简单学习总结
-
[JAVA]性能问题常用linux命令和java命令总结
-
JAVA内存泄漏问题处理方法经验总结
-
Leetcode 数组问题2:买卖股票的最佳时机 II