题解 | #跳跃游戏(三)#
跳跃游戏(三)
https://www.nowcoder.com/practice/d92a70f4f42248d688b93c9e50d2e757
def jump(n, nums):
if n == 0:
return -1
if n == 1:
return 0
# leng 当前所能到达的最远位置
# next 为下一次跳跃从[0,i]内的点为起点所能达到的最远位置
# 当 leng > i 时判断在[0,i]内的点为起点进行下一次跳跃所能到达的最远点
# 当 leng <= i 时此时需要进行下一步跳跃,step += 1,
# 跳跃后判断在[0,i]内的点为起点是否跳跃至该区间以外,若无法超越该区间则不能跳跃至最末端
leng, next_, step = nums[0], nums[0], 1
for i in range(1, n - 1):
if leng > i:
next_ = max(next_, nums[i] + i)
else:
leng = max(next_, nums[i] + i)
step += 1
if leng <= i:
return -1
return step
if __name__ == "__main__":
n = int(input())
nums = list(map(int, input().split()))
print(jump(n, nums))
if n == 0:
return -1
if n == 1:
return 0
# leng 当前所能到达的最远位置
# next 为下一次跳跃从[0,i]内的点为起点所能达到的最远位置
# 当 leng > i 时判断在[0,i]内的点为起点进行下一次跳跃所能到达的最远点
# 当 leng <= i 时此时需要进行下一步跳跃,step += 1,
# 跳跃后判断在[0,i]内的点为起点是否跳跃至该区间以外,若无法超越该区间则不能跳跃至最末端
leng, next_, step = nums[0], nums[0], 1
for i in range(1, n - 1):
if leng > i:
next_ = max(next_, nums[i] + i)
else:
leng = max(next_, nums[i] + i)
step += 1
if leng <= i:
return -1
return step
if __name__ == "__main__":
n = int(input())
nums = list(map(int, input().split()))
print(jump(n, nums))