首页 > 试题广场 >

跳盒子

[编程题]跳盒子
  • 热度指数：3173 时间限制：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

输出

2

备注:
如果没有盒子或跳不到最后一个盒子上，则返回-1；如果已经在最后盒子上，则直接返回0。
算法知识视频讲解
添加回答
卑微求职头像 卑微求职 
'''
 Welcome to vivo !
'''
# leetcode 原题45   输出要改一下
#leetcode保证能跳到最后一个位置，这里不一定
def solution(step_list):
    n=len(step_list)
    max_num=0
    cnt=0
    end=0
    for i in range(n-1):
        if i<=max_num:
            max_num=max(max_num,i+step_list[i])
            #if max_num>=n-1
            if i==end:
                end=max_num
                cnt=cnt+1
    return cnt if max_num>=n-1 else -1

step_list = [int(i) for i in input().split()]
print(solution(step_list))
发表于 2020-06-07 00:35:31 回复(0)
罗布顿珠头像 罗布顿珠 
 private static int solution(int[] input) {


        if(input.length==1){
            //如果只有一个盒子，那么起点即为终点，无需跳跃
            return 0;
        }
        if(input.length>1&&input[0]==0){
            //如果不只一个盒子，那么肯定需要跳动。但是起点位置能跳跃的距离为0
            // 那么肯定到不了终点
            return -1;
        }
        //下面的代码处理需要跳动才能到达终点的情况
        int[] dp=new int[input.length];

        for (int i=0;i<input.length;i++){
            //计算能够到达最右的盒子
            int range=Math.min(input.length-1,i+input[i]);
            for (int j=i+1;j<=range;j++){
                if(dp[j]==0){
                    dp[j]=dp[i]+1;
                }
            }
        }
        int ret=dp[input.length-1];
        //需要跳动的次数至少大于0，结果出现跳动0次，说明不可达，返回-1
        return ret==0?-1:ret;

    }

发表于 2020-05-31 10:52:44 回复(0)
pein531头像 pein531
创建当前位置的列表，然后bfs构建下一个位置的列表，并依次判断下一个位置是否已经到达目的地。如果下一步的位置可以到达或超过最后一个盒子的位置就立即返回跳跃的步数以保证步数是最少的；如果在过程中发现下一步的位置全都无法继续向前移动，则返回-1，表示不可能到达最末尾的位置。 
def solution(step_list):
    # TODO Write your code here
    cur_pos = [0]          # 刚开始在起点的0位置
    n = len(step_list)
    if n == 1:
        return 0
    steps = 0
    while 1:
        next_pos = []        # pos下一步的临时位置
        while cur_pos:
            pos = cur_pos.pop(0)
            if step_list[pos] == 0:
                # 此位置无法移动，直接跳过
                continue
            # 否则遍历下一个位置的可能性
            for step in range(1, step_list[pos] + 1):
                if pos + step >= n - 1:
                    return steps + 1
                else:
                    # 如果跨step的下一个位置无法移动，则这一步不跳
                    if step_list[pos + step] == 0:
                        continue
                    next_pos.append(pos + step)
        if not next_pos:
            # 如果下一步全都无法移动，则直接break返回-1
            break
        cur_pos = next_pos
        steps += 1
    return -1

step_list = list(map(int, input().split()))
print(solution(step_list))


编辑于 2021-02-13 17:31:06 回复(0)
AidenPierc头像 AidenPierc
        // TODO Write your code here
        boolean[][] edge = newboolean[input.length][input.length];
        for(inti=0;i< input.length;i++){
            for(intj=0;j<input.length;j++){
                edge[i][j] = false;
            }
        }
        for(inti=0;i<input.length;i++){
            if(input[i]==0)continue;
            for(intj=1;j<=input[i];j++){
                if(i+j<input.length){
                    edge[i][i+j] = true;
                }
            }
        }
 
        int[] shortestPath = newint[input.length];
        for(inti=0;i<input.length;i++){
            shortestPath[i] = -1;
        }
        shortestPath[0] = 0;
        Stack<Integer> stack = newStack<>();
        Stack<Integer> auxiliary = newStack<>();
        stack.push(0);
        intcurrent = 0;
        intround = 0;
        while(round<input.length-1){
            if(shortestPath[input.length-1]!=-1)returnshortestPath[input.length-1];
            round++;
            while(!stack.isEmpty()){
                current = stack.pop();
                for(inti = 0;i<input.length;i++){
                    if(edge[current][i]&&shortestPath[i]==-1){
                        shortestPath[i]=round;
                        auxiliary.push(i);
                    }
                }
            }
            while(!auxiliary.isEmpty()){
                stack.push(auxiliary.pop());
            }
        }
        returnshortestPath[input.length-1];

