题解 | #跳跃游戏(三)#

跳跃游戏(三)

http://www.nowcoder.com/practice/14abdfaf0ec4419cbc722decc709938b

题目：

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。

如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0)，请返回-1
数据保证返回的结果不会超过整形范围，即不会超过 $2^{31}-1$

方法一：贪心

需要确定两个最远覆盖距离，当前位置的最远覆盖距离currDist和下一个位置的最远覆盖距离nextDist。在移动指针到达currDist之前，不断更新nextDist，如果指针移动到了currDist,就可以更新currDist为nextDist,并且步数加一，当currDist到达终点后直接返回结果，否则不可能到达终点返回-1

alt

java
javascript

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minJumpStep (int[] nums) {
        // write code here
        if(nums.length==1)return 0;
        if(nums.length==0)return -1;
        int step=0,currDist=0,nextDist=0;//记录步数，当前位置的最远覆盖，下一个位置的最远覆盖
        for(int i=0;i<nums.length;i++){
            nextDist=Math.max(nextDist,i+nums[i]);//更新下个位置的最远覆盖
            if(i==currDist){//如果走到了当前位置的最远覆盖，更新当前位置的下一个最远位置
                currDist=nextDist;
                step++;
                if(currDist>=nums.length-1)return step;//如果当前位置的最远覆盖已经到达终点，直接返回步数
            }
        }
        return -1;
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function minJumpStep( nums ) {
    // write code here
    if(nums.length==1)return 0;
    if(nums.length==0)return -1;
    let step=0,currDist=0,nextDist=0;//记录步数，当前位置的最远覆盖，下一个位置的最远覆盖
    for(let i=0;i<nums.length;i++){
        nextDist=Math.max(nextDist,i+nums[i]);//更新下个位置的最远覆盖
        if(i==currDist){//如果走到了当前位置的最远覆盖，更新当前位置的下一个最远位置
            currDist=nextDist;
            step++;
            if(currDist>=nums.length-1)return step;//如果当前位置的最远覆盖已经到达终点，直接返回步数
        }
    }
    return -1;
}
module.exports = {
    minJumpStep : minJumpStep
};

复杂度：

时间复杂度： $O (n)$ ,一次循环
空间复杂度： $O (1)$ ,常数级空间复杂度

方法二：动态规划

定义dp数组：dp[i]表示到达i位置所需的最少步数
确定动态转移方程:在计算dp[i]时，需要搜索每一个在j=[0,i)之间的可能的上一个位置，如果j+nums[j]>=i，则说明从j位置可以到达i位置，那么到达i位置的最少步数要么是在到达j位置后再加1，要么是保持不变，因此需要在这两个值中取最小值，即 $d p [i] = M a t h . m i n (d p [i], d p [j] + 1)$
确定初始化条件：因为到达第一个位置所需步数为0因此dp[0]=0，在第一次找dp[i]的值时，为了让dp[i]取到dp[j]+1,因此dp[1:n]初始化为最大值n(n为数组长度，最大跳跃步数不可能超过数组长度)
遍历顺序：正向遍历dp数组
结果：如果dp[i]在计算后仍然等于n，说明不可能到达i位置，则也不可能到达终点

alt

java
javascript

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;
        int n=nums.length;
        int[]dp=new int[n];
        Arrays.fill(dp,n);
        dp[0]=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(j+nums[j]>=i){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
            if(dp[i]==n)return -1;
        }
      
        return dp[n-1];
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function minJumpStep( nums ) {
    // write code here
    const n=nums.length;
    if(n==0)return -1;
    let dp=new Array(n).fill(n);
    dp[0]=0;
    for(let i=1;i<n;i++){
        for(let j=0;j<i;j++){
            if(j+nums[j]>=i){
                dp[i]=Math.min(dp[i],dp[j]+1);
            }
        }
        if(dp[i]==n)return -1;
    }
    
    return dp[n-1];
}
module.exports = {
    minJumpStep : minJumpStep
};