45. 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

This is an extension of Jump Game.

The solution is similar, but we also track the maximum steps of last jump.

对于上述的问题,当我们从最开始的索引节点开始取步数的时候,我们最多能覆盖的范围就是A[0]的值所定的范围,如下图:

假定4是它所能涵盖最远的范围,那么对于1到4这个范围内的值来说,它的最小步数就是1。在没有到达数组的末尾时,我们需要继续考虑步数为2的涵盖范围。在1到4的这个范围内来取,假设中间1所取的数值范围最大,如下图:

这个时候,我们要取的第二步的范围是从4到9。 通过这个步骤推演,我们会发现一个规律。就是对于任何一个步数来说,它当前所能涵盖的最大范围即为所用步数最少的范围。比如前面到4只需要1步。而从当前步数涵盖的范围到下一个范围则需要从当前范围里取涵盖最大的一个。这样依次类推。

所以每次我们只要在某个步数所能涵盖的最大范围内设置它当前的步数,只有超过这个最大范围的时候才对这个步数加一。求下一个步数的时候则求在当前步数的范围内能涵盖的最大值。在具体的实现中,我们需要记录在每一步中它所能涵盖的最大值,每次到遍历到这个值的时候,我们的步数加一。另外,我们在每次的遍历中都要计算当前位置所能涵盖的最大范围以作为下一个步数所能涵盖的范围。

Reference: http://shmilyaw-hotmail-com.iteye.com/blog/2292195

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int reach = 0;
        int lastReach = 0;
        int step = 0;
        for (int i = 0; i <= reach && i < nums.length; i++) {
            //when last jump can not read current i, increase the step by 1
            if (lastReach < i) {
                step++;
                lastReach = reach;
            }
            // Update maximal jump.
            reach = Math.max(reach, i + nums[i]);
        }
        if (reach < nums.length - 1) return 0;
        return step;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s