给定一个非负整数数组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
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; } }
解题思路:首先利用跳跃游戏(一)来判断是否能够完成跳跃游戏。再使用状态数组dp来记录到达该位置的最小跳跃次数(动态规划)。dp[j]记录了到达下标为j的位置的最小步数,如果dp[j] = 0,说明该位置从未到达,因此直接赋值为dp[i] + 1(i为跳跃点),如果dp[j] != 0,说明有多种跳跃方式能够到达该位置,因此选一个dp[i] + 1与dp[j]之间的较小者。
import java.util.*; public class Solution { public int minJumpStep (int[] nums) { if(nums.length == 0)return -1; int dp [] = new int[nums.length];//dp数组 int maxindex = 0;//最大能达到的index下标 for(int i = 0; i < nums.length && i <= maxindex; ++i) { maxindex = Math.max(maxindex, i + nums[i]);//更新最大能达到的下标 for(int j = i + 1; j <= i + nums[i] && j < nums.length; ++j) { if(dp[j] == 0) dp[j] = dp[i] + 1;//当dp[j] = 0时,说明还没有能够到达该位置的跳跃点,直接用dp[i] + 1步即可。 else dp[j] = Math.min(dp[i] + 1, dp[j]);//当dp[j] != 0,说明有多种跳跃方式能够到达该位置,因此选一个小的方式。 if(j == nums.length -1) return dp[j];//此处说明已经到达最后,可以直接返回了 } } return maxindex >= nums.length - 1 ? dp[nums.length - 1] : - 1;//首先判断是否能到达最后,能到达则返回最小步数,不能到达就返回-1. } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ bool canjump(vector<int>& nums) { int dis = 0; for(int i=0; i<nums.size()-1; i++) { if(dis < i) return false; if(i + nums[i] >= nums.size()-1) return true; dis = max(dis, i+nums[i]); } return false; } int minJumpStep(vector<int>& nums) { // write code here int len = nums.size(); if(len == 1) return 0; if(len == 0) return -1; if(!canjump(nums)) return -1; int ans = 0; int premax = 0, curmax = 0; for(int i=0; i<nums.size()-1; i++) { curmax = max(curmax, i+nums[i]); if(premax == i) { ans++; premax = curmax; } } return ans; } };
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. }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int minJumpStep(vector<int>& nums) { // write code here //在每个位置从前往后遍历O(k*n),k是nums[i]的最大值(1000) if(nums.size()==0) { return -1; } vector<int> dp(nums.size(),9999999);//最后一个样例答案刚好是99999... dp[0]=0; for(int i=0;i<nums.size();i++) { for(int j=1;(j<=nums[i])&&(i+j<nums.size());j++) { dp[i+j]=min(dp[i+j],dp[i]+1); } } int rt=dp[nums.size()-1]; return (rt==9999999)?-1:rt; } int help(vector<int>& nums) { //dp[i]表示跳到i位置的最小步数 //dp[i]=min{dp[j]}+1,其中j<i&&j+nums[j]>=i //在每个位置从后往前遍历后五个样例会超时,O(n^2) if(nums.size()==0) { return -1; } vector<int> dp(nums.size(),9999999);//最后一个样例答案刚好是99999... dp[0]=0; for(int i=1;i<nums.size();i++) { for(int j=0;j<i;j++) { if(j+nums[j]>=i) { dp[i]=min(dp[i],dp[j]+1); } } } int rt=dp[nums.size()-1]; return (rt==9999999)?-1:rt; } };
//贪心:每次尽可能走最大距离,最后到达终点后,就是最小的步数(以最小的步数增加覆盖范围) int minJumpStep(vector<int>& nums) { // write code here if(nums.empty()) return -1; int curDistance=0; int nextDistance=0; int res=0; for(int i=0;i<nums.size();i++) { nextDistance=max(nextDistance,i+nums[i]);//在到达当前最大覆盖范围之前,不断更新下一步的最大覆盖范围 if(i==curDistance)//在数组范围内,到了最大的覆盖范围了 { if(i==nums.size()-1) return res;//如果当前最大覆盖范围就是数组边界,直接返回 else//当前覆盖范围没有超过数组边界 { curDistance=nextDistance;//更新范围 res++;//步数加1 if(curDistance>=nums.size()-1) return res;//预判新的范围是否超出数组边界 } } } return -1; }
class Solution { public: int minJumpStep(vector<int>& nums) { int n=nums.size();int count=0; if(n==0)return -1;if(n==1)return 0; vector<int>dp(n,100000);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){dp[cur]=1;break;} else { dp[cur+i]!=100000; dp[cur]=min(dp[cur],dp[cur+i]+1); } } } return (dp[0]==100000)?-1:dp[0]; } };贪心:
class Solution { public: int minJumpStep(vector<int>& nums) { int n=nums.size(); if(n==0)return -1; if(n==1)return 0; int val=0;int count=0;int cur=0;//cur当前位置, count步数,val能到达的最远距离。 for(int i=0;i<n-1;i++) { val=max(val,i+nums[i]); if(i>=val)return -1; if(cur>=n-1)break; if(i==cur) { count++;cur=val; } } return count; } };