给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。
1.如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0),请返回-1
2.数据保证返回的结果不会超过整形范围,即不会超过
数据范围:
[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,1,3,2,0,0,100]
-1
public static int minJumpStep(int[] nums) { // 大致思路如下: // 1.初始化:从第0个台阶开始跳,最远可直接跳到 0 + nums[0] 的位置, // 2. 在跳到 nums[0] 之间, 再记录下来 nums[i] + i 的位置,它为最近连续两次跳过的最远位置 // 3. 如果发现 0 ~ nums[0] 之间,有更优的原则,即连续跳跃两次距离更远,就使用这个更远的距离作为下一次跳跃的开始位置 // 这是因为 0 ~ nums[0] 之间的任何一个台阶都可以一步到位,所以只需要看两次跳跃的最终距离: nums[i] + i // 4. 更新了最大跳跃的下标后,继续循环,循环过程中又继续找最大距离,直到满足最后一个元素. // 总结: 第一次初始化的时候选择第一个元素,在遍历过程中调整最优路径,确认最终位置,使得每次更新最终位置都是最优解,遍历结束则是全局最优解 int n = nums.length; if (n == 0) return -1; if (n == 1) return 0; int maxReach = 0; // 当前能够到达的最远位置 int steps = 0; // 当前步数,初始化,第一次循环为初始为1 int currEnd = 0; // 当前步数下,能够到达的最远位置 for (int i = 0; i < n - 1; i++) { maxReach = Math.max(maxReach, i + nums[i]); if (i == currEnd) { steps++; currEnd = maxReach; } if (currEnd >= n - 1) return steps; } return currEnd >= n - 1 ? steps : -1; } public static int minJumpStepDP(int[] nums) { if (nums.length == 0) return -1; int[] dp = new int[nums.length]; int maxIndex = 0; // 从第0个台阶开始尝试 for (int i = 0; i < nums.length && i <= maxIndex; ++i) { // 更新当前 i 的情况下最远能跳到的位置 maxIndex = Math.max(maxIndex, i + nums[i]); // (i+1, i+nums[i]) 之间找最优解 for (int j = i + 1; j <= i + nums[i] && j < nums.length; ++j) { // 初始化 if (dp[j] == 0) // 当 i > 0 , dp[i] 已经在之前的 dp[j] 中计算好了最优解 dp[j] = dp[i] + 1; else // 因为 i ~ i+ nums[i] 是一步到位,因此加1 dp[j] = Math.min(dp[i] + 1, dp[j]); if (j == nums.length - 1) return dp[j]; } } return maxIndex >= nums.length - 1 ? dp[nums.length - 1] : -1;//首先判断是否能到达最后,能到达则返回最小步数,不能到达就返回-1. }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ int minSteps = Integer.MAX_VALUE; public int minJumpStep (int[] nums) { // write code here int n = nums.length; if(n == 0) return -1; if(n == 1) return 0; dfs(nums, 0, 0); return minSteps == Integer.MAX_VALUE? -1: minSteps; } private void dfs(int[] nums, int cur, int steps) { if(cur >= nums.length - 1){ minSteps = Math.min(minSteps, steps); return; } if(nums[cur] == 0){ return; } for(int i = 1; i <= nums[cur]; i++){ dfs(nums, cur + i, steps + 1); } } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ public int minJumpStep (int[] nums) { // write code here int n = nums.length; if(n == 0) return -1; if(n == 1) return 0; int[] dp = new int[n]; // dp[i]表示从i位置到最后一个位置需要的最少步数 Arrays.fill(dp, Integer.MAX_VALUE); dp[n - 1] = 0; for(int cur = n - 2; cur >= 0; cur--){ for(int i = 1; i <= nums[cur]; i++){ if(cur + i >= n - 1){ // 从cur可以一步到达最后一个位置 dp[cur] = 1; break; }else{ if(dp[cur + i] != Integer.MAX_VALUE){ // 在dp[cur+i]能到达最后位置的基础上再加上一步 dp[cur] = Math.min(dp[cur], dp[cur + i] + 1); } } } } return dp[0] == Integer.MAX_VALUE? -1: dp[0]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ public int minJumpStep (int[] nums) { // write code here int n = nums.length; if(n == 0) return -1; if(n == 1) return 0; int steps = 0, cur = 0, reach = 0; // 步数,当前位置,可以到达的最远位置 for(int i = 0; i < n - 1; i++){ reach = Math.max(reach, i + nums[i]); // 可以到达的最远位置 if(i >= reach) return -1; if(cur >= n - 1) break; // 已经可以到达最后一个位置 if(i == cur){ steps++; cur = reach; } } return steps; } }