跳盒子

[编程题]跳盒子

热度指数：3176 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小v在公司负责游戏运营，今天收到一款申请新上架的游戏“跳一跳”，为了确保提供给广大玩家朋友们的游戏都是高品质的，按照运营流程小v必须对新游戏进行全方位了解体验和评估。这款游戏的规则如下：

有n个盒子排成了一行，每个盒子上面有一个数字a[i]，表示在该盒子上的人最多能向右移动a[i]个盒子（比如当前所在盒子上的数字是3，则表示可以一次向右前进1个盒子，2个盒子或者3个盒子）。

现在小v从左边第一个盒子上开始体验游戏，请问最少需要移动几次能到最后一个盒子上？

输入描述:

输入 ：2 2 3 0 4

表示现在有5个盒子，上面的数字分别是2, 2, 3, 0, 4。

输出描述:

输出：2

小v有两种跳法：

跳法1：盒子1 -> 盒子2 -> 盒子3 -> 盒子5，共3下

跳法2：盒子1 -> 盒子3 -> 盒子5，共2下

跳法2的步骤数最少，所以输出最少步数：2。

示例1

输入

2 2 3 0 4

输出

备注:

如果没有盒子或跳不到最后一个盒子上，则返回-1；如果已经在最后盒子上，则直接返回0。

算法知识视频讲解

Python

ΔtZ.

def canJump(nums):
    steps = 0
    max_Jump = 0
    for i in range(len(nums)-1):
        if i > max_Jump:
            return -1
        if max_Jump < i + nums[i]:
            steps +=1
            max_Jump = i + nums[i]
    if max_Jump >= len(nums) - 1: 
        return steps
    else:
        return -1

step_list = [int(i) for i in input().split()]
print(canJump(step_list))

case通过率100%

编辑于 2020-08-12 12:05:47 回复(0)