首页 > 试题广场 > 跳跃游戏(三)
[编程题]跳跃游戏(三)
  • 热度指数:318 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。
1.如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0),请返回-1
2.数据保证返回的结果不会超过整形范围,即不会超过


数据范围:


示例1

输入

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

输出

3

说明

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

输入

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

输出

-1
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minJumpStep(int[] nums) {
        // write code here
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return 0;
        }

        int length = nums.length;
        int[] indexs = new int[length];
        int[] minx = new int[length];
        Arrays.fill(indexs, -1);
        for (int i = 0; i < length; i++) {
            int min = 0;
            //当前节点最短
            if (indexs[i] != -1) {
                min = minx[indexs[i]] + 1;
            }
            minx[i] = min;
            //覆盖index
            if (nums[i] > 0&&(min>0||i==0)) {
                for (int j = i+1; j <=Math.min(i + nums[i], length-1); j++) {
                    //判断最短路径
                    if (indexs[j] == -1||(indexs[j] != -1&&min<minx[indexs[j]]+1)) {
                        indexs[j] = i;
                    }
                }
                if (minx[length - 1] > 0) {
                    return minx[length - 1];
                }
            }
        }
        return minx[length - 1] > 0 ? minx[length - 1] : -1;
    }
    
}
发表于 2021-11-25 17:48:42 回复(0)