当前位置:   article > 正文

【LeetCode-面试-股票问题】算法中所有股票问题汇总_股票问题编程

股票问题编程

  股票问题是我们常见的算法问题,因为它可以考察我们对算法的理解以及我们的编程思维方式,同时它也是贪心算法跟动态规划的高度体现!下面是LeetCode上面所有的股票问题!

`下面两个核心方程!

第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
i代表天,k代表交易次数,0代表不持有也就是sell,1代表持有也就是buy!

`

121.买卖股票的最佳时机(easy)限定交易次数 k=1

原题:

给定一个数组 prices ,它的第i个元素prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

解法

121题限制条件:一次交易机会
那么我们目的是求出合适的买入和卖出机会,然后获得的最大利润!
因此,我们需要两个关键值,一个是最小的买入值buy,另一个是最大的利润sell!

  • 必须是先买入才能卖出,所以初始化第一天买入,然后第二天卖出
  • 循环求取每天的最大的sell和最小buy
 public int maxProfit(int prices[]) {
        int sell = 0;
        int buy = -prices[0];//假设第一天买了
        for (int i=1;i<prices.length;i++){
            sell = Math.max(sell,buy+prices[i]);//不持有,即该天的卖出,求最大利润,卖出所以是加价格
           buy = Math.max(buy,-prices[i]);//持有,即当天买入,就负的价格 -prices,
                                         // 最小买入,因为buy是负的,所以其最大就是价格最小
        }
        return sell;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

122.买卖股票的最佳时机 II(medium)交易次数无限制 k = +infinity

原题:

给定一个数组 prices ,其中prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解法

122 题限制:交易次数无限制 k = +infinity
这是经典贪心算法

  • 求最大利润,我们其实只需要考虑交易为正的情况,也就是说只要交易是正收益,就可以进行
  • 因为不限制交易次数,所以卖出的时候还可以买入,买入前也可以卖出
  • 因此,只需要将收益为正的值纳入总和即可
 public int maxProfit2(int prices[]) {
        int resSell = 0;
        for (int i=0;i<prices.length-1;i++){
            int tmp = prices[i+1]-prices[i];//卖出前必须买入。则后一天减前一天
            if(tmp>=0){//大于0,表示此次交易为正,可进行交易
                resSell+=tmp;//利润加入总和
            }
        }
        return resSell;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

也可以使用跟121题类似的方法

  • 假设第一次买入
  • 计算每次的最大买入、卖出
  • 因为是无限交易,所以买入时,我们需要带入sell总额
  • 第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
  • 第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
  • sell为该天不持有,buy为该天持有
 public int maxProfit2(int prices[]) {
  		int sell = 0;
        int buy = -prices[0];//假设第一天买了
        for (int i=1;i<prices.length;i++){
           sell = Math.max(sell,buy+prices[i]);不持有,即该天的卖出,求最大利润,卖出所以是加价格
             buy = Math.max(buy,sell-prices[i]);//持有,即当天买入,就负的价格 -prices,
                                                //又因为该天不持有时sell可能不为0,所以考虑总的收益所以得加入sell-价格
        }
        return sell;
  }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

123.买卖股票的最佳时机 III (hrad) 限定交易次数 k=2

原题:

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解法

在任意一天结束之后,我们会处于以下五个状态中的一种:
1.未进行过任何操作;
2.只进行过一次买操作;
3. 进行了一次买操作和一次卖操作,即完成了一笔交易;
4.在完成了一笔交易的前提下,进行了第二次买操作;
5.完成了全部两笔交易。
由于第一个状态的利润显然为 0,因此我们可以不用将其记录。对于剩下的四个状态,我们分别将它们的最大利润记为buy1,sell1,buy2,sell2

  • 对于buy1 而言,在第 i 天我们可以不进行任何操作,保持不变,也可以在未进行任何操作的前提下以prices[i] 的价格买入股票
  • 对于sell1而言,在第 ii 天我们可以不进行任何操作,保持不变,也可以在只进行过一次买操作的前提下以prices[i] 的价格卖出股票
  • 同理我们可以得到buy2,sell2
//注意最后一次交易持有时考虑第一次交易的sell
    public int maxProfit3(int prices[]) {
        int n = prices.length;
        int sell1 = 0;//dp[i][2][0]
        int buy1 = -prices[0];//第一次交易的dp[i][2][1]
        int sell2 = 0;//dp[i][1][0]
        int buy2 = -prices[0];//第2次交易的dp[i][1][1]
        for (int i= 1;i<n;i++ ){
            sell2 = Math.max(sell2,buy2+prices[i]);//最后一次交易(不持有)
            buy2 = Math.max(buy2,sell1-prices[i]);//最后一次持有,因为该天不持有时,有第一次交易sell1的值,所以带入
            sell1=Math.max(sell1,buy1+prices[i]);//第一次交易(不持有)
            buy1 = Math.max(buy1,-prices[i]);//第一次持有,sell为0,所以0-prices[i]
        }
        return sell2;//最后交易后的利润为总利润
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

188. 买卖股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k

原题:

给定一个整数数组prices ,它的第 i 个元素prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解法
  • 先确定k值,因为k最大为prices总天数的一半;
  • 初始化buy和sell的数组,k+1,因为k次交易,第一次交易前得进行初始化;
  • 交易前初始化buy[0],sell[0]
  • 初始化k次交易的值,都为最小值的一半,防止越界
  • 遍历价格,开始交易,确定首次交易前的buy最小,然后进行k次交易,找到最大利润
 public int maxProfit4(int k,int prices[]) {
        if(prices.length==0){
            return 0;
        }

        int n = prices.length;
        k = Math.min(k,n/2);//k最大为总天数的一半
        int[] buy = new int[k+1];
        int[] sell  = new int[k+1];

        buy[0] = -prices[0];//交易前的买入
        sell[0] = 0;//交易前的利润为0
        for (int i =1;i<=k;i++){//初始K次交易,为最小。防止越界
            buy[i] = sell[i]= Integer.MIN_VALUE/2;
        }

        for(int i=1;i<n;++i){//遍历价格,开始交易
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);//确定交易前的最小买入
            for (int j = 1; j <= k; ++j) {//开始k次交易
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);//第j次买入的最小
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);//第j次交易的利润
            }
        }
        return Arrays.stream(sell).max().getAsInt();
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

309. 最佳买卖股票时机含冷冻期(medium) 含有交易冷冻期

原题:

给定一个整数数组,其中第i个元素代表了第i天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  1. 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  2. 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
解法

存在冷冻期,就要考虑冷冻期的利润和不在冷冻期的利润

  • 手上持有股票的最大收益
  • 手上不持有股票,并且处于冷冻期中的累计最大收益
  • 手上不持有股票,并且不在冷冻期中的累计最大收益
  • 该天持有(今天买入才会持有,当前应该执行买入)=前一天持有不操作 和 前一天不持有买入(前一天不持有的话,前一天就是冷冻期,那么今天就不再冷冻期,就用不在冷冻期最大利润-价格))
  • 该天冷冻期利润(交易后才是冷冻期,当前应该进行卖出) = (今天是冷冻期那么肯定是交易后变冷冻)buy+卖出价格
  • 该天不在冷冻期(那么当前肯定是冷冻,当前冷冻不进行操作) = (今天不是冷冻期,由冷冻期过后才解冻)应该跟冷冻期比较获得最大利润
