[leetcode]Jump Game

新博文地址：[leetcode]Jump Game

http://oj.leetcode.com/problems/jump-game/

 

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.

题目思路是容易理解的，数组中每个数字表示最大跳数，问能不能调到最后一个元素，拿第一个数组A来讲：[2,3,1,1,4]第一个元素是2，即最大跳数是2，好吧，我们就跳两步，跳到了1，good，走一步，还是1，好的继续跳，4，最后一个元素，完成。当然，如果第一步我们不跳两步，跳一步的话，是3，还是可以跳到4的。综合来看，只要可以跳过0，就总是可以跳到最后一个元素的。

 

但是第二个数组A就不行，因为3,2,1,0这是个坑。。。（坑爹呢！）你是躲不过0的，因此，我的想法就是看看那数组中有没有这样的坑，如果有，再判断这样的坑能不能跳出去，如果存在跳不过去的这样的坑，返回false，其他情况总是true。

 

下面来看这种坑的特点，首先坑的必要不充分条件是0.。我们假设0的下标是index，则下标为[index - i]的值肯定是 <= index -i，比如，拿第二组测试用例来看，0的下标是3，则下标为2的数字必须 <= 1，下标为1的数字必须<=2，这样才能满足让你只能往坑里跳。。。

 

再看这样的案例：1，0，2，0

我们从后往前遍历，如果发现存在一个坑，那么就不需要再往前遍历了，因为就算前面顺利通过了，也得搁在这儿，如上例2 ，0其实并不是坑，是可以跳过去的，那继续往前遍历，查看前面是否存在“坑”。好了，发现第二个0，继续往前遍历，发现这个坑你是躲不过的，ok，返回false。

如1,0,1,0这个例子的话，只需要判断两个数字就可以了。

    public boolean canJump(int[] A) {
		int zeroIndex = 0;
		boolean canJump = true;
		for(int i =  A.length - 1; i >= 0; --i){
			if(A[i] == 0){
				zeroIndex = i;
				canJump = false;
				break;
			}
		}
		if(canJump == false){
			for(int i = zeroIndex; i >= 0; i--){
				if(A[i] > zeroIndex - i || (A[i] == zeroIndex - i && zeroIndex == A.length - 1)){
					canJump = true;
				}
				if (A[i] == 0 && i != zeroIndex && canJump) {//只有当后面的坑是可以跳过去的时候，才有必要检查前面的元素
					zeroIndex = i;
					canJump = false;
					continue;
				}
			}
		}
		return canJump;
    }