055._jump_game.md

55. Jump Game

题目: https://leetcode.com/problems/jump-game/

难度:

Medium

问题出现在一旦有0，而且这个0是不可跨过的那么无解，无法达到

看了hint，根本不用这个数组，直接用一个数来记录可达最远距离，非常巧妙

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums:
            return True
        if len(nums) == 1:
            return True
        n = len(nums)
        idx, reach = 0, 0
        while idx < n-1 and idx <= reach:  # idx <= reach是为了处理nums[idx] == 0的情况，若idx>reach说明已经失败了
            reach = max(reach, idx+nums[idx])
            idx += 1
        return reach >= n-1

idx记录当前loop位置，reach记录当前可到位置

注意这里的while循环的条件是 idx < n-1 and idx <= reach，之所以加上 idx <= reach 是因为如果idx > reach说明idx层不可达，其实也可以直接terminate.