55. 跳跃游戏

leetcode 55. 跳跃游戏
代码随想录

弄一个可移动的范围，然后在范围内一步一步的移动；如果某一步使可移动范围增加了，就更新我们的可移动范围。如果可移动范围覆盖了数组的长度，那就是能到达，否则就达到不了。

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

leetcode 45.跳跃游戏 II
代码随想录

dp 暴力，算了一下范围，肯定不会有超过len(nums)的，但是时间太长了

class Solution:def jump(self, nums: List[int]) -> int:dp = [100000001] * len(nums)dp[0] = 0for i in range(len(nums)):for j in range(i):if j + nums[j] >= i:dp[i] = min(dp[i], dp[j] + 1)return dp[-1]

定义两个覆盖范围：当前，下一个
在当前范围，没移动一下i就需要计算，这样把当前范围呢遍历完的时候，就可以找到从当前范围能达到的最远范围，不管怎么走，都只需要一步;
当i到了当前的覆盖范围，就需要进入下一个覆盖范围，这个时候步数就需要加1了,然后判断是不是能到达最后

class Solution:def jump(self, nums: List[int]) -> int:if len(nums) == 1:return 0cur_ = 0step = 0next_ = 0for i in range(len(nums)):next_ = max(i+ nums[i], next_)if i == cur_:step += 1cur_ = next_if cur_ >= len(nums) - 1:breakreturn step

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

leetcode 1005.K次取反后最大化的数组和
代码随想录

我最开始想要直接排序，然后再去取反；但是最后去找数值最小的就比较麻烦，carl说直接按照绝对值排序，很好的办法。

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key=lambda x:abs(x),reverse=True)for i in range(len(nums)):if nums[i] < 0 and k > 0:nums[i] *= -1k -= 1if k % 2 == 1:nums[-1] *= -1return sum(nums)