Leetcode Jump Game I & II (Java)
Jump Game I
Given an array of non-negative integers, you are initially positioned at the first index of the array.
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.
Java Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class Solution { public boolean canJump(int[] nums) { int size = nums.length; if (size == 0) return true; int curMax = nums[0]; for(int i = 1; i < size; i++) { if( i <= curMax) { curMax = Math.max(curMax, nums[i] + i); }else{ return false; } } return true; } } |
Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.
Analysis
We keep three pointers,
i: the index of current visiting item,
maxSoFar: the max index that can be reached since last change of step
curMax: the max index that can be reached from the index that is smaller than maxSoFar.
For each i <= maxSoFar, we update curMax = max(curMax, i + num[i]),
Then we update maxSoFar by curMax and increase cnt. Since it is assumed that the array can always be reachable, curMax will always be larger than maxSoFar.
Once maxSoFar > nums.length, return cnt.
Java Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class Solution { public int jump(int[] nums) { if(nums.length <= 1 ) return 0; int maxSoFar = nums[0]; int cnt = 1; int i = 1; int curMax = 0; while(i < nums.length) { if(maxSoFar >= nums.length - 1) { return cnt; } while(i <= maxSoFar) { curMax = Math.max(curMax, i + nums[i]); i++; } // if(curMax > maxSoFar) { // no needed as it is garanteed to be reachable cnt++; maxSoFar = curMax; // } } return cnt; } } |
