55. 跳跃游戏 [medium]

https://leetcode-cn.com/problems/jump-game/

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

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

通过次数118,958 | 提交次数296,342

Second Try

参考题解才写出的通过版本，其他写法都被时间卡住了。贪心算法，这个思路还是挺特别的。每一次只比较能走的最远的位置（而不是距离），在最远位置之前的每一个位置都可以继续试一遍，得到更远的位置，然后这样一路猛推就到了。遍历只要一遍，快得飞起。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool

        有个特殊测试案例, [0]还是挂了，这种边界条件真是想不到
        """

        max_step = 0
        for i in range(len(nums)):
            max_step = max(max_step, i + nums[i])
            if max_step >= len(nums) - 1:
                return True
            # 如果这一步判断在前，则无法通过[0]的测试
            if max_step == i:
                return False
        return False

First Try （Time Exceeded Version)

递归+动态规划写法

还是超时了，有一个25003长度的数组就无法通过。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        # 加上cache，可以通过该版本，但是依然无法通过一个25003个的数组，f**k
        [2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,           7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6]

       
        卧槽，还是超时了


        """

        cache = [True for i in range(len(nums))]
        def jumpat(idx):
            # print(idx, nums[idx])
            # 不佳判断的话 [2,0] 会出现indexError
            if idx < len(nums) and not cache[idx]: 
                return False
            if idx == len(nums) - 1:
                return True
            if idx > len(nums) - 1:
                return False
            max_step = nums[idx]
            for i in range(max_step, 0, -1):  # try the maximum distance first
                r = jumpat(idx + i)
                if r:
                    return True
            cache[idx] = False
            return False

        rv = jumpat(0)
        return rv

普通递归写法

超时很明显，每次只从最小距离开始深度遍历，同时有很多重复。

后来尝试每次从最远的距离开始深度遍历，但range(max_step, 0, -1)这个逆序写错了很多次。

刚开始写成了range(max_step+1, 1, -1), 其实应该是range(max_step, 0, -1):

没想到写了那么久的range和python，在range逆序的时候竟然出现那么多bug。理解range的-1应该从for循环里每次减1的角度来考虑，而不是列表里的倒序a[::-1].

range(a, b)在改变顺序后应该是range(b, a, -1);比如range(1, 0)为空，但是range(1, 0, -1)就为[1];range(3, 1, -1)为[3, 2], 而range(1, 3)为[1,2].

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        # wtf, 超时了
        [2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6]
        """

        def jumpat(idx):
            # print(idx, nums[idx])
            if idx == len(nums) - 1:
                return True
            if idx > len(nums) - 1:
                return False
            max_step = nums[idx]
            for i in range(1, max_step + 1):
                r = jumpat(idx + i)
                if r:
                    return True
            return False

        rv = jumpat(0)
        return rv