leetcode股票买卖问题

川长思鸟来 2023-06-19 05:27 2阅读 0赞

# 股票买卖问题 #

> 本人是大三学生，有问题欢迎及时指出呀

### 文章目录 ###

*  股票买卖问题
 *   *  1.\[买卖股票的最佳时机\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
     *  2.\[最佳买卖股票时机含冷冻期\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
     *  3.\[买卖股票的最佳时机含手续费\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
     *  4.\[买卖股票的最佳时机 III\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)
     *  5.\[买卖股票的最佳时机 IV\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)

## 1.[买卖股票的最佳时机][Link 1] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

**暴力法**

暴力法很简答，两层循环遍历，获取每一种利润，然后再找出最大利润

public int maxProfit(int[] prices) {
        
            int max = 0;
            //从第一个元素遍历到倒数第二个元素
            for(int i = 0;i < prices.length-1;i++){
        
                //从第二个元素遍历到最后一个元素,保证买入在卖出前
                for(int j = i+1;j < prices.length;j++){
        
                    int profile = prices[j] - prices[i];
                    if(profile > max){
        
                        max = profile;
                    }
                }
            }
            return max;
        }

//暴力法
    func maxProfit1(price []int)int{
        
    
    	if len(price) == 0{
        
    		return 0
    	}
    	max := 0
    	//第一层循环控制买入价
    	for i:= 0;i < len(price) - 1;i++{
        
    		//第二层循环控制卖出价
    		for j := i + 1;j < len(price);j++{
        
    			temp := price[j] - price[i]
    			max = int(math.Max(float64(temp), float64(max)))
    		}
    	}
    	return max
    }

**动态规划**

动态规划 前i天的最大收益 = max\{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格\}

public int maxProfitWithDp(int[] prices) {
        
            int min = Integer.MAX_VALUE;
            int max = 0;
            //找出买入价后的最大卖出价
            for(int i = 0;i<prices.length;i++){
        
                if(prices[i]<min){
        
                    //找到最小买入价
                    min = prices[i];
                }else if(prices[i] - min > max){
        
                    //找出最大利润
                    max = prices[i] - min;
                }
            }
            return max;
        }

func maxProfit(prices []int) int {
        
    
    	if len(prices) == 0{
        
    		return 0
    	}
    	min := prices[0]
    	max := 0
    	for i := 1;i < len(prices);i++{
        
    		//找出最小买入价
    		min = int(math.Min(float64(min), float64(prices[i])))
    		//找出最大利润
    		max = int(math.Max(float64(max),float64(prices[i] - min)))
    	}
    	return max
    }

## 2.[最佳买卖股票时机含冷冻期][Link 2] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

与之前不同的点：

*  可以完成多次交易
 *  每次卖出股票后需等待一天才可以买入新股票
 *  买股票前需卖出原持有股票

这个问题中存在三种状态：

*  卖出（seld）
 *  买入（hold）
 *  持有股票（什么也不干，可能处于冷冻期也可能不处于冷冻期）（rest）

这三种状态的状态转移是：

1.  持有股票到卖出即hold到seld
    
        seld[i] = hold[i - 1] + price[i]
2.  持有股票(可能前一天就持有，也可能处于冷冻期没有然后过了冷冻期后买入变为持有)
    
        hold[i] = max{hold[i - 1],rest[i - 1] - price[i]}
3.  冷冻期(可能前一天就是冷冻期今天什么也不干，也可能前一天刚卖出，今天为冷冻期)
    
        rest[i] = max{rest[i - 1],sold[i - 1]}

用profit\[i\]表示前i天的最大利润

所以动态方程为：

profit[i] = max{sold[i - 1],rest[i - 1]}

func maxProfit(prices []int) int {
        
    	if len(prices) == 0 {
        
    		return 0
    	}
    	hold := math.MinInt8
    	seld := 0
    	rest := 0
    	for i := 0;i < len(prices);i++{
        
    		//记录前一天卖出状态
    		preSeld := seld
    		//卖出状态：前一天持有然后当天卖出
    		seld = hold + prices[i]
    		//持有状态：前一天本来就持有，或者前一天冷冻期过了后当天买入
    		hold = int(math.Max(float64(hold), float64(rest-prices[i])))
    		//冷冻期状态：前一天是冷冻期，或者前一天刚好卖出
    		rest = int(math.Max(float64(rest), float64(preSeld)))
    	}
    	return int(math.Max(float64(rest), float64(seld)))
    }

public int maxProfit(int[] prices) {
        
            int sold = 0;
            int rest = 0;
            int hold = Integer.MIN_VALUE;
            for(int i : prices){
        
                //记录前一天卖出
                int preSold = sold;
                //状态转移方程：
                    // newHold = Max{oldHold,rest - price[i]}
                    // newSold = hold + price[i]
                    // newRest = Max{oldRest,oldSold}
                sold = hold + i;
                hold = Math.max(hold,rest - i);
                rest = Math.max(preSold,rest);
            }
            return Math.max(sold,rest);
        }

## 3.[买卖股票的最佳时机含手续费][Link 3] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

这道题目就没有了冷冻期的概念，即卖出后可以立即买入，但是每一次交易（买入和卖出）都需要付一次手续费

这道题目我用一个二位数组来表示状态：

dp[i][0]：第i天不持有股票的最大利润
    dp[i][1]：第i天持有股票的最大利润

分析状态转移：

从第 i - 1天状态到第 i 天 持有状态：

*  i - 1天本来持有持有
 *  i - 1天不持有但是第i天购买

dp[i] = max(dp[i - 1][1],dp[i - 1][0] - prices[i])

从第 i - 1天状态到第 i 天 不持有状态：

*  第 i - 1天本来不持有
 *  第 i - 1天本来持有但是第 i 天卖出并且交上手续费

dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee)

所以，最终状态方程：

res = max(res,Math.max(dp[i][0],dp[i][1]))

分析初始状态：

dp[0][0] = 0;
            dp[0][1] = -prices[0];

if len(prices) == 0{
        
    		return 0
    	}
    	var dp [50001][2]int
    	res := 0
    	dp[0][0] = 0
    	dp[0][1] = -prices[0]
    	for i := 1;i < len(prices);i++{
        
    		dp[i][0] = int(math.Max(float64(dp[i-1][0]), float64(dp[i-1][1] + prices[i] - fee)))
    		dp[i][1] = int(math.Max(float64(dp[i - 1][1]),float64(dp[i - 1][0] - prices[i])))
    		res = int(math.Max(float64(dp[i][0]),float64(dp[i][1])))
    	}
    	return res

public int maxProfit(int[] prices, int fee) {
        
            if(prices.length == 0){
        
                return 0;
            }
            int[][] dp = new int[prices.length][2];
            int res = 0;
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            for(int i = 1;i < prices.length;i++){
        
                dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
                dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
                res = Math.max(res,Math.max(dp[i][0],dp[i][1]));
            }
            return res;
        }

## 4.[买卖股票的最佳时机 III][III] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

这道题目跟之前又有不同了，没有了冷冻期，没有了手续费，但是限制了交易次数，只能交易两次

分析状态：

dp[i][1][0]：第一次交易第i天卖出
    dp[i][1][1]：第一次交易第i天买入
    dp[i][2][0]：第二次交易第i天卖出
    dp[i][2][1]：第二次交易第i天买入

状态转移分析：

dp[i][1][1] --》 dp[i][1][0] --》 dp[i][2][1] --》 dp[i][2][0]

所以：

func maxProfit(prices []int) int {
        
    	firstBuy := math.MinInt64
    	firstSeld := 0
    	secondBuy := math.MinInt64
    	secondSeld := 0
    	for i := 0;i < len(prices);i++{
        
    		firstBuy = int(math.Max(float64(firstBuy),float64(-prices[i])))
    		firstSeld = int(math.Max(float64(firstSeld),float64(firstBuy + prices[i])))
    		secondBuy = int(math.Max(float64(secondBuy),float64(firstSeld - prices[i])))
    		secondSeld = int(math.Max(float64(secondSeld),float64(secondBuy + prices[i])))
    	}
    	return secondSeld
    }

public int maxProfit4(int[] prices) {
        
            /**
            对于任意一天考虑四个变量:
            fstBuy: 在该天第一次买入股票可获得的最大收益 
            fstSell: 在该天第一次卖出股票可获得的最大收益
            secBuy: 在该天第二次买入股票可获得的最大收益
            secSell: 在该天第二次卖出股票可获得的最大收益
            分别对四个变量进行相应的更新, 最后secSell就是最大
            收益值(secSell >= fstSell)
            **/
            int firstBuy = Integer.MIN_VALUE;
            int firstSell = 0;
            int secondBuy = Integer.MIN_VALUE;
            int secondSell = 0;
            for(int i : prices){
        
                firstBuy = Math.max(firstBuy,-i);
                firstSell = Math.max(firstSell,firstBuy + i);
                secondBuy = Math.max(secondBuy,firstSell - i);
                secondSell = Math.max(secondSell,secondBuy + i);
            }
            return secondSell;
        }

## 5.[买卖股票的最佳时机 IV][IV] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

这道题目就是上一道的上升了，最多完成k次交易

分析状态：

dp[i][0]:i次交易下来不持有股票
    dp[i][1]:i次交易下来持有股票

分析状态转移：

i 次交易下来持有股票，可能是 i 次下来持有股票，或者 i- 1次交易下来不持有股票，但是在第 i 次交易中，买入股票，交易次数+1，达到i次，状态为持有股票

dp[i][1] = Math.max(dp[i][1],dp[i - 1][0] - p)

i 次交易下来不持有股票，可能是 i 次下来不持有股票，或者 i次交易下来持有股票，但是在第 i 次交易中，卖出股票，状态为不持有股票

dp[i][0] = Math.max(dp[i][0],dp[i][1] + p)

所以

public int maxProfit(int k, int[] prices) {
        
            if(k < 1){
        
                return 0;
            }
            //当k超过一半时，改用贪心算法
            if(k >= prices.length/2){
        
                return greedy(prices);
            }
            //dp[i][0]：第i天不持有
            //dp[i][1]：第i天持有
            int[][] dp = new int[k][2];
            for(int i = 0; i < k; ++i) {
        
                dp[i][1] = Integer.MIN_VALUE;
            }
            for(int p : prices){
        
                //第一次交易
                dp[0][1] = Math.max(dp[0][1],-p);
                dp[0][0] = Math.max(dp[0][0],dp[0][1] + p);
                //剩下k-1次
                for(int i = 1;i < k;i++){
        
                    dp[i][1] = Math.max(dp[i][1],dp[i - 1][0] - p);
                    dp[i][0] = Math.max(dp[i][0],dp[i][1] + p);
                }
            }
            return dp[k - 1][0];
        }
    
        private int greedy(int[] prices) {
        
            int max = 0;
            for(int i = 1; i < prices.length; ++i) {
        
                if(prices[i] > prices[i-1]) {
        
                    max += prices[i] - prices[i - 1];
                }
            }
            return max;
        }

[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191204144645705.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 2]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191204145932785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 3]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191204155521489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[III]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2019120416334930.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[IV]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191204165443449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70