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

本是古典何须时尚 2022-06-06 21:33 450阅读 0赞

# Jump Game #

## 题目大意 ##

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

注意点：

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

## 解题思路 ##

参考：  
[https://www.hrwhisper.me/leetcode-jump-game/][https_www.hrwhisper.me_leetcode-jump-game]  
[https://blog.csdn.net/zl87758539/article/details/51694895][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/][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有点吓人。标签是贪心，但其实只要好好想是可以想出来的，并没有用到什么特别的技巧。

[https_www.hrwhisper.me_leetcode-jump-game]: https://www.hrwhisper.me/leetcode-jump-game/
[https_blog.csdn.net_zl87758539_article_details_51694895]: https://blog.csdn.net/zl87758539/article/details/51694895