跳跃游戏
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
样例
A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.
解题
更新
public class Solution {
/**
* @param A: A list of integers
* @return: The boolean answer
*/
public boolean canJump(int[] A) {
// wirte your code here
if(A== null || A.length == 0)
return true;
int maxJump = A[0];
if(maxJump == 0 && A.length == 1)
return true;
if(maxJump == 0)
return false;
for(int i=1;i<A.length;i++){
maxJump = Math.max(maxJump - 1,A[i]); // 向前走一步 -1，并更新可走步长
if(maxJump >= A.length - i -1){ // 判断是否能够到达 len -1 位置
return true;
}
if(maxJump <=0)
return false;
}
return true; // false 都能通过
}
}
定义一个布尔数组，对每个位置判断其是否可以走
当数组的第一个位置是0的时候，返回false
初始布尔数组第一个位置是true，这样是为了保证走的连续型，当某个位置是false说明利用前面走的方式不能走到该位置，下面就无法走下去了。返回false
或者说，能到达当前位置的时候，当前位置才可以向前走，能到达当前位置体现在visited[i] = true
public class Solution {
/**
* @param A: A list of integers
* @return: The boolean answer
*/
public boolean canJump(int[] A) {
// wirte your code here
if(A == null || A.length<=1)
return true;
boolean visited[] = new boolean[A.length];
visited[0] = true;
if(A[0] ==0) return false;
for(int i = 0;i<A.length;i++){
if(visited[i] == false)
return false;
int d = A[i];
int jump = 0;
while(jump <=d){
if(jump+i< A.length)
visited[jump+i] = true;
if(jump+i == A.length -1)
return true;
jump++;
}
}
return visited[A.length - 1];
}
}
但是上面的程序在LeetCode无法通过，lintcode只是小样本数据
leetcode 看到不需要定义布尔数组的解法
定义变量maxJump：表示从现在位置能够向后走的最大的步数
显然maxJump受前一个maxJump的影响，前一个maxJump走到现在位置，只需要一步，走到现在 位置是maxJump -1
在 i 位置可以最远向后走的步数是 A[i]
两者的最大值就是 i 位置开始向后走的步数：maxJump = max( maxJump -1,A[i])
当maxJump ==0 的时候说明，不能向后走了，死局。
注意：对最后一步的maxJump可以为0，因为已经走到了最后了，所以for循环只判断的倒数第二个位置
public class Solution {
/**
* @param A: A list of integers
* @return: The boolean answer
*/
public boolean canJump(int[] A) {
// wirte your code here
if(A == null || A.length<=1)
return true;
if(A[0] ==0) return false;
int maxJump = A[0];
for(int i = 1;i<A.length -1;i++){
maxJump = Math.max(maxJump - 1,A[i]);
if(maxJump == 0)
return false;
}
return true;
}
}