先利用输入构造有向图，再求0节点到最后一个节点的单源最短路径，这里可利用广度优先遍历。（当然也可以djkstra）
发表于 2020-09-22 15:28:16 回复(0)
牛客724669211号头像 牛客724669211号 
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;
bool flag;
int solution(int a[], int N, int depth)
{
    int min_depth = INT_MAX;
    if(N <= 0){
        return depth;
    }
    if(a[0] == 0){
        return -1;
    }
    for(int i = N-1; i >= 0; i--){
        if(a[i]+i >= N){
            int temp = solution(a,i,depth+1);
            min_depth = min(min_depth, temp);
            flag = true;
        }
    }
    if(flag){
        return min_depth;
    }else{
        return -1;
    }
}

int main()
{
	string str("");
	getline(cin, str);
	int a[2000];
	int i = 0;
	char *p;
	int count = 0;

	const char* strs = str.c_str();
	p = strtok((char *)strs, " ");
	while(p)
	{
		a[i] = atoi(p);
		count++;
		p = strtok(NULL, " ");
		i++;
		if(i >= 2000)
			break;
	}
    flag = false;
	int num = solution(a, count-1, 0);
	cout << num << endl;
	return 0;
}
AC版本答案，要注意一些特殊的情况，N=1或者，N=0，结果为0；a = [1,1]结果为1；a[0]为0的话，结果为-1，用一个flag值来判断能否跳到终点。
发表于 2020-06-03 23:27:20 回复(0)
坚持挣扎头像 坚持挣扎
java递归版 
private static int rec(int[] input,int index){
    if(index==input.length-1) return 0;//刚好到最后一格
    if(index>input.length-1) return Integer.MAX_VALUE/2;//超出数组边界则返回一个较大的值
    int steps = input[index];//索引处的步数
    int step = Integer.MAX_VALUE/2;//设初始结果为不可能的较大值
    for(int i=index+1;i<=index+steps;i++){
        step = Math.min(step,rec(input,i));//从这个位置要到最后一个位置最少需要多少步
    }
    return step+1;//返回步数，加上到达这个位置的一步
}

private static int solution(int[] input) {

    // TODO Write your code here
    if(input.length==1) return 0;
    int step = rec(input,0);//从0开始递归
    if(step<=input.length) return res;//步数不会大于数组的长度
    return -1;
}
动态规划版，从后往前 
//动态规划版本
private static int solution(int[] input) {
    if(input.length==1) return 0;
    int len = input.length;
    int[] steps = new int[len];//每个数组代表到最后位置的步数
    Arrays.fill(steps,Integer.MAX_VALUE/2);
    steps[len-1]=0;//最后一个盒子是0
    for(int i=len-2;i>=0;i--){//从后往前遍历
        for(int j=1;j<=input[i];j++){//当前能走多少步
            if(i+j>=len) break;//超过数组边界就没必要进行下去了
                        //计算当前位置到最后一个盒子需要多少步
            steps[i]=Math.min(steps[i+j]+1,steps[i]);
        }
    }
    if(steps[0]<=len) return steps[0];
    return -1;
}

编辑于 2020-06-01 16:35:51 回复(1)
巨人的肩膀头像 巨人的肩膀
题目中没有说有跳跃不到终点的情况，也没说这种情况返回-1，出题不严谨，吐槽一下
下面附上解法 
int solution(int a[], int N)
{
    int left = 0;
    int right = 0;
    int step = 0;
    while (right < N - 1) {
        ++step;
        int next = right;
        for (int i = left; i <= right; ++i) {
            if (i + a[i] > next) {
                next = i + a[i];
                left = i + 1;
            }
        }
        if (next == right) return -1;
        right = next;
    }
    return step;
}


发表于 2019-11-20 22:25:12 回复(2)
C/C++
卷毛侠头像 卷毛侠 
//i+a[i]即i位置最多可跳至i+a[i]位置，最后一个位置为N-1，假如我们想跳至位置j，
//我们只需在j前面中找出不小于j的数就代表可跳至j，取最前面的那一个不小于j的就
//可得到最小步数。
int solution(int a[], int N)
{

        // TODO Write your code here
    vector<int> v;
    for(int i = 0;i < N;i++){
        v.push_back(i+a[i]);
    }
    if(v.size() == 1)
        return 0;
    int tmp = N-1;
    int step = 0;
    bool bark = false;
    for(int i = 0;i < tmp;i++){
        if(v[i] >= tmp){
            step++;
            if(i != 0){
                tmp = i;
                i = -1;  
            }
            else{
                bark = true;
                break;
            }
        }
    }
    return (bark)?step:-1;
        
}

