股票问题-合集

字数统计: 3.6k字   |   阅读时长≈ 14分钟

股票问题-合集

题号 题解
121. 买卖股票的最佳时机 暴力解法、动态规划（Java）
122. 买卖股票的最佳时机 II 暴力搜索、贪心算法、动态规划（Java）
123. 买卖股票的最佳时机 III 动态规划（Java）
188. 买卖股票的最佳时机 IV 动态规划（「力扣」更新过用例，只有优化空间的版本可以 AC）
309. 最佳买卖股票时机含冷冻期 动态规划（Java）
714. 买卖股票的最佳时机含手续费 动态规划（Java）

题号 题解
121. 买卖股票的最佳时机 暴力解法、动态规划（Java）
122. 买卖股票的最佳时机 II 暴力搜索、贪心算法、动态规划（Java）
123. 买卖股票的最佳时机 III 动态规划（Java）
188. 买卖股票的最佳时机 IV 动态规划（「力扣」更新过用例，只有优化空间的版本可以 AC）
309. 最佳买卖股票时机含冷冻期 动态规划（Java）
714. 买卖股票的最佳时机含手续费 动态规划（Java）

1. leetcode-121. 买卖股票的最佳时机

1. 题目描述

  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

  • 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

1
2
3
4
5
6
7
8
9
10
11
12
示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2. 思路一 ： 暴力

思路：枚举所有发生一次交易的股价差。

代码1 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len < 2){        // 1. 特判
            return 0;
        }

        int res = 0;        // 有可能不发生交易，所以结果集的初始值设置为0

        // 2. 枚举所有发生一次交易的股票价格差
        for(int i = 0;i < len - 1;i++){
            for(int j = i + 1;j < len;j++){
                res =  Math.max(res,prices[j] - prices[i]);
            }
        }

        // 3. 返回结果
        return res;
    }
}

复杂度分析：

  • 时间复杂度：O(N^2)，这里 N 是股价数组的长度；
  • 空间复杂度：O(1)。

3. 思路二 ： 动态规划

思路：题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划 的方法来解决。

买卖股票有约束，根据题目意思，有以下两个约束条件：

  • 条件 1：你不能在买入股票前卖出股票；
  • 条件 2：最多只允许完成一笔交易。

因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中。

1. 状态定义：

dp[i] [j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。

  • j = 0，表示当前不持股；
  • j = 1，表示当前持股。

注意：这个状态具有前缀性质，下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]。

说明：

  • 使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少，卖出股票手上的现金数增加 这个事实；
  • 「现金数」等价于题目中说的「利润」，即先买入这只股票，后买入这只股票的差价；
  • 因此在刚开始的时候，我们的手上肯定是有一定现金数能够买入这只股票，即刚开始的时候现金数肯定不为 0，但是写代码的时候可以设置为 0。极端情况下（股价数组为 [5, 4, 3, 2, 1]），此时不发生交易是最好的（这一点是补充说明，限于我的表达，希望不要给大家造成迷惑）。

2.状态转移

dp[i][0] : 规定了今天不持股，有以下两种情况

  • 昨天不持股，今天什么都不做
  • 昨天持股 ，今天卖出股票（现金数增加）

dp[i][1] : 规定了今天持股，有以下两种情况

  • 昨天持股，今天什么都不做
  • 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）

知识点：

  • 多阶段决策问题：动态规划常常用于求解多阶段决策问题；
  • 无后效性：每一天是否持股设计成状态变量的一维。状态设置具体，推导状态转移方程方便。
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
26
27
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特判
        if(len < 2){
            return 0;
        }

        // 1. 状态定义
        int[][] dp = new int[len][2];
        // dp[i][0] 下标为i这天结束的时候，不持股，手上拥有的现金数
        // dp[i][1] 下标为i这天结束的时候，持股，手上的现金数

        // 2. 初始化 : 不持股显然为0,持股就需要减去第1天（下标为0）的股价
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 3. 状态转移
        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],-prices[i]);
        }

        // 4. 返回值
        return dp[len - 1][0];
    }
}

复杂度分析：

  • 时间复杂度：O(N)，遍历股价数组可以得到最优解；
  • 空间复杂度：O(N)，状态数组的长度为 N。

4. 处理输入

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
26
27
28
29
class MainClass{
    public static int[] stringToIntegerArray(String input){
        input = input.trim();
        input = input.substring(1,input.length() - 1);

        if (input.length() == 0){
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0;index < parts.length;index++){
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null){
            int[] prices = stringToIntegerArray(line);
            int ret = new Solution().maxProfit(prices);
            String out = String.valueOf(ret);
            System.out.println(out);
        }
    }
}

测试输出

1
2
3
4
[7,1,5,3,6,4]
5
[7,1,5,3,6,4]
5

5. 优化1：滚动数组 (待续)

6. 优化2 ： 空间优化

