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.
这道题是比较相对于jump2是比较简单的，只需要求出是否能都达到终点即可
第一次记录了最长距离maxlen，如果最远距离和当前位置一致。那么就不可到达终点，如果最远距离超过了长度－1，那么直接返回true，虽然ac，但是结果并不是很好。
public class Solution { public boolean canJump(int[] nums) { int maxlen = nums[0]; int len = nums.length; if ( len < 2 ) return true; if( maxlen == 0) return false; for( int i = 1;i<len;i++){ maxlen = (i+nums[i])>maxlen?(i+nums[i]):maxlen; if( i == maxlen ) return false; if( len-1 <= maxlen ) return true; } return len<=maxlen-1?true:false; } }
然后稍微修改了一下代码，速度有所提升。(还是很奇怪的是，同样的代码，每次提交的时候运行时间有可能不一致。)
public class Solution { public boolean canJump(int[] nums) { int maxlen = nums[0]; int len = nums.length; if ( len < 2 ) return true; if( maxlen == 0) return false; if( maxlen >= len-1) return true; for( int i = 1;i<len;i++){ nowlen = i+nums[i]; if( nowlen > maxlen ){ maxlen = nowlen; if( len-1 <= maxlen ) return true; } else if( i == maxlen ) return false; } return true; } }
看了官方的解答方案之后，发现还有一种更简便的写法，就是从后往前便利。虽然时间复杂度和空间复杂度没有变化，但是代码量少了不少，但是很奇怪的是，就算是官方答案，偶尔也会ac不了，出现超时，还有就是这两种答案的时间是一样的。
public class Solution { public boolean canJump(int[] nums) { int lastPos = nums.length - 1; for (int i = nums.length - 1; i >= 0; i--) { if (i + nums[i] >= lastPos) { lastPos = i; } } return lastPos == 0; } }
leetcode 55 Jump Game ----- java
原文：http://www.cnblogs.com/xiaoba1203/p/5750990.html