题解 | #跳跃游戏(三)#
跳跃游戏(三)
http://www.nowcoder.com/practice/14abdfaf0ec4419cbc722decc709938b
题目：
给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。
-
如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0)，请返回-1
-
数据保证返回的结果不会超过整形范围，即不会超过
方法一：贪心
需要确定两个最远覆盖距离，当前位置的最远覆盖距离currDist和下一个位置的最远覆盖距离nextDist。在移动指针到达currDist之前，不断更新nextDist，如果指针移动到了currDist,就可以更新currDist为nextDist,并且步数加一，当currDist到达终点后直接返回结果，否则不可能到达终点返回-1
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
};
复杂度：
- 时间复杂度：,一次循环
- 空间复杂度：,常数级空间复杂度
方法二：动态规划
- 定义dp数组：dp[i]表示到达i位置所需的最少步数
- 确定动态转移方程:在计算dp[i]时，需要搜索每一个在j=[0,i)之间的可能的上一个位置，如果j+nums[j]>=i，则说明从j位置可以到达i位置，那么到达i位置的最少步数要么是在到达j位置后再加1，要么是保持不变，因此需要在这两个值中取最小值，即
- 确定初始化条件：因为到达第一个位置所需步数为0因此dp[0]=0，在第一次找dp[i]的值时，为了让dp[i]取到dp[j]+1,因此dp[1:n]初始化为最大值n(n为数组长度，最大跳跃步数不可能超过数组长度)
- 遍历顺序：正向遍历dp数组
- 结果：如果dp[i]在计算后仍然等于n，说明不可能到达i位置，则也不可能到达终点
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
};
复杂度：
- 时间复杂度：,双重循环
- 空间复杂度：,dp数组占用一定空间
