python 买卖股票的最佳时机 LeetCode No.122

系统 421 0

python 买卖股票的最佳时机 LeetCode No.122

python 买卖股票的最佳时机 LeetCode No.122_第1张图片
解法:
一、暴力解法
二、贪心算法:由于不限制买卖次数,也没有交易费用,就可以是用贪心算法。思路:只要第二天比前一天高,我们就买进,第二天卖掉,就可以赚钱。
三、动态规划:根据算法导论这本最权威的书(最难读的一本书)中提到动态规划的四个步骤,第一刻画一个最优解的结构特征,第二递归地定义最优解的值,第三计算最优解的值,通常采用自低向上的方法,第四计算出的信息构造一个最优解(如最长公共子序列中,求出最长的子序列的其中一种组合)想了解的可以看我之前的关于动态规划的文章资料动态规划,回到这一题,找到递推公式是最重要的,也就是第二步,dp[i] = dp[i-1] if prices[i]<=prices[i-1] else dp[i-1]+(prices[i]-prices[i-1]),看起来和贪心算法的思路类似,但是如果加上别的限制条件,贪心算法就不再实用。(ps,下面那个动态规划的代码是leetcode上面的,然后我发现,和我自己写的惊人的相似,哈哈哈笑死了。)

            
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                maxProfit
              
              
                (
              
              self
              
                ,
              
               prices
              
                :
              
               List
              
                [
              
              
                int
              
              
                ]
              
              
                )
              
              
                -
              
              
                >
              
              
                int
              
              
                :
              
              
                # dp[i] = dp[i-1] if prices[i]<=prices[i-1] else dp[i-1]+(prices[i]-prices[i-1])
              
              
        res 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              
                len
              
              
                (
              
              prices
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               prices
              
                [
              
              i
              
                ]
              
              
                >
              
              prices
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                res 
              
                +=
              
              
                (
              
              prices
              
                [
              
              i
              
                ]
              
              
                -
              
              prices
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
                return
              
               res

            
          
            
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                maxProfit
              
              
                (
              
              self
              
                ,
              
               prices
              
                )
              
              
                :
              
              
                """
        :type prices: List[int]
        :rtype: int
        """
              
              
        money 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              
                len
              
              
                (
              
              prices
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               prices
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                <
              
              prices
              
                [
              
              i
              
                ]
              
              
                :
              
              
                money
              
                +=
              
              prices
              
                [
              
              i
              
                ]
              
              
                -
              
              prices
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                return
              
               money

            
          

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论