荐 LeetCode股票问题总结java

股票问题总结java 个人博客

https://www.b2bchain.cn/6492.html

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

 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;
        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