LeetCode55. 跳跃游戏

题目大意:判断是否可以从数组的第一个位置调到最后一个位置,每次跳得步数必须小于等于当前位置上的值

题目分析:使用贪心算法,每次选择最远能达到的地方,假设从某一点最远可以到达A点,那么A点之前的所有点都是可以到达的。所以我们只要不断的更新最远可达到的点,然后看是否最远的点超过了终点即可。

具体来说,就是根据A点之前所有的点加上其最远的距离,求它们的一个最大值,求到一个reach之后,迭代地求最大值即可。

代码展示:

class Solution(object):
    def canJump(self, nums):
        reach = nums[0]
        i = 0
        while i<len(nums) and i<=reach:
            reach = max(reach,i+nums[i])
            i += 1
        if reach>=len(nums)-1:
            return True
        else:
            return False

此题如果按照每步走的可能性进行搜索,那么一旦数组长度变长,搜索空间将急剧增大,所以必然是超时的。

相关文章
相关标签/搜索