区块链技术博客
www.b2bchain.cn

LeetCode股票问题总结java

这篇文章主要介绍了LeetCode股票问题总结java,通过具体代码讲解8216并且分析了LeetCode股票问题总结java的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了LeetCode股票问题总结java。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8216.html。具体如下:

股票问题总结java 个人博客

股票问题总结

———————————————————————————————————————————————————————–

 121. 买卖股票的最佳时机 

剑指 Offer 63. 股票的最大利润

 只能买卖一次,遍历维护当前最小值  一直更新最大利润即可

  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;, //只循环i即可,j为固定值0.1         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++) {                //只有此时有i-1状态改变买入dp[i - 1][1] - p                 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://www.b2bchain.cn/8216.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » LeetCode股票问题总结java
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们