反向查找
class Solution {
public int jump(int[] nums) {
int step=0;//跳跃次数
int right=nums.length-1;
while(right>0){
for(int i=0;i<right;i++){
if(i+nums[i]>=right){ //选取能跳到最右侧的最远的一个位置
step++; //跳跃步数+1
right=i;// 更新right的位置
break;
}
}
}
return step;
}
}
正向查找
class Solution {
public int jump(int[] nums) {
int step=0;//记录步数
int maxposition=0;//最远能到达的位置，2,3,1,2
int end=0;
for(int i=0;i<nums.length-1;i++){
//i=0时，可到达位置1,2
maxposition=Math.max(maxposition,i+nums[i]);//能到达的最远的位置
if(i==end){ //到达了一个end算是一次跳跃
end=maxposition;
step++;
}
}
return step;
}
}
