给出一个非负整数数组,你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置
例如
给出数组 A =[2,3,1,1,4]
给出数组 A =[2,3,1,1,4]
[2,3,1,1,4]
2
public class Solution { public int jump(int[] A) { if(A == null || A.length <= 0) return -1; // 动态规划,dp[i]放置到达i点的最少步数 int[] dp = new int[A.length]; // 首先都赋值max for(int i = 0; i < A.length; i++) dp[i] = Integer.MAX_VALUE; dp[0] = 0; for(int i = 0; i < A.length; i++){ // A[i]>0,说明此点可达 if(A[i] > 0){ for(int j = 1; j <= A[i]; j++){ if(i + j < A.length) dp[i + j] = Math.min(dp[i] + 1, dp[i + j]); // 第一次到达终点直接返回 if(i + j == A.length - 1) return dp[A.length - 1]; } } } return dp[A.length - 1]; } }
/* * Runtime: 9 ms. Your runtime beats 93.99 % of java submissions. * 参考自leetcode网友:@ChengZhang * The main idea is based on greedy. Let's say the range of the current jump * is [curBegin, curEnd], curFarthest is the farthest point that all points * in [curBegin, curEnd] can reach. Once the current point reaches curEnd, * then trigger another jump, and set the new curEnd with curFarthest, then * keep the above steps, as the following */ public int jump(int[] A) { int jumps = 0, curEnd = 0, curFarthest = 0; for (int i = 0; i < A.length - 1; i++) { curFarthest = Math.max(curFarthest, i + A[i]); if (i == curEnd) { jumps++; curEnd = curFarthest; } } return jumps; }
i~furthest_pre
中,区域中的点中能到达的最大位置)所能到达的最大位置(furthest_cur
),当前位置的上一个位置(也是区域)所能到达的最大位置(furthest_pre
),还有就是所走的步数。 furthest_cur
是还没有step++的时候,具体结合代码,也就是是一个预判能走到的但还没走的状态。 furthest_pre
)之间构成了一块区域,然后我们开始一格一格走,每走一下刷新一下当前这块区域能到的最大位置(furthest_cur
),如果走到从开始位置走到了furthest_pre
那我们也刷新出了最大的furthest_cur
,如果furthest_cur
比终点大,那恭喜!再跳一不就到终点了!可以开始跳一步咯!然后重复上述的动作,直到到达终点。 furthest_pre
,那肯定能到一步到它前面那块区域的某一位置,实行下一步跳,跳到furthest_cur
。 4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2
代码
public class Solution {
public int jump(int[] A) {
int len=A.length;
if(len==0||A==null){
return 0;
}
int furthest_cur=0;
int furthest_pre=0;
int steps=0;
for(int i=0;i<len;i++){
if(furthest_pre>=len){
return steps;
}
if(i>furthest_pre){
furthest_pre=furthest_cur;
steps++;
}
furthest_cur=Math.max(furthest_cur,A[i]+i);
}
return steps;
}
}
class Solution { public: // 当前能够到达的最远距离还没有到n,必须再走下一步 int jump(int A[], int n) { int curReach=0,maxReach = 0,steps=0; for(int i=0;i<n && i<=maxReach;i++) { if(i>curReach) //steps-1步能够到达的距离,必须再走一步了 { ++steps; curReach = maxReach; } maxReach = max(maxReach,i+A[i]); // step步最远距离 } if(maxReach<n-1) return -1; else return steps; } };
/* 贪心算法可以解决, 关键是三个变量的含义 cur_step_max_point 使用当前的步数可以去的最远位置 next_step_max_point 使用当前的步数,如果再走一步,可以到达的最远位置 step 当前的步数 ------------------- 一个具体的例子,i=1讲得比较详细,后面的基本就是代码流程。 A[7] = {3, 1, 2, 1, 2, 3, 2} 初始状态:此时step=0, 所以最远能去0, 下一步能去的最远位置就是A[0] i = 0: 就是初试状态,step = 0, cur_step_max_point = 0, next_step_max_point = A[i] = 3; i = 1: 此时已经超过了当前步数step=0的的极限了,所以迈出一步,step = 1,同时当前步数可以到的最远点位置 就要更新了,即cur_step_max_point = next_step_max_point = 3;同时next_step_max_point也 可以更新了,即A[i] + i, 此时A[i] + i值为2,还不如i = 0时的next_step_max_point大,所以不更 新,因为去2这个位置当前步数1就满足。 i = 2 此时cur_step_max_point = 3,在当前步数的射程范围内,不用新增步数。但是在i = 2位置,下一步可以 去的最远位置要更新了,因为A[i] + i = 4, 大于之前存的下一步可以到达的最远位置。next_step_max_point = 4; i = 3 也在cur_step_max_point = 3的射程范围内, cur_step_...不更新。此时i=3下一步能到达的最远位置A[3]+1=4, 也不用更新 i = 4 此时i已经超出了step = 1所能到达的最远距离cur_step... = 3。所以step++,step = 2。更新cur_step_...,令 cur_step_max_point = next_step_max_point = 4。同时更新next_step_max_point = A[i] + i = 6; i = 5 此时i又超过了step = 2时的最大位置cur_step_max_point = 4。所以step++,step = 3 cur_step_max_point = next_step_max_point = 6。next_step_max_point = A[i] + i = 8; 这是突然发现cur_step_max_point = 6. 大于等于n。说明当前步数可以到达n点,于是直接return step. */ int jump(int A[], int n) { if (n == 1 || n == 0) return 0; int next_step_max_point = A[0]; //下一步可以到达的最远距离 int cur_step_max_point = 0; //当前步数可以去的最远距离 int step = 0; //去next_step_max_point的累计步数 for(int i = 0; i < n; i++) { if (i > cur_step_max_point) { cur_step_max_point = next_step_max_point; step++; } if (cur_step_max_point >= n) { return step; } next_step_max_point = max(A[i] + i, next_step_max_point); } return step; }
class Solution { public: int jump(int A[], int n) { if(n==1) return 0; if(n==2) return 1; int a[n-1]; a[0] = 1; int i,j; for(i=1;i<=n-2;i++){ if(A[n-2-i]>=i+1) a[i] = 1; else{ a[i] = n; for(j=1;j<=A[n-2-i];j++){ if(1+a[i-j]<a[i]) a[i] = 1+a[i-j]; } } } return a[n-2]; } };
先预处理一遍,把第i个为能走到的最大坐标存起来。
我们从后往前处理,每次找到第一个能够大于等于目标值的坐标,
把找到的坐标更新为下一个目标值,一直找到目标值为起始位置坐标,即为最小步数。
public int jump(int[] A) {
int[] b=new int[A.length];
for (int i = 0; i < A.length; i++) {
b[i]=i+A[i];
}
int ans=0;
int end=A.length-1;
while (true){
for (int j = 0; j < end; j++) {
if(b[j]>=end){
end=b[j]-A[j];
++ans;
break;
}
}
if(end==0){
break;
}
}
return ans;
}
//动态规划 public class Solution { public int jump(int[] A) { int[] dp = new int[A.length + 1]; for (int i = 2; i < dp.length; i++) { dp[i] = Integer.MAX_VALUE; } for (int i = 1; i < A.length; i++) { int index = A[i - 1] + i ; while ( index > i) { if (index < dp.length &&dp[i] + 1 < dp[index]) dp[index] = dp[i] + 1; index--; } } return dp[A.length]; } }
class Solution { public: int jump(int A[], int n) { int *dp = new int[n](); // dp存放都到各点的最小步数 for(int i = 0; i < n; i++) { int maxp = min(i+A[i],n-1); // 从i 出发能走到的最远距离 for (int j = i + 1; j <= maxp; j ++) { if(dp[j] == 0 || dp[j] > dp[i]+1) dp[j] = dp[i] + 1; // 如果位置没被走过,或者可以用更少步数到达,则到达j点的步数为dp[i]+1 } } int res = dp[n-1]; delete [] dp; dp = nullptr; return res; } };
/* 用一个标号数组存储每个点到终点的最短距离,初始设置终点的dis为0; 从后往前更新每个点的最短距离即可 */ class Solution { public: int jump(int A[], int n) { if(n==0)return 0; int maxnum = 0xffffff; int dis[10000]; for (int i = 0; i < sizeof(dis) / sizeof(dis[0]); i++)dis[i] = maxnum; dis[n-1]=0; for(int i=n-2;i>=0;i--){ if(A[i]+i>=n-1)dis[i]=1; else for(int j=i;j<=A[i]+i;j++)if(dis[i]>dis[j]+1)dis[i]=dis[j]+1; } if(dis[0]==maxnum)return -1; return dis[0]; } };
public class Solution { public int jump(int[] A) { if(A.length==0){ return 0; } int furstep = 0,furpre = 0,step = 0; for(int i = 0;i<A.length;i++){ if(furpre>=A.length-1){ return step; } if(i>furpre){ furpre = furstep; step++; } furstep = Math.max(furstep,A[i] + i); } return step; } }
public class Solution { public int jump(int[] A) { if(A.length==1) return 0; int minstep=1,minindex=A[0],maxindex=minindex; for(int i=1,length=A.length;i<length;i++){ if(i>minindex){ minstep++; minindex=maxindex; } if(A[i]+i>maxindex){ maxindex=A[i]+i; } } return minstep; } }
public int jump(int[] A) { int[] dp = new int[A.length]; // dp存放都到各点的最小步数 for (int i = 0; i < dp.length; i ++) { int maxPosition = Math.min(i + A[i], A.length - 1); // 从i点出发能走的最远距离 for (int j = i + 1; j <= maxPosition; j ++) { if(dp[j] == 0) dp[j] = dp[i] + 1; // 如果位置没被走过,则到达j点的步数为dp[i]+1 } if(dp[A.length - 1] != 0) break; // 当第一次到达终点时,肯定是到达终点最短的步数 } return dp[A.length - 1]; }
public int jump (int[] A) { int[] resultList = new int[A.length + 1]; // 为一维数组 resultList 填充初始值 -1, 值表示到达节点 i 所需的跳数,如果为-1 即为不可达 Arrays.fill(resultList, -1); // 数组的起始位置一定是可达的, 并且所需跳数为 0 resultList[0] = 0; int len = 0; for (int i = 0; i < A.length - 1; i++) { len = A[i]; // 判断可达点 并且 len > 0 if (len > 0 && resultList[i] > -1) { int endIndex = (i + len + 1 > A.length ? A.length : i + len + 1); for (int j = i + 1; j < endIndex; j++ ) { if (resultList[j] == -1) { // 当前节点 i 跳数多1 resultList[j] = resultList[i] + 1; }else { // 当前节点 有其他的节点已经可达, 赋值为两者中的最小值 resultList[j] = Math.min(resultList[i] + 1, resultList[j]); } } } } return resultList[A.length - 1]; }
符合动态规划的条件:
然后就是实现问题了,两个循环,外循环是遍历每个点,内循环是遍历当前点的“势力范围”。
class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return int整型 */ int jump(int *A, int n) { // write code here // 动态规划:设到i的最少步数为f(i),则f(i) = f(i的上一个点) + 1 // dp数组保存到第i个点最少的步数 if (n <= 1) return 0; vector<int> dp(n, 0); for (int i = 0; i < n; ++i) { int maxIdx = min(A[i] + i, n - 1); // 从i走能到的最大位置 for (int j = i + 1; j <= maxIdx; ++j) { if (dp[j] == 0) dp[j] = dp[i] + 1; // 位置没有被走过,保存最小步数 } if (dp[n - 1] != 0) return dp[n - 1]; } return -1; } };