代码随想录算法训练营第32天（py）| 贪心 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

本文主要是介绍代码随想录算法训练营第32天（py）| 贪心 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

思路

仅收集正利润

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

55. 跳跃游戏

力扣链接
给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

思路

探索跳跃覆盖范围究竟可不可以覆盖到终点
cover为可覆盖到的下标，i为当前下标
在cover内逐个遍历并更新cover
当cover可以达到数组末尾时，即可返回True

class Solution:def canJump(self, nums: List[int]) -> bool:if len(nums)==1:return Truecover = 0i = 0while i <= cover:cover = max(i+nums[i], cover)if cover >= len(nums)-1:return Truei += 1return False

45.跳跃游戏II

力扣链接
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置，并返回跳跃次数。

思路

统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
移动下标达到了当前覆盖的最远距离下标时：
如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution:def jump(self, nums: List[int]) -> int:if len(nums)==1:return 0curcover = 0nextcover = 0res = 0for i in range(len(nums)):nextcover = max(nextcover, nums[i]+i) #更新下一步覆盖范围if i == curcover: #如果当前覆盖范围走到头了res += 1 #需要走下一步curcover = nextcoverif nextcover >= len(nums)-1: #如果能走完就直接返回return resreturn res