欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 LeetCode股票问题总结java

程序员文章站 2022-04-19 09:06:15
股票问题总结java 个人博客https://www.b2bchain.cn/6492.html309. 最佳买卖股票时机含冷冻期//给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 //// 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): //// // 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 // 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 // ///....

股票问题总结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