一个函数解决【LeetCode 买卖股票的最佳时机】系列所有题目!

题目和题解汇总

之前介绍了【LeetCode 买卖股票的最佳时机】系列一共六道题目,这里把之前的题解还有题目链接汇总一下,方便大家查找。

第一题

LeetCode 121. 买卖股票的最佳时机
每日算法系列【LeetCode 121】买卖股票的最佳时机

第二题

LeetCode 122. 买卖股票的最佳时机 II
每日算法系列【LeetCode 122】买卖股票的最佳时机 II

第三题

LeetCode 123. 买卖股票的最佳时机 III
每日算法系列【LeetCode 123】买卖股票的最佳时机 III

第四题

LeetCode 188. 买卖股票的最佳时机 IV
每日算法系列【LeetCode 188】买卖股票的最佳时机 IV

第五题

LeetCode 714. 买卖股票的最佳时机含手续费
每日算法系列【LeetCode 714】买卖股票的最佳时机含手续费

第六题

LeetCode 309. 最佳买卖股票时机含冷冻期
每日算法系列【LeetCode 309】最佳买卖股票时机含冷冻期

通用解法

上面六道题目中,前四题限制了买卖的次数,第五题加入了手续费,第六题加入了冻结时间。所以我们提出一般性的问题:

给定每天的价格 prices,最大买卖次数 k,手续费 fee,冻结时间 freeze,求最大利润。

观察前面六题的代码,我们可以在第四题基础上进行修改,这样代码量比较小。

首先是增加手续费,这个很简单,只需要在 dp1 更新时减去一个手续费 fee 就行了。

有点麻烦的是冻结时间。在第六题代码中,增加了一个维度用来保存每一只股票之前(包含)的最大利润,目的是为了获取相隔一个冻结时间之前的股票以前可以获得的最大利润。但是通用情况下不能这么保存,不然的话空间复杂度就变成了 O(nk) ,极限情况下会爆掉。

解决方法就是,因为对于第 i 只股票来说,只需要访问它与 之间的数值,那么我们只需要保存 大小的数组就行了。在访问的时候,采用取模的方法,来让数组滚动起来。

还有一些细节,比如如果 ,那么问题就退化为了没有买卖次数限制,也就是第五题和第六题的情况。如果不这样处理的话,按照上面方法做,时间复杂度和空间复杂度都是 O(nk) ,可能会吃不消。

代码

通用函数

        class Solution:
    def solve(self, prices, k=1, fee=0, freeze=0):
        n = len(prices)
        if n == 0 or k == 0: return 0
        limit = 0 if k >= n//2 else 1
        k = 1 if k >= n//2 else k
        dp0 = [-prices[0]] * (k+1)
        dp1 = [[0]*(k+1) for _ in range(freeze+1)]
        for i in range(1, n):
            for j in range(1, k+1):
                dp0[j] = max(dp0[j], dp1[i%(freeze+1)][j-1 if limit else j]-prices[i])
                dp1[i%(freeze+1)][j] = max(dp1[(i-1)%(freeze+1)][j], dp0[j]+prices[i]-fee)
        return max(dp1[(n-1)%(freeze+1)][k], 0)
      

第一题

        class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.solve(prices, k=1, fee=0, freeze=0)
      

第二题

        class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.solve(prices, k=len(prices), fee=0, freeze=0)
      

第三题

        class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.solve(prices, k=2, fee=0, freeze=0)
      

第四题

        class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        return self.solve(prices, k, fee=0, freeze=0)
      

第五题

        class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        return self.solve(prices, len(prices), fee, 0)
      

第六题

        class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.solve(prices, k=len(prices), fee=0, freeze=1)
      
算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

京东 京东零售 总包63w
起床了的佳佳:要是我看前面就直接决定了, 你还分析,羡慕死了
点赞 评论 收藏
分享
牛客915519934号:差不多得了 ,真以为我们好忽悠呢?当初就是听了你们的话没有赶上风口入行Java,现在还想再忽悠我呢?这明显就是一个新风口,国家大力发展制造业,以后这个圈子的钱只会越来越多,不管是入门还是大佬,只要进来少说有你一口饭吃,一个个自私自利自己上了车就劝退其他人,钱都让你赚得了呗。就这点东西,入门很容易的,学个pcb,单片机就可以去找工作了,少说一万五起,以后只会越来越高,以后想进阶就去FPGA,linux,给的钱吊打互联网,再说说你们一直说数电模电难?实际呢也不过一个月就能拿下的事情,你不需要学的多深,只需要入门就足够了,就按我说的学出来少说两万起,最好报个培训班,入门更快,兄弟们跟着我冲就完事了,趁着这个机会,狠狠赚他一笔。
点赞 评论 收藏
分享
GGrain:没事,本硕985也不发面试笔试😖
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务