[LeetCode]Jump Game

很简单题，一种解法是类似BFS，
维护一个right bound 每次扫的话更新right bound，如果发现超过了len - 1，则说明可以到，如果当前位置超过了right bound则说明到不了（没有办法到更远了，从头开始到的最远的位置就是right bound）。

代码如下：

	public class Solution {
	public boolean canJump(int[] A) {
	if (A == null)
	return false;
	int len = A.length;
	if (len == 0)
	return false;
	int rightBound = A[0];
	int i = 0;
	while (i <= rightBound) {
	if (i + A[i] > rightBound)
	rightBound = i + A[i];
	if (rightBound >= len - 1)
	return true;
	i++;
	}
	return false;
	}
	}

view raw jump game sol 1.java hosted with ❤ by GitHub

值得注意的是，在while循环当中，我们不需要check是否到了len - 1，即是否越界。原因在于，除去len长度为1的情况会return true，长度大于1的时候，分两种情况：

• 如果没有办法跳到len - 1，的话会直接break，更不会越界
• 如果能跳到len - 1，那么最晚在倒数第二个位置即len - 2就会发现right bound会大于等于len - 1，所以会break也不会越界

第二种方法，类似DP的思路，不维护array，从末尾向头部遍历，由于能不能跳过只取决于能否跨过由0造成的gap（gap可能包含非0元素），所以维护一个gap，如果当前A[i] >= gap,则gap reset成1，res设为true（说明从i可以跳到末尾），否则，gap++，res设为false（从i跳不到末尾），所以就看在0的位置res是true还是false。另一方面，gap表示的是从i开始到一个能跳到end的位置的最短距离，如果从i能跳到那个位置，就可以跳到end，否则，无法跳到end，代码如下：

	public class Solution {
	public boolean canJump(int[] A) {
	if (A == null)
	return false;
	int len = A.length;
	if (len == 0)
	return false;
	if (len == 1)
	return true;
	int gap = 1;
	boolean res = false;
	for (int i = len - 2; i >= 0; i--) {
	if (A[i] >= gap) {
	gap = 1;
	res = true;
	} else {
	gap++;
	res = false;
	}
	}
	return res;
	}
	}

view raw jump game sol 2.java hosted with ❤ by GitHub