Java描述 LeetCode，45. Jump Game II 跳跃游戏II

本文主要是介绍Java描述 LeetCode，45. Jump Game II 跳跃游戏II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

1-1：题目

Given an array of non-negative integers nums, 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.

You can assume that you can always reach the last index. 注意，这里已经说了必定能到最后一个位置了

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: 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.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii

1-2：动态规划解法

1-2-1：idea

• 确定状态dp[i]：到达index=i这个位置需要的最小跳跃次数；
• 状态转移方程：假设现在站在index=0的初始位置上，那么它能到达的范围就是1~nums[i]，对于这个范围内的index，从0开始，我只需要一次就可以到达，这个时候轮到i=1，当i=1的时候，就可以出现一种情况，如果nums[1]>1，就会和i=0的时候能到达的范围出现一个重叠范围，这个范围内的index既可以通过i=0一步到位，也可以经过i=1这个位置，两步，所以每次要在重叠的范围要判断一下。
• 确定边界：很容易看出i=0的时候，dp[0] = 0；
• 遍历顺序，从左到右。

1-2-2：代码

public static int jump(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n];
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j - i <= nums[i]; j++) {
            if (j < n) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
    }
    System.out.println(Arrays.toString(dp));
    return dp[n - 1];
}

代码注意点：

• 这边不能一边遍历i一边赋值Integer.MAX_VALUE。因为这个里是通过dp[j]来赋值的，范围内的位置好几个，只有一个赋值Integer.MAX_VALUE，其他几个还是0，取最小值当然会用0，而不是真实的步数，这个尝试一下就知道了。
• 这里是范围内进行多次赋值的，状态转移方程等式的左边是dp[j]而不是dp[i]。

时间复杂度O(n^2)，空间复杂度O(n)，养成写复杂度的习惯从今天开始。

1-3：贪心算法解法1

还记得之前跳跃游戏1里面吗？在上一篇blog里，我尝试把重叠的部分跳过，最终失败了，但是这里又用上了这种思想了，并且成功解决了这道问题，之前的问题，在于计算重叠的时候太急切，以至于跳过了一些中间部分的大哥，具体参考：Java描述 LeetCode，55. Jump Game 跳跃游戏1-4-2，可能这需要几分钟。不想看可以跳过，直接看下面的idea。

1-3-2：idea

贪心贪心，我这里怎么贪呢？从index=0的时候，他就可以有这样一个范围可以到达：[1:nums[i]]，那么我怎么选择下一步的位置呢？总的次数最少，分解下，每一次都要走的更远，所以只要在[1:nums[i]]中选出第二次能到达跳跃更远的那个作为第一次跳跃的落脚点就可以了。以此类推，这么一想这中间确实省掉了一些的路。虽然如此并没有做到完美，会导致一些重复遍历，还是好一些了。

1-3-3：代码

 public static int jump(int[] nums) {
    public static int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int i = 0; // i代表每次落的位置
        int next = 0; // next代表下一个位置
        int count = 0;
        while (i < n) {
            // 如果能凭借着自己就可以到达最后一个index，就不需要继续往下跳了
            if (i + nums[i] >= n - 1) {
                count++;
                return count;
            }

            // 开始寻找下一个跳跃的位置
            int j = i + 1;
            //对i位置能走到的位置，看下一个位置最多能在哪
            int maxInstance = Integer.MIN_VALUE;
            while (j < n && j - i <= nums[i]) {
                if (j + nums[j] >= maxInstance) {
                    maxInstance = j + nums[j];
                    next = j;
                }
                j++;
            }
            i = next;// 跳跃一次
            count++;
//            if (i >= n - 1) {
//                return count;
//            }
        }
        return -1;
    }
 }

这是我自己写的代码，自己的思路。但是这个代码要写对不是很容易。首先他的边界情况有几点要注意。

• 什么时候才要寻找下一个落脚点？
  • 如果在一个位置上，我自己到达的最远距离里面包括了终点位置，自然就不用再继续跳了。这个要放在while循环的开头，
  • 如果在一个位置上，我自己的范围到不了终点，我需要寻找一个落脚点。

时间复杂度O(n^2)，空间复杂度O(1)

1-4：贪心算法解法2

1-4-1：idea

答案的解法也是差不多的思路，但是不是通过上面确定下一步来做的，它用一个max来确定下一步能到达的范围,end记录当前步能到达的最大范围，一边遍历nums[]数组，一边来确定下一步能到达的最大范围MaxPosition，一旦遍历到了上一步最大的范围end，就进入下一个更大的范围MaxPosition，同时步数要+1，注意最后一步是必定到的。

1-4-2：代码

public static int jump2(int[] nums) {
    int length = nums.length;
    int end = 0;
    int maxPosition = 0;
    int steps = 0;
    for (int i = 0; i < length - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
            end = maxPosition;
            steps++;
        }
    }
    return steps;
}

代码很简单，但是我肯定想不到。哈哈哈，又是秒啊秒啊！
时间复杂度O(n^2)，空间复杂度O(1)

1-5：总结

主要是3种解法，两个贪心一个动态规划，前两种自己写的，还可以，答案的我是想不到，算是积累！加油hhg。原创万岁！

这篇关于Java描述 LeetCode，45. Jump Game II 跳跃游戏II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！