Day20：贪心算法，跳跃游戏

1.55跳跃游戏

维护当前可达最远距离

1. 如果i超过了当前可达最远距离，无法达到终点
2. 当当前可达最远距离大于等于终点时，说明可达终点

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

2.45跳跃游戏

返回到达n-1的最小跳跃次数。测试用例保证可以到达n-1

1. 维护三个变量，跳跃次数，已访问的可达最远位置，当前能跳跃的最远距离

2. cur_reach和max_reach的区别

3. jumps不是在起跳时+1，程序不知道起跳点在哪，只是在必须要跳跃（超过当前跳跃边界）时才跳跃，故cur_reach不是起跳点！！

   1. ​​​​jumps += 1不是"记录起跳"，而是"记录必须进行一次新跳跃"

   2. 真正的起跳点可能是当前边界内的任意位置

   3. 算法通过farthest隐式选择了最优起跳点/降落点

   4. 不关心从哪里跳，只关心跳几次

4. 循环范围[0,n-2]：程序保证了一定能到达n-1，故在最后一个值前就确定了最后一跳，最后一个值是目标，而不是决定要不要起跳

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) max_reach = 0 jumps = 0 cur_reach = 0 for i in range(n-1): max_reach = max(max_reach, nums[i]+i) if i == cur_reach: jumps += 1 cur_reach = max_reach return jumps

3.1005. K 次取反后最大化的数组和

我的错误：应该遍历k，k为0才结束，而我遍历数组，没有考虑到当所有的负数都变成整数且k还有剩余的情况

以下是正确代码：

1. 负数：从小到大依次反转负数
2. 非负数：只操作最小值，并且只在剩余k为奇数时反转最小值
3. 两次排序

class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: nums.sort() # 翻转所有负数 for i in range(len(nums)): if nums[i] < 0 and k > 0: nums[i] = -nums[i] k -= 1 # 如果k还有剩余 if k % 2 == 1: # 翻转当前最小的元素 nums.sort() # 重新排序找到最小值 nums[0] = -nums[0] return sum(nums)