public int maxProfit5(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int n= prices.length;
        int buy = -prices[0];//手上持有股票的最大收益
        int sellC = 0;//手上不持有股票,并且处于冷冻期中的累计最大收益
        int sellO =0;//手上不持有股票,并且不在冷冻期中的累计最大收益

        for (int i =1;i<n;i++){
            int newbuy = Math.max(buy,sellO-prices[i]);//该天持有(今天买入才会持有,当前应该执行买入)=前一天持有不操作 和 前一天不持有买入
                                                        // (前一天不持有的话,前一天就是冷冻期,那么今天就不再冷冻期,就用不在冷冻期最大利润-价格)
            int newsellC = buy+prices[i];//该天冷冻期利润(交易后才是冷冻期,当前应该进行卖出) = (今天是冷冻期那么肯定是交易后变冷冻)buy+卖出价格
            int newsellO =Math.max(sellC,sellO);//该天不在冷冻期(那么当前肯定是冷冻,当前冷冻不进行操作) = (今天不是冷冻期,由冷冻期过后才解冻)应该跟冷冻期比较获得最大利润
            buy =newbuy;
            sellC=newsellC;
            sellO=newsellO;
        }
        return Math.max(sellC,sellO);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

714. 买卖股票的最佳时机含手续费 (medium) 每次交易含手续费

原题:

给定一个整数数组prices,其中第i个元素代表了第i天的股票价格 ;整数fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续

解法

无限次交易次数,但是每次卖出有手续费!

  • 我们可以将卖出的手续算进在买入的价格里!
  • 遍历所有价格
  • 当 当前价格+手续费大于我们的买入价格buy(买入价格+fee)时,那么我们的买入价格就是偏贵的,应该选择此次的买入价格!
  • 当 当前价格大于我们的buy(买入价格+fee),证明此次交易会使我们收益的,所以直接进行卖出,同时我们又可以免手续买入
 //当我们卖出一支股票时,我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
    public int maxProfit6(int[] prices, int fee) {
        if (prices.length==0){
            return 0;
        }
        int n = prices.length;
        int buy = prices[0]+fee;//买入的价格和即将卖出的手续费
        int profit =0;//总收益
        for (int i =1;i<n;i++){
            if(prices[i]+fee <buy){//当前买入价格更低,则更换买入时机
                buy = prices[i]+fee;
            }else if(prices[i]>buy){//当前价格大于买入价格,证明收益为正,则卖出
                profit+=prices[i]-buy;
                buy = prices[i];//假设又买入,准备下次比较
            }
        }
        return profit;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/628950
推荐阅读
相关标签
  

闽ICP备14008679号