下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 48 | 面试题:股票买卖系列
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享
本节摘要
展开

精选留言(25)

  • 2018-12-01
    1. 不知道是不是我一个人的问题:视频在播放到代码段的时候就卡住了,只能砍到交易两次的代码,看不到交易K次的代码,所以我无法验证问题2中白班上与代码是否匹配。
    2. 我认为白板上的递推公式推导略微有些问题。
    白板上的为:
    1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][1][k - 1] + a[i]};
    2) dp[i][1][k] = MAX{ dp[i - 1][1][k], dp[i - 1][0][k - 1] - a[i]};

    我认为方程2)后一个dp应该由dp[i - 1][0][k - 1] - a[i]修改为dp[i - 1][0][k] - a[i]。评论中有人提到这一点了。
    1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][1][k - 1] + a[i]};
    2) dp[i][1][k] = MAX{ dp[i - 1][1][k], dp[i - 1][0][k] - a[i]};
    其中,dp表示第i天,0->i天共交易了k次的最大获益。中间的0表示第i天不持有股票,1表示第i天持有股票;

    3. 还需要注意的是边间条件的处理(代码细节)。
    方程1) 中,当k = 0时,MAX中的第二个选项将会导致k - 1 < 0,数组越界,并且实际意义也是不对的,不可能在前面不发生交易的情况下持有1股股票。
    这里应当有判断:k == 0时,该情况不可能发生,可将MAX中的第二项修改为INT_MIN (C语言表示);
    当k > 0时,保持dp[i - 1][1][k - 1] + a[i]不变。

    4. 要说的是,我用C在LeetCode上测试,小规模数据时可以通过,大规模数据(K = 1000000, pricesSize非常大)时,总是出现莫名错误,还不知道是为什么。
    代码见Github:
    https://github.com/fangxlmr/LeetCode/blob/master/188.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.c
    展开
    13
  • 2018-11-25
    这个状态转移方程有个疑问,卖买一次应该是一次交易,但是状态转移的时候,卖买都算了一次?
    9
  • 2018-12-05
    借楼。
    @Mythxu
    你对交易次数的理解为:买入时增加交易次数,卖出时交易次数不变,所以,在你的递推式中,0表示当前**持有**股票,1表示当前**不持有**股票。而我则与你相反,买入时不变,而卖出时视为完成一次交易,递推式中的0表示当前**不持有**股票,1表示当前**持有**股票。所以 我们对递推式的改动恰恰相反,总的来说,殊途同归。相同的是,白班上的递推方程确实是存在问题。[我的代码在LeetCode上AC了,确认无误。]
    @zixuan
    我确实是注意到了,LeetCode 上的测试用例比较严格,当K远远大于len(prices)的时候,将会产生[Time Limit Exceed]。我认为你的方法应该可以解决该问题。我这里有另外一种更可靠,便捷的方法供参考:<Ref: http://www.cnblogs.com/grandyang/p/4295761.html>
    当K远远大于pricesSize时,DP方法要维护的数组就会相应变的很大,这将导致其非常低效。从Best Time to Buy and Sell Stock II 可以看出,在最坏的情况下(递增序列),我们每次在第 i 天买入,第 i + 1 卖出,然后再在第 i + 1 天买入,第 i + 2天卖出。这里的无穷次交易,我们最多只需要进行N次(更准确的是N - 1 次)即可获得最大收益。因此,在最多进行K次交易的情况中,当K > N 时,可以认为进行无穷次交易,将算法由DP退化为Best Time to Buy and Sell Stock II 中简单的线性扫描+比较,这样时间复杂度由O(NK)降低为O(N),空间复杂度由O(NK)将为O(1)。
    代码[Accepted]见Github:
    https://github.com/fangxlmr/LeetCode/blob/master/188.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.c
    展开

    作者回复: 👍🏻👍🏻

    1
    6
  • 2019-04-30
    按照老师的办法AC 188题可交易K次的java实现:
        public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length == 0)
                return 0;
            /**
             当k大于等于数组长度一半时, 问题退化为贪心问题此时采用 买卖股票的最佳时机 II
             的贪心方法解决可以大幅提升时间性能,如果不用这个贪心,有个testCase过不去,会报空间超
             限
             */
            if(k >= prices.length / 2)
                return greedy(prices);
            int[][][] mp = new int[prices.length][2][k + 1];
            for (int i = 0; i <= k; i++) {
                // 第 1 天买入 - 卖出循环 K 次之后不再买入,所以初始值为 0
                mp[0][0][i] = 0;
                // 第 1 天买入 - 卖出循环 K 次之后又买入,所以初始值为 -prices[0]
                mp[0][1][i] = -prices[0];
            }
            for (int i = 1; i < prices.length; i++) {
                for (int j = 0; j <= k; j++) {
                    mp[i][0][j] = j != 0 ? Math.max(mp[i - 1][1][j - 1] + prices[i], mp[i - 1][0][j]) : mp[i - 1][0][j];
                    mp[i][1][j] = Math.max(mp[i - 1][0][j] - prices[i], mp[i - 1][1][j]);
                }
            }
            int max = Integer.MIN_VALUE;
            for (int i = 0; i <= k; i++)
                max = Math.max(max, mp[prices.length - 1][0][i]);
            return max;
        }

        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;
        }
    展开

    作者回复: 帅

    1
    3
  • 2019-04-07
    老师,交易两次的代码好像不对呢,过不去
    3
  • 2019-02-11
    188题按你写法不行,开辟三维空间的话,有一个testcase过不了,超过内存限制
    3
  • 2018-11-30
    老师你这个状态方程有问题的。。这一套题我改了快三天了。。希望能更正
    应该是这样的:
    f[i+1][k][1] = max(f[i][k][1], f[i][k-1][0]-p)
    f[i+1][k][0] = max(f[i][k][0], f[i][k][1]+p)
    0的状态是第K次交易已经卖出,1是第K次交易刚刚买入,因此0的递推在1之后,并且需要用到1的数值
    3
  • 2018-11-26
    希望能贴出交易两次的代码,似乎状态转移方程并不对
    3
  • 2019-05-26
    又听到一个名词,状态压缩。
    2
  • 2019-03-05
    哥哥还是麻烦把K次的代码贴一下吧 ,自己写的根本整不出来 想要的结果,搞得都没得信心了
    2
  • 2018-12-05
    看了其他人的留言,@Miletos同学的第一个问题,白板上方程2)应该是对的,方程1)中后一个dp应该由 dp[i - 1][1][k - 1] + a[i]修改为dp[i - 1][0][k] +a[i] (即将k-1修改为k)
    我理解的交易次数是,买入时增加交易次数,卖出时交易次数不变。
    方程1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][0][k] +a[i]};MAX的后一个式子即是前面交易了k次,持股,当前第i天完成第k次交易的卖出操作。
    我修改过的状态转移方程应该跟@farFlight同学的留言一致


    展开
    2
  • 2019-09-19
    写了一个单数组的JS实现来,空间优化为O(n)。思路是观察到DP状态转移的两个函数并不会覆盖到需要使用的前一天的值,所以单个数组就足够应付了。

    ```
    var maxProfit = function(k, prices) {
      if (k <= 0 || !prices || prices.length <= 1) {
        return 0;
      }
      
      const MIN = Number.NEGATIVE_INFINITY;
      // mp[0...k -> # of transaction][0 -> no stock, 1 -> has stock]
      const mp = [
        [0, MIN],
        [0, -prices[0]],
      ];
      
      for (let i = 1; i < prices.length; i++) {
        
        const maxK = Math.min(k, Math.floor(i / 2) + 1);
        
        for (let j = 1; j <= maxK; j++) {
          if (j >= mp.length) {
            // new transaction for the day, must be buy
            mp[j] = [MIN, mp[j - 1][0] - prices[i]];
            // each day can only add one more transaction, so we are done
            break;
          }
          
         // This DP function won't accidentally overwrite needed values from
         // previous day, so a single array is enough
          mp[j][0] = Math.max(mp[j][0], mp[j][1] + prices[i]);
          mp[j][1] = Math.max(mp[j][1], mp[j - 1][0] - prices[i]);
        }
      }
      
      let max = MIN;
      
      for (let j = 0; j < mp.length; j++) {
        if (mp[j][0] > max) {
          max = mp[j][0];
        }
      }
      
      return max;
    };
    ```
    展开
    1
  • 2019-07-31
    老师好,两次交易这道题给的答案跑不过,我大概分析了下,是因为并非任意的 profit[i][j][k] 都是存在的,比如 profit[0][1][0] 就不存在。
      我把初始状态都设置为 None ,后续运算中如果出现 None ,则运算结果也是 None ,最终跑过了。
    1
  • 2019-04-11
    本课程动态规划的转移方程讲的很好,老师,还是把K次代码贴岀来吧,被折腾几天了

    作者回复: 多谢肯定! 现在没法补贴代码了,不过leetcode的讨论区里就有的。

    1
  • 2019-12-02
    Python 代码 最多交易k次的情况 终于跑通了额。。
    class Solution:
        def maxProfit(self, k: int, prices: List[int]) -> int:
            n = len(prices)
            if n == 0:
                return 0
            
            if k >= n//2:
                res = 0
                for i in range(n-1):
                    if prices[i] < prices[i+1]:
                        res += prices[i+1] - prices[i]
            else:
                res = -float('inf')
                dp = [[[0 for i in range(2)] for j in range(k+1)] for m in range(n)]

                # 第二维 当前交易次数
                # 第三维 当前是否持仓
                for i in range(k+1):
                    dp[0][i][0],dp[0][i][1] = 0,-prices[0]

     
                for i in range(1,n):
                    for j in range(0,k+1):
                        if j == 0:
                            dp[i][j][0] = dp[i-1][j][0]
                        else:
                            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]+prices[i])
                        dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]-prices[i])
                    
                for i in range(k+1):
                    res = max(res, dp[n-1][i][0])
            
            return res
    展开
  • 2019-11-08
    跪了
  • 2019-09-28
    技巧:有n个限制条件》n+1状态维度
  • 2019-07-05
    这是按照老师的方法实现的python代码,同时参考楼上@以安的 JAVA 实现
    class Solution:
        def maxProfit(self, k: int, prices: List[int]) -> int:
            if not prices:
                return 0
            # the problem will become a greedy problem if k is larger than the half length
            if k > len(prices) / 2:
                res = 0
                for i in range(1, len(prices)):
                    if prices[i] > prices[i-1]:
                        res += prices[i] - prices[i-1]
                return res
            
            dp = [[[float("-inf")] * 2 for i in range(k+1)] for i in range(len(prices))]
            # init
            for kk in range(k+1):
                dp[0][kk][0] = 0
                dp[0][kk][1] = - prices[0]
                
            for i in range(1, len(prices)):
                for kk in range(k+1):
                    # need to handle the special case when kk == 0
                    dp[i][kk][0] = max(dp[i-1][kk][0], dp[i-1][kk-1][1] + prices[i]) if kk > 0 else dp[i-1][kk][0]
                    dp[i][kk][1] = max(dp[i-1][kk][0] - prices[i], dp[i-1][kk][1])
            return max([dp[-1][kk][0] for kk in range(k+1)])
    展开
  • 2019-05-30
    当可以同时持有n 股的话,我觉得可以先计算出最多可持有一股时最大的收益,然后乘以n 就行
  • 2019-05-27
    找出问题的所有正交维来定义问题模型,dp的关键。