【代码随想录】刷题记录(85)-跳跃游戏

题目描述：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

 

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

 

我的作答：

啊啊啊啊啊圣诞节为什么我还在上班。。。。。我的怨气比鬼还重。。。。

判断是否能跳到终点，就看每一步的下一步覆盖范围有多大。像下图就是能到终点和不能到终点的情况。而贪心算法贪的就是能不能最快地到终点，比如如果我第一个数能跳到终点，就不用继续遍历第二个数了。

由此我们可以开始写：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cover = 0
        i = 0
        if len(nums)==1: return True #如果只有一个数那肯定能遍历到最后一个数
        while i<=cover:
            cover = max(i+nums[i], cover)
            if cover>=len(nums)-1: #判断累积的覆盖范围是否大于最后一个元素的下标
                return True
            i += 1
        return False

想放假想元旦想过年.................... 

 

参考代码：使用for循环，nb！

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

 

 

原文地址：https://blog.csdn.net/Aerochacha/article/details/144724939

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！