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
.
public class Solution { public boolean canJump(int[] A) { // Note: The array may have number 0. // If the array doesn't have 0, return true; // If the array has 0, you should check if the number before 0 can privide with steps to pass 0 // We don't need consider the last number even though it is 0 // If the first number is 0, return false. int n = A.length; if (n == 0) return false; if (n == 1) return true; // If the first number is 0, return false. if (A[0] == 0) return false; // All of the zero numbers index (Note: don't consider the last element) List<Integer> zeroIndex = new LinkedList<>(); for (int i = 1; i < n-1; i++) if (A[i] == 0) zeroIndex.add(i); // If no 0 number if (zeroIndex.isEmpty()) return true; boolean pass; // If there is any qualified element, pass = true. for (int id : zeroIndex) { pass = false; for (int i = 0; i < id; i++) // i + A[i] represents the position that skipped to. if (i+A[i] > id) pass = true; // If there isn't any qualified elements before 0, return false. if (!pass) return false; } return true; } }
No comments:
Post a Comment