【leetcode-Python】-贪心-55. Jump Game

  • 时间:
  • 浏览:
  • 来源:互联网

题目链接

https://leetcode.com/problems/jump-game/

题目描述

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

判断你是否能够到达最后一个位置。如果能,返回true,否则返回false。

示例

输入:[2,3,1,1,4]

输出:true

可以先跳一步,从位置0到达位置1,然后从位置1跳3步到达最后一个位置。

解题思路

这道题目可以理解为“按照给定的规则跳跃,最远可以到达哪里”。如果最远可以到达的位置越过了数组的最后一个位置,那么数组的最后一个位置自然是可以达到的。nums[i]为从位置i可以跳跃的最大长度,因此如果位置i可以到达,那么i+1,.....,i+nums[i]都可以到达。

这道题可以由贪心来解,贪心的策略为“找尽可能到达最远的位置”。在遍历数组时,我们维护一个变量t表示“从起点开始跳跃,最远可以到达的位置”。那么对于当前遍历到的位置x,如果x<=t,则表示x可以从起点跳跃若干次到达。既然x能够到达, 那么我们就再更新“最远可以到达的位置”t为max(t,x+nums[x])。遍历完后判断最远可以到达的位置是否大于等于最后一个位置。如果是,则表示最后一个位置可达,返回True;否则返回False。

Python实现

我们设定位置和索引一致,即数组各个元素的位置范围为0,...,len(nums)-1。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        n = len(nums)
        for i in range(n):
            if(farthest >= i): #i可以达到 
                farthest = max(i+nums[i],farthest)#更新farthest
        return farthest >= n-1

扩展

【leetcode-Python】-动态规划&贪心-45. Jump Game II

 

 

本文链接http://www.dzjqx.cn/news/show-617051.html