给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
public boolean canJump(int[] A) {// write your code hereif (A[0] == 0 && A.length != 1)return false;boolean canJump = false;int zeroPos = -1;for (int i = 0; i < A.length; i++) {if (A[i + A[i]] == 0)zeroPos = i + A[i];if (A[i] == 0 && i == A.length - 1)return true;if (A[i] + i >= A.length -1 )return true;if (A[i+A[i]] == 0 && i+A[i] == A.length -1)return true;else if (A[i + A[i]] == 0) {if (zeroPos == i)return false;zeroPos = i+A[i];continue;}i = A[i] + i - 1;}return canJump;
}
dalao思路：
public boolean canJump2(int[] A) {// write your code hereif (A == null) return false;int n = A.length;if (n < 2) return true;int curMax = 0;for (int i = 0; i < n; i++) {if (i <= curMax) curMax = Math.max(i + A[i], curMax); //max/min 贪心的关键}return curMax >= n - 1;
}
dalao思路:只是讨论是否能达到终点的话 ，在小于当前最大点遍历的每一步都讨论是否能得到更大的一步，最终遍历完后如果大于长度，那就可以到达
summary:贪心策略，需要获得全局的最优结果，但遍历得每一步只能得到局部的结局/局部最优结果，同时在处理局部的时候 还要注意会不会出现更好的结果，有则更新
之前一直困扰于遍历到i的时候就直接跳到a[a[i]]的结果，忽视了过程中可能会出现更好的结果