【Leetcode】【python】Jump Game Jump Game II 跳跃游戏 跳跃游戏 II

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

总结

其实这两题其实不难，标明hard有点吓人。标签是贪心，但其实只要好好想是可以想出来的，并没有用到什么特别的技巧。