题目描述
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 is2. (Jump1step from index 0 to 1, then3steps to the last index.)
- 思路
求在一个数组中，值为对应的最大可走步数，初始在0位置，最少几步可以到达最后一个位置。
递归等方法写的都超时，后来看别人的题解才知道其他方法。遍历此数组，定义一个变量cur记录当前位置可走的最远位置，还有一个变量last记录上一跳跃到的位置可到达的最远位置。
当当前位置大于之前记录的最远位置时，表示永远走不到此位置则退出；
当当前位置大于last时，表示上次跳跃到的位置刚好跳不到现在的位置，需要跳跃。此时递增步数，更新last值为上个位置（即刚好可以跳到的位置）可以跳到的最远位置。
最后更新当前可走的最远距离cur。
贪心的思想，由于每次跳跃时都是达到当前所能走到的最远位置（再不跳就永远不会到达后面的位置了），所以最后得出的结果是最少的跳跃步数。
public class Solution {
public int jump(int[] A) {
if(A == null || A.length == 0)
return -1;
if(A.length == 1)
return 0;
int cnt = 0; //跳跃步数
int cur = 0; //当前所能跳跃的最远距离
int last = 0; //上一次跳跃点所能到达的最远距离
for(int i=0; i<A.length; i++){
if(i > cur) //不可能跳到当前位置时退出
return -1;
if(i > last){ //不要和下面的语句顺序反了
last = cur;
cnt ++;
}
cur = Math.max(cur, i + A[i]); //记录当前可达的最远距离
}
return cnt;
}
}
