【代码随想录训练营】【Day 35】【贪心-2】| Leetcode 122, 55, 45

【代码随想录训练营】【Day 35】【贪心-2】| Leetcode 122, 55, 45

需强化知识点

• 贪心：跳跃游戏

题目

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

• 动态规划
• 贪心：只要股票第二天涨了，前一天就买，第二就买

class Solution:def maxProfit(self, prices: List[int]) -> int:# dp = [[0] * 2 for _ in range(len(prices))]# # 0 代表当天持有，1 代表当天不持有# dp[0][0] = -prices[0]# result = 0# for i in range(1, len(prices)):#     dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])#     dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])#     result = max(result, max(dp[i][0], dp[i][1]))# return resultresult = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]:result += prices[i] - prices[i-1]return result

55. 跳跃游戏

• cover记录每步能覆盖到的最大范围，只要最终cover能到达最后一个下标，即为True，注意通过 if i <= cover:来控制，在cover范围内都可以更新cover

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

45. 跳跃游戏 II

• 最小跳跃数，即每一步都是最远
• 当到达目前cover，就要跳一步，选择跳到下一步能跳到的最远，因此new_cover要一直更新，维护着下一步能跳到的最远

class Solution:def jump(self, nums: List[int]) -> int:new_cover, cover = 0, 0result = 0if len(nums) == 1:return 0for i in range(len(nums)):new_cover = max(new_cover, nums[i] + i)if i == cover:cover = new_coverresult += 1if cover >= len(nums) - 1:return resultreturn result