刷題32-跳躍遊戲

原題連結

題目描述

給出一個非負整數陣列，你最初在陣列第一個元素的位置。
陣列中的元素代表你在這個位置可以跳躍的最大長度。
判斷你是否能到達陣列最後一個元素的位置。
例如
A =[2,3,1,1,4], 返回 true.
A =[3,2,1,0,4], 返回 false.

範例

輸入：
[2,3,1,1,4]
輸出：
true

輸入：
[3,2,1,0,4]
輸出：
false

參考解法

// 從後往前遍歷
public boolean canJump (int[] A) {
	// 排除特例
	if(A==null || A.length<1)
		return false;
	if(A.length==1)
		return true;
	
	int n = A.length;
	// 這個變數定義很重要，指的是能達到終點的下標的值
	int last = n-1;
	// 從後往前遍歷
	for (int i = n-2; i >= 0; i--) {
		if(i+A[i]>=last) {
			// 能達到，則迭代一個值
			last = i;
		}
	}
	return last==0;
}