跳跃游戏(一)

[编程题]跳跃游戏(一)

热度指数：5339 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则返回true，否则返回false。

数据范围:

$1<=nums.length<= 2\times10^5$

$0<=nums[i]<=10^5$

示例1

输入

[2,1,3,3,0,0,100]

输出

true

说明

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，再跳到nums[3]=3的位置，再直接跳到nums[6]=100，可以跳到最后，返回true

示例2

输入

[2,1,3,2,0,0,100]

输出

false

说明

无论怎么样，都跳不到nums[6]=100的位置

算法知识视频讲解

Python 3

45度信仰

从第一个元素开始，每次选取最大的 val。 value = nums[ i ], val = value+ i + 1 。当 val >= len(nums)，可以抵达

class Solution:
    def canJump(self , nums: List[int]) -> bool:
        length = len(nums)
        if length <= 1:
            return True
        i = 0
        val =  nums[i] + i
        if val >=len(nums)-1:
            return True
        while True:
            maxs = 0
            for j in range(i+1,val+1):
                if j < len(nums)-1:
                    val =  nums[j] + j
                    if val >= maxs:
                        maxs = val
                        i = j
                    if maxs >= len(nums)-1:
                        return True
            if not maxs:
                return False

发表于 2024-10-06 22:42:06 回复(0)