[LeetCode]Jump Game II

类似Jump Game 的第一种解法，我们采用类似BFS的解法，还是BFS找最短路径的问题。
首先如果A的len为1的话。我们直接返回0。之后我们维护step来表示BFS的深度，初始化为1，同时维护一个right bound，初始化为A[0]，i初始化为0。进入循环，每次check一下right bound是否大于等于len - 1，如果是的话，return step。否则从i到right bound看最远能到的值，更新right bound，如果发现新的rightbound 和老的right bound一样，说明我们没法前进了，break 返回 -1。如果不是的话，更新right bound，step++，重复之前的步骤。

代码如下：

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

view raw jump game II.java hosted with ❤ by GitHub