代码随想录算法训练营第三十二天| LeetCode122. 买卖股票的最佳时机 II、LeetCode55. 跳跃游戏、LeetCode45. 跳跃游戏 II

一、LeetCode122. 买卖股票的最佳时机 II

        1：题目描述（122. 买卖股票的最佳时机 II）

        给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

        在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

        返回 你能获得的 最大 利润 。

        2：解题思路

         具体思路：参考代码随想录：122. 买卖股票的最佳时机 II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 前一天买入，后一天卖出
        res = 0
        for i in range(len(prices)-1):
            # 记录每次前一天买入，后一天卖出，所赚取的利润
            pricesDiff = prices[i+1] - prices[i] 
            # 当利润大于0，我们就将所得的利润累加     
            if pricesDiff > 0:
                res += pricesDiff
        return res

二、LeetCode55. 跳跃游戏

        1：题目描述（55. 跳跃游戏）

        给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

        数组中的每个元素代表你在该位置可以跳跃的最大长度。

        判断你是否能够到达最后一个下标。

        2：解题思路

        具体思路：参考代码随想录：55. 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0                # 记录跳跃步数的最大值
        # nums长度为1时，及开始位置就是最后一个下标
        if len(nums) == 1: return True
        index = 0                # index表示当前位置的下标，初始为0
        while index <= cover:
            # 在当前下标index需要跳跃的步数，和cover中取最大值
            cover = max(index+nums[index], cover)
            # 跳跃的步数大于等于最后一个下标时，就一定可以到达最后一个下标
            if cover >= len(nums)-1: return True
            index += 1
        return False

三、LeetCode45. 跳跃游戏 II

        1：题目描述（45. 跳跃游戏 II）

        给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

        数组中的每个元素代表你在该位置可以跳跃的最大长度。

        你的目标是使用最少的跳跃次数到达数组的最后一个位置。

        假设你总是可以到达数组的最后一个位置。

        2：解题思路

        具体思路：参考代码随想录：45. 跳跃游戏 II

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1: return 0          # nums只有一个元素时，不需要跳跃就已经到达最后一个下标了
        ans = 0                 # 记录步数
        curDistance = 0         # 当前覆盖最远距离下标
        nextDistance = 0        # 下一步覆盖最远距离下标
        for i in range(len(nums)):
            # 更新下一步覆盖最远距离下标
            nextDistance =max(i+nums[i], nextDistance)     
            if i == curDistance:            # 遇到当前覆盖最远距离下标
                if curDistance != len(nums) - 1:        # 如果当前覆盖最远距离下标不是终点
                    ans += 1                # 需要走下一步
                    curDistance = nextDistance          # 更新当前覆盖最远距离下标（相当于加油了）
                    if nextDistance >= len(nums)-1: break       # 下一步的覆盖范围已经可以达到终点，结束循环
        return ans