代码随想录27期|Python|Day32|122.买卖股票的最佳时机II|55. 跳跃游戏|45.跳跃游戏II

发布时间:2024年01月04日

122. 买卖股票的最佳时机 II

本题的思路和昨天的最大子序列和是一致的。都是只考虑正数对于总和的增益,遇到负数选择跳过。

在这里有一个计算股价利润的方式:一段时间的总利润 = 这期间每两天之差的和。

也就是nums[i + j] = nums[i] + nums[i-1] + ... + nums[i + j] - nums[i + j -1]

那么最大利润就是所有的两天之间正数差值的总和。

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

55. 跳跃游戏

思路:每一个下标都对应一个最远能到达的下标(reach),只需要检查每一个字符能到达的最大下标即可。

for循环遍历数组,在最大可到达下标值不是本下标(也就不是0)的情况下更新reach的值;一旦找到大于最后一个下标的reach就返回True,否则继续更新,直到当前下标和当前reach相等(说明遇到全部都走到0的情况了)不再更新reach。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        if len(nums) == 1:
            return True
        for i in range(len(nums)):
            if i <= reach:  # 当前下标不是最大可达下标的时候继续更新
                reach = max(i + nums[i], reach)
                if reach >= len(nums) - 1:  # 最大可达下标大于末尾下标即可返回
                    return True
        return False

45. 跳跃游戏 II

思路:本题和上面一题有很大的区别,也就是如何判断已经覆盖的基础上考虑记录步长。

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nxt_reach = 0
        cur_reach = 0
        res = 0
        if len(nums) == 1:
            return 0
        for i in range(len(nums)):
            nxt_reach = max(nxt_reach, i + nums[i])
            if i == cur_reach:
                res += 1
                cur_reach = nxt_reach
                # 在上一步和现在到达的位置中间,nxtreach是否已经可达终点,如果是,那么两步之内必然可以结束
                if nxt_reach >= len(nums) - 1:
                    break
        return res

第32天完结🎉

文章来源:https://blog.csdn.net/m0_57527624/article/details/135394693
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。