贪心算法122|55|45
122买卖股票的最佳时机II
class Solution: def maxProfit(self, prices: List[int]) -> int: result = 0 for i in range(len(prices) - 1): result += max(prices[i + 1] - prices[i], 0) return result
55跳跃游戏
class Solution: def canJump(self, nums: List[int]) -> bool: if len(nums) == 1: return True cover = 0 for i in range(len(nums) - 1): if i <= cover: cover = max(cover, i + nums[i]) if cover >= len(nums) - 1: return True return False
45跳跃游戏II
class Solution: def jump(self, nums: List[int]) -> int: if len(nums) == 1: return 0 step = 0 cur_dis = 0 next_dis = 0 for i in range(len(nums)): next_dis = max(next_dis, i + nums[i]) if i == cur_dis: step += 1 cur_dis = next_dis if cur_dis >= len(nums) - 1: return step