JAVA求解跳跃游戏（Jump Game）

JAVA求解跳跃游戏（Jump Game）

原题链接：https://leetcode.com/problems/jump-game/description/ JUMP GAME
原题链接：https://leetcode.com/problems/jump-game-ii/description/ JUMP GAMEII

这两个是一类问题

问题描述：给定一个非负整数数组，给定的初始化位置在数组的起始位置。数组中的每个元素代表着你能都在此位置跳跃的最大的距离。你的目标是用最少的跳跃数达到数组的末尾。

假设条件：你可以假设你总是有可能到达数组的末尾。

给出的一个举例为
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.)

算法设计—1

public static int canJump (int[] nums) {
        if (nums.length == 1) {//当数组中只有一个元素时，返回0。
            return 0;
        }

        int step = 0;//在开始之前初始化 step = 0 
        int position = 0;// 从当前的step开始的位置初始化为0
        int reachable = 0;// 从当前的step可以到达的最远的位置
        int furthest = 0;// 下一步可以达到的最远的位置, 在下一轮次循环中，它是新的reachable的值


        while (position <= reachable) {// 一次循环代表一步, 从step==0开始
            furthest = Math.max(furthest, position + nums[position]);// 求出一个最大值
            if (furthest >= nums.length - 1) {//能够到达数组的结束（末尾）
                return step + 1; // step+1
            }
            if (position == reachable) {//本次跳跃结束
                if (furthest <= reachable) {//不能到达
                    return -1; //返回 -1
                } else {// 添加本次的step，更新 reachable的值
                    ++step;
                    reachable = furthest;
                }
            }
            ++position;//继续
        }
        return -1;
    }

算法设计—2

public static int canJump(int[] nums) {
// If nums.length < 2, means that we do not
// need to move at all.
if (nums == null || nums.length < 2) {
return 0;
}

    // First set up current region, which is
    // from 0 to nums[0].
    int l = 0;
    int r = nums[0];
    // Since the length of nums is greater than
    // 1, we need at least 1 step.
    int step = 1;

    // We go through all elements in the region.
    while (l <= r) {

        // If the right of current region is greater
        // than nums.length - 1, that means we are done.
        if (r >= nums.length - 1) {
            return step;
        }

        // We should know how far can we reach in current
        // region.
        int max = Integer.MIN_VALUE;
        for (; l <= r; l++) {
            max = Math.max(max, l + nums[l]);
        }

        // If we can reach far more in this round, we update
        // the boundary of current region, and also add a step.
        if (max > r) {
            l = r;
            r = max;
            step++;
        }
    }

    // We can not finish the job.
    return -1;
}

可以自己编写一个main方法进行测试。

（完）