JumpGame

//Jump Game Total Accepted: 50023 Total Submissions: 185682 My Submissions Question Solution 
//Given an array of non-negative integers, you are initially positioned at the first index of the array.
//
//Each element in the array represents your maximum jump length at that position.
//
//Determine if you are able to reach the last index.
//
//For example:
//A = [2,3,1,1,4], return true.
//
//A = [3,2,1,0,4], return false.
import java.util.ArrayList;


public class JumpGame {


public static void main(String[] args) {
// TODO Auto-generated method stub


}


public boolean canJump(int[] nums) {


ArrayList<Integer> zeroindex=new ArrayList<>();
//只要管最后一个前面的 length-1的数
for(int i=0;i<nums.length-1;i++){
if(nums[i]==0){
zeroindex.add(i);
}
}

for(int i=0;i<zeroindex.size();i++){
int j;
for(j=zeroindex.get(i)-1;j>=0;j--){
if(nums[j]>zeroindex.get(i)-j)
break;
}
if(j<0)
return false;
}
return true;
}


}


//Given an array of non-negative integers, you are initially positioned at the first index of the array.
//
//Each element in the array represents your maximum jump length at that position.
//
//Your goal is to reach the last index in the minimum number of jumps.
//
//For example:
//Given array A = [2,3,1,1,4]
//
//The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
public class JumpGameII {


public static void main(String[] args) {
// TODO Auto-generated method stub


}


public int jump(int[] nums) {
if(nums==null||nums.length==0||nums.length==1)
return 0;
int jump=0;
int laststep=0;
for(int i=0;i<nums.length;i++){
nums[i]=nums[i]+i;
if(nums[i]>=nums.length-1){
jump++;
laststep=i;
//找到第一个就可以停止了
break;
}
}
while(laststep>0){
for(int j=0;j<laststep;j++){
if(nums[j]>=laststep){
jump++;
laststep=j;
break;
}

}
}
return jump;
}


}