编辑于 2019-12-24 13:59:45 回复(2)
Java
求高薪的小萌新头像 求高薪的小萌新
1000怎么可能调到最后
发表于 2021-11-11 13:50:19 回复(0)
牛客283149592号头像 牛客283149592号 
//一大堆if  else 的**算法

private static int solution(int[] input) {
        
        // TODO Write your code here
        if(input.length==1){
            //如果只有一个盒子，那么起点即为终点，无需跳跃
            return 0;
        }
           
        int step = 0;
        int end = input[0];
        int big = input[0];
        for(int i =0;i<input.length;i++){
            if(end>=i){
                if(big<input[i]+i){
                    big = input[i]+i;
                }
            }else if(end<i){
                step++;
                end = big;
                if(end<i){
                    return -1;
                }
                big = input[i]+i;
            }
            if(end>=input.length-1){
                step++;
                break;
            }
            
            
        }
        
        
        
        
        
        
        return step;
    }

发表于 2021-11-07 10:10:51 回复(0)
Python
ΔtZ.头像 Δ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)
i_am_cser头像 i_am_cser 
还是使用了递归的情况，把所有情况都考虑了一遍。后来想到，其实可以在times > min_times的时候就终止
此次递归。

void getResult(int a[], int start, int end,int times,int &min_times) {
    if (start < end && a[start] == 0) {
        return; // 不符合条件
    }
    if (start >= end) {
        if (times < min_times) { // 更新最小值
            min_times = times;
        }
        return;
    }
    for (int i = 1; i <= a[start]; i++) {
        getResult(a, start + i, end,times+1,min_times); // 迭代函数
    }
}
int solution(int a[], int N)
{
    int result = 0, min_times = N+1; // 设置不可能步数为初始值
    getResult(a, 0, N - 1,result,min_times);
    if(min_times > N) return -1;
    return min_times;
}

发表于 2020-03-07 21:14:36 回复(0)
平成最后的无业游民头像 平成最后的无业游民
倒推顺序。太坑了，没说不能的情况
n=list(map(int,input().split(" ")))
s=len(n)-1
c=0
def ss(a,b):
    for i in range(len(b)):
        if i+b[i]>=a:
            return i
    else:return -1
while s!=0 :
    s=ss(s,n[:s])
    if s==-1:
        c=-1
        break
    c=c+1
print(c)
发表于 2020-03-07 20:04:13 回复(0)
后知后觉的Jim头像 后知后觉的Jim 
//递归(纯暴力)
       private static int solution(int[] input) {
            //len-1是终点，input[i]是在当前格子i,能够跳多远
            int len=input.length; 
            int ret=recursion(0,input[0],input, len);//从第0个格子开始起跳
            return ret==len?-1:ret;//[0,1,0,1,1,0,0,0]永远跳不到终点
        }
        //start是当前处在的位置
        //capacity是当前格子能跳多远input[start]
        //len是数组input的长度
        private static int recursion(int start,int capacity,int[] input,int len){
            if(start==len-1){//到达终点
                return 0;//从终点出发，需要多个步骤能到达目标，0步
            }
            int ans=len;
            for(int i=1;i<=capacity;i++){
                if(start+i<=len-1){//从当前格子跳出距离为i，不能超出终点
                    ans=Math.min(ans,1+recursion(start+i,input[start+i],input,len));
                }else{
                    break;//憋跳了
                }
                //选择不跳，可以等到下一次再跳，i++即可
            }
            return ans;
        }
发表于 2020-03-01 12:17:40 回复(0)
今天先寄到这里头像 今天先寄到这里
///动态规划掌握的不熟悉，还是用了递归，不过比较麻烦，记录一下
#include<stdlib.h>
#include<malloc.h>
#include<vector>
using namespace std;

int solution(vector<int>a,int l){
    int al=a.size();
    int max=a[al-l-1];
    if(max==0)return -1;
    if(l<=max)return 1;
    int bushu=99999;
    int com;
        for(int j=1;j<=max;j++){
             com=solution(a,l-j);
            if(com>0&&com<bushu)bushu=com;
        }if(bushu==99999)return -1;
        else return bushu+1;
}


int main(){
    int x;int i=0;
    vector<int>a;
    vector<int>b;
    while(cin>>x){
        int tmp=x;
        a.push_back(tmp);
        b.push_back(tmp+i);
        i++;
    }//i为盒子个数，也为长度+1
    int l=a.size()-1;
    if(l==0){
        cout<<0;return 0;
    }
     int num=solution(a,l);
      cout<<num;
}
发表于 2020-02-27 10:21:35 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 数据挖掘工程师 测试开发工程师 vivo 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
15条回答 9077浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号