跳转至

LeetCode: 55. 跳跃游戏

1、题目描述

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

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

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

示例 1:

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

示例 2:

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

2、解题思路

​ 这个游戏一开始没什么思路,后来换个角度想一下,实际上,既然是每次最多的是当前的哪一步,也就是说,如果我们能够让最长的路线,大于等于最后一个位置,这样就能保证到达最后一个位置

​ 因此,这道题的正确解法,是使用贪心法,每一次,挑选后面可能到达最长路径的那个步伐,然后不断地向后走,直到跳不过去为止

​ 然后判断一下,是不是大于等于最后一个位置,得到结果

举个例子

[2 3 1 1 4]

首先,将数组进行变换,看每一次跳跃能够从当前位置跳到哪一步

[2 4 3 4 8]

​ 如上所示,第一步,能够看到的是4,3,也就是说,最远可以跳远额到位置4,于是,我们选择4所在的点,然后从这个点继续判断

​ 4对应的是点1,原位置是3,也就是这个点能够看到3步,也就是看到3,4,8,我们挑选最大的那个,也就是8,我们发现8已经跳出了数组,循环退出

再来看另外一个例子:

[3,2,1,0,4]

首先变换一下,看看每个点都能跳跃到的最远位置是哪个

[3 3 3 3 8] 

​ 我们发现,从第一个位置,整跳转到第三个位置,因此,我们就只能跳转到第三个位置上,然后我们发现,第三个只能跳转到它本身,这样就出问题了,因此,我们可以判断,如果当前这一次的步伐,相对于之前的步伐没有增加,直接退出循环即可,然后判断走到哪一步了


​ 或者换个思路,贪心法的状态转换方程为 pos = max(pos,nums[i]+i)

​ 我们队每一个点,判断他能不能继续往前走,如果能够正常走到最后,表示当前的思路肯定是可以的,没什么问题,如果中途被停下了,不能继续往前走,也就是说不能遇到了循环了

​ 那么什么时候是停止条件呢?

[3,2,1,0,4]

​ 我们来分析一下,首先,pos和第一个判断,也就是3+0,肯定是2比较大,这时候,pos为3,i变成了1,现在我们还是可以向后判断的,因为最大跳转两步,而1小于3,这时候,我们继续判断

​ 然后到下一步,如果说i>= pos,这时候,就不要判断了,因为pos是目前能看到的最长的位置,如果等于这个位置,表示陷入循环,超过的时候,表示跳不过去了

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        pos = -1

        length = len(nums)
        for i in range(length):
            pos = max(pos, nums[i] + i)
            if i >= pos and i < length - 1:
                return False
        return True

​ 如上,一旦想明白了以后,代码实际上很简单