LeetCode.045.Jump Game II 跳跃游戏2

题目描述

45 Jump Game II
https://leetcode-cn.com/problems/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.

Example:

Input: [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.

Note: You can assume that you can always reach the last index.

---

相似题目

LeetCode.055.Jump Game 跳跃游戏
LeetCode.045.Jump Game II 跳跃游戏2

---

解题过程

贪心

贪心的思路和 55 题一样，O(n) 从前往后遍历，用一个变量 farthest 记录当前能跳到的最远下标， farthest 到达末尾时结束。
同时，用变量 steps 记录步数
最关键的问题是，如何更新步数 steps 呢？
用变量 nextEnd 记录下一步能跳到的最远下标，只要在 nextEnd 范围内都可一步完成，所以
i < nextEnd 时，在上一步能跳到的范围内，所以步数不增加
i >= nextEnd 时，到达上一步能跳到的最远位置，步数 steps 加 1，同时更新下一步的最远距离为当前能跳到的最远距离 farthest

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

private static class SolutionV2020Greedy {
    public int jump(int[] nums) {
        if (null == nums || nums.length < 2) {
            return 0;
        }
        int steps = 0;
        int nextEnd = 0; // 下一步能跳到的最远下标，只要在 nextEnd 范围内都可一步完成
        int farthest = 0; // 当前能跳到的最远下标
        for (int i = 0; i < nums.length; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            // 可以跳到末尾，直接结束
            if (farthest >= nums.length - 1) {
                return steps + 1;
            }
            // i大于等于上一步的最远距离时，更新下一步的最远距离为当前能跳到的最远距离，步数step加1
            if (i >= nextEnd) {
                nextEnd = farthest;
                steps++;
            }
        }
        return steps;
    }
}

BFS超时

超时，84 / 92 个通过测试用例
时间复杂度 O(n^2)，空间复杂度 O(n)

// 广度优先搜索，超时，84 / 92 个通过测试用例
private static class SolutionV2020BFS {
    public int jump(int[] nums) {
        if (null == nums || nums.length < 2) {
            return 0;
        }
        // 标记已访问过的结点
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        // 跳跃的步数
        int steps = 1;
        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            for (int i = 0; i < levelCount; i++) {
                Integer start = queue.poll();
                visited.add(start);
                for (int j = 1; j <= nums[start]; j++) {
                    int jumpTo = start + j;
                    if (jumpTo >= nums.length - 1) {
                        return steps;
                    }
                    if (!visited.contains(jumpTo)) {
                        queue.offer(jumpTo);
                    }
                }
            }
            steps++;
        }
        return steps;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_045_JumpGame2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_045_JumpGame2.java

---