55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1 2 3

>输入：nums = [2,3,1,1,4] >输出：true >解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1 2 3

>输入：nums = [3,2,1,0,4] >输出：false >解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

要成功跳跃，即每一步要落点在不等于0且下一次条约距离足够远的点，正向去做非常复杂，因此，正难则反…反过来思考。从最后一个节点开始，从后往前寻找能到达它的结点，重复此步骤，更新跳跃者的位置，如果在此位置前无法找到一个节点能到达此位置，说明跳跃会失败返回False…如果跳跃者位置更新到了下标为0的节点，说明跳跃成功，返回True 这里从后往前找到第一个能到达此位置的点的原因是:第一个点找到，如果存在能成功的方案，找第一个点只是增加了跳跃的次数，而不会改变能不能跳跃成功.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def canJump(self, nums):
        # 获取最后一个坐标的位置
        loc = len(nums)-1
        # 从后往前遍历
        while loc>0:
            x = loc-1
            rec = 1
            # rec代表到达当前节点需要的长度，x代表查询的坐标位置
            # 如果x节点无法跳跃到当前loc节点，则往后移动
            while x>=0 and nums[x]<rec:
                x-=1
                rec+=1
            # 此时已经遍历完所有的位置都不存在能够跳跃到达的节点，返回False
            if x<0:
                return False
            loc = x
        return True