55.跳跃游戏
https://leetcode-cn.com/problems/jump-game/
难度：中等
题目介绍：
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例：
示例1：
输入： nums = [2,3,1,1,4]
输出： true
解释： 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例2：
输入： nums = [3,2,1,0,4]
输出： false
解释： 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
- 1 <= nums.length <= 3 * 10^4
- 0 <= nums[i] <= 10^5
题解：
思路：
其实每一次具体要跳几步无所谓，关键是在于可跳的范围。
不一定非要明确一次究竟要跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。在这个范围内，无论怎么跳，反正是一定可以跳过来的。所以这个问题就转化为：跳跃范围究竟可不可以覆盖到终点！
为了获得最大的覆盖范围，每次移动都需要更新最大覆盖范围 max_range。
因此，贪心算法在这里的体现就是：每次取最大跳跃范围。全局最优解为：最后得到整体最大覆盖范围，看是否能到终点。
每一次移动 index，都只能在 max_range的范围内移动，每移动一个元素，max_range就会发生更新，这也就表明 index 上限的更新，因为 i 是只能在 max_range的范围内移动的。在 python3 中，由于 for 循环在一开始会对上界进行缓存，因此如果采用 max_range作为 for 循环的上界，那么最后是无法更新 max_range的，因此在这里，采用 while 循环来进行计算。
代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) == 1:
return True
max_range = 0
index = 0
while index <= max_range:
max_range = max(index + nums[index], max_range)
if max_range >= len(nums) - 1:
return True
index += 1
return False
|