说明：空间优化只看状态转移方程。

状态转移方程里下标为 i 的行只参考下标为 i - 1 的行（即只参考上一行），并且：

  • 下标为 i 的行并且状态为 0 的行参考了上一行状态为 0 和 1 的行；
  • 下标为 i 的行并且状态为 1 的行只参考了上一行状态为 1 的行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len < 2){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = -prices[0];

        for(int i = 1;i < len;i++){
            dp[0] = Math.max(dp[0],dp[1] + prices[i]);
            dp[1] = Math.max(dp[1],-prices[i]);
        }
        return dp[0];
    }
}

复杂度分析：

  • 时间复杂度：O(N)，遍历股价数组可以得到最优解；
  • 空间复杂度：O(1)，状态数组的长度为 2。

7. 知识点：无后效性

  • 以下截图来自《算法导论》中文版第 15 章第 1 节的描述，这里借用它的图说明动态规划求解过程需要满足无后效性的意思

  • 一个问题的递归结构如下图所示（这里忽略问题场景）。

mark

  • 可以发现有重复求解的部分，需要添加缓存，这是「记忆化递归」。
  • 另外还可以从通过发现一个问题最开始的样子，通过「递推」一步一步求得原始问题的解，此时求解的过程如下图所示：

mark

箭头指向的地方表示当前求解的过程中参考了以前求解过的问题的结果，这个过程不能形成回路，形成回路就无法求解。

总结 ： 动态规划的两种求解形式

  • 自顶向下：也就是记忆化递归，求解过程会遇到重复子问题，所以需要记录每一个子问题的结果；
  • 自底向上：通过发现一个问题最开始的样子，通过「递推」一步一步求得原始问题的解。

在「力扣」上的绝大多数问题都可以通过「自底向上」递推的方式去做。

2. Leetcode-309. 最佳买卖股票时机含冷冻期

1. 题目描述

  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  • 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

2. 思路一 ： 暴力

  • 根据题意：由于不限制交易次数，在每一天，就可以根据当前是否持有股票选择相应的操作。「暴力搜索」在树形问题里也叫「回溯搜索」、「回溯法」。
  • 首先画出树形图，然后编码。

mark

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
26
27
28
29
30
31
// DFS
class Solution{
    public int res = 0;

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2){
            return 0;
        }
        dfs(prices,0,len,0,res);
        return res;
    }

    private void dfs(int[] prices, int start, int len, int status, int profit) {
        // 1. 递归结束的条件
        if (start == len){
            res = Math.max(res,profit);
            return;
        }

        // 2. DFS
        dfs(prices,start + 1,len,status,profit);
        if (status == 0){
            // 说明当前不持有股票 可以购入股票
            dfs(prices,start + 1,len,1,profit - prices[start]);
        }else {
            // 说明当前持有股票 可以卖掉
            dfs(prices,start + 1,len,0,profit + prices[start]);
        }
    }
}

很显然，超时在意料之中。注意看这个超时是在数据规模很大的时候，因此，可以说明搜索算法是正确的。

mark

mark

3. 思路二 ： 动态规划

根据 「力扣」第 121 题的思路，需要设置一个二维矩阵表示状态。

  1. 状态定义
  • dp[i][j] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。

注意：限定持股状态为 j 是为了方便推导状态转移方程，这样的做法满足 无后效性。

其中：

  • 第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
  • 第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
  1. 状态转移方程
  • 状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
  • 每一天状态可以转移，也可以不动。状态转移用下图表示：

mark

（状态转移方程写在代码中）

  1. 初始化
  • 如果什么都不做，dp[0][0] = 0；
  • 如果持有股票，当前拥有的现金数是当天股价的相反数，即 dp[0][1] = -prices[i]；
  1. 返回值
  • 终止的时候，上面也分析了，输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]。

代码1 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len < 2){
            return 0;
        }

        // 1. 状态定义
        int[][] dp = new int[len][2];           // 0 表示持有现金 1 表示持有股票

        // 2. 初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 3. 状态转移
        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]);
        }

        // 4. 返回值
        return dp[len - 1][0];
    }
}

复杂度分析

  • 时间复杂度：O(N），这里 N表示股价数组的长度；
  • 空间复杂度：O(N），虽然是二维数组，但是第二维是常数，与问题规模无关。

代码2：我们也可以将状态数组分开设置。

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
26
public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // cash：持有现金
        // hold：持有股票
        // 状态数组
        // 状态转移：cash → hold → cash → hold → cash → hold → cash
        int[] cash = new int[len];
        int[] hold = new int[len];

        cash[0] = 0;
        hold[0] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i]);
            hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);
        }
        return cash[len - 1];
    }
}

复杂度分析

  • 同上

4. 优化一 ： 滚动变量 （待续）

5. 优化二 ： 贪心算法

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/

714. 买卖股票的最佳时机含手续费

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信