[Leetcode][python]Jump Game/Jump Game II/跳跃游戏/跳跃游戏 II

蛮三刀酱

发布于 2019-03-26 16:42:55

8370

文章被收录于专栏：蛮三刀的后端开发专栏蛮三刀的后端开发专栏

Jump Game

题目大意

数组中的每个值表示在当前位置最多能向前面跳几步，判断给出的数组是否否存在一种跳法跳到最后。

注意点：

所有的数字都是正数跳的步数可以比当前的值小

解题思路

参考： https://www.hrwhisper.me/leetcode-jump-game/ https://blog.csdn.net/zl87758539/article/details/51694895 意思是说：不管每一步怎么跳，我都跳到最后，跳到不能跳为止。比如我们用一个变量G，来记录我能跳到的最后的位置。对第i步来说，从第i个位置出发的最远是nums[i]+i那么我们的G=max(G,nums[i]+i) 如果在某一步i>G，也就是说，前面能跳到的最远距离跳不到i，那就肯定失败。如果最终能跳到最后一步就返回成功。

代码

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        L = len(nums)
        if L==0:
            return False
        G = nums[0]
        for i in range(1,L):
            if G<i:
                return False
            G=max(G, nums[i]+i)
            if G>=L-1:
                return True
        return G>=L-1

Jump Game II

题目大意

数组中的每个值表示在当前位置最多能向前面跳几步，判断至少跳几步能够跳到最后。注意点：

所有的数字都是正数跳的步数可以比当前的值小 假设：所有的测试用例都能够跳到最后

解题思路

参考：https://www.hrwhisper.me/leetcode-jump-game/

curReach表示当前能跳到的最远距离，lastReach表示上次最远可以跳到的距离。那么，对于每次lastReach < i 时，说明跳上一次不到i，需要cnt++

代码

这种解法的前提是假设所有都有解，所以一旦发现lastReach跳不到，就要多增加一步。

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        curReach,lastReach,cnt,Len=0,0,0,len(nums)
        for i in range(0,Len):
            if lastReach < i :
                lastReach = curReach
                cnt += 1            
            curReach = max(curReach,nums[i]+i)
        return cnt