2023-12-30 买卖股票的最佳时机 II和跳跃游戏以及跳跃游戏 II

发布时间:2024年01月10日

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

思路:关键点是每一次利用峰值来计算【画图好理解一点,就是计算陡坡的值】!每一次累加和的最大! 或者可以这样理解,把利润划分为每天的,如假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。此时就是把利润分解为每天为单位的维度,而不是从 0 天到第 3 天整体去考虑!

那么根据 prices 可以得到每天的利润序列:(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

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

在这里插入图片描述

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 求峰值的一些问题!关键问题就是找出第一个小值的下标
        if len(prices) == 1 or len(prices) == 0:
            return 0
        min_value = min(prices[0],prices[1])
        count = 0
        for i in range(0, len(prices) - 1):
            if i != 0 and prices[i + 1] < prices[i]:
                count += prices[i] - min_value
                min_value = prices[i + 1]

        if min_value < prices[-1]:
            count += prices[-1] - min_value
        return count
# 贪心算法
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1, len(prices)):
            result += max(prices[i] - prices[i - 1], 0)
        return result

55. 跳跃游戏

思路:问题的核心是将跳几步转化为每次跳跃能覆盖的最大范围!

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点

img

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 进行每次跳跃覆盖的范围
        if len(nums) == 1:
            return True
        index = 0
        cover = nums[0]
        while index <= cover:
            # 更新覆盖范围 只更新比起大的范围
            cover = max(index + nums[index], cover)
            index += 1
            if cover >= len(nums) - 1:
                return True
        return False

45. 跳跃游戏 II

思路:问题的核心依旧是找出能覆盖的最大的范围,不过需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖【一轮遍历下来就可以了】

45.跳跃游戏II

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 依旧是使用覆盖范围,不过是一步一步慢慢来的
        if len(nums) == 1:
            return 0
        # 当前覆盖的的最大距离
        cur_distance = 0
        # 下一步覆盖的最大距离
        next_distance = 0
        # 步数
        res = 0
        # 需要使用到下标了
        for i in range(len(nums)):
            next_distance = max(i + nums[i], next_distance)
            if i == cur_distance:
                res += 1
                # 更新当前的覆盖距离
                cur_distance = next_distance
                if cur_distance >= len(nums) - 1:
                    return res
        return res
文章来源:https://blog.csdn.net/niuzai_/article/details/135514255
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。