跳跃游戏(一)

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

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

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

数据范围:

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

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

输入描述:

第一行输入一个正整数 n ，表示数组 nums 的长度
第二行输入 n 个整数表示数组的每个元素

输出描述:

输出 true 或者 false

示例1

输入

7
2 1 3 3 0 0 100

输出

true

说明

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

示例2

输入

7
2 1 3 2 0 0 100

输出

false

说明

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

算法知识视频讲解

Python3

在加班的奇亚籽很刻苦

n = int(input())
nums = [int(x) for x in input().split()]
if n ==1:
    print('true')
else:
    dp = [False]*n
    target = n-1
    for i in range(n-2,-1,-1):
        if target-i <= nums[i]:
            target = i
            dp[i] = True
            continue
    print(str(dp[0]).lower())

发表于 2022-10-08 10:04:06 回复(0)