跳跃游戏
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
样例
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; } }