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.)
Idea: I tried to write the code as self-explain as I could. Dynamic programming. The furthest position we can jump to from position i is F[i]=max(F[i-1], i+array[i]). Then we calculate the number of jumps during filling the table.
We scan the array from left to right, if we found the current index is smaller than the position the jumper has "arrived", we just calculate and cache the furthest position "canJumpTo" from position "arrived" or any position before "arrived". For example [5,3,1,1,4], if the jumper arrived at index 2, the furthest position is max(5+0, 3+1)=5. If we found the current index is larger than "arrived", we jump once at the maximum distance. Once we reach the right boundary of the array, we stop the loop.
Time: O(n) Space: O(1)
Code:
public class Solution {
public int jump(int[] A) {
int result=0;
int arrived=0;
int canJumpTo=0;
for(int i=0;i<A.length;i++)
{
if(i>arrived)
{
arrived=canJumpTo;
result++;
}
canJumpTo=Math.max(canJumpTo, i+A[i]);
}
return result;
}
}
No comments:
Post a Comment