LeetCode.055.Jump Game 跳跃游戏

题目描述

55 Jump Game
https://leetcode-cn.com/problems/jump-game/

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.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

---

相似题目

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

---

解题过程

跳跃游戏是一个非常灵活的题目，贪心、动态规划、DFS、BFS 都可以做，但最好的解法是贪心。
除了 O(n) 的贪心算法外，BFS 和 DFS 都是模拟跳跃过程，时间复杂度 O(n^2)，比较好理解但遇到最后2个超大的测试用例会超时。

贪心

贪心算法， max 记录当前能跳到的最远位置，从前往后遍历，
如果 i > max ，表示连当前位置也到达不了，则肯定到不了末尾，直接返回 false 结束。
如果 max 已到达末尾，返回 true 结束

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

private static class SolutionV2020Greedy {
    public boolean canJump(int[] nums) {
        if (null == nums || nums.length < 2) {
            return true;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > max) {
                return false;
            }
            max = Math.max(max, i + nums[i]);
            if (max >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

DFS超时

深度优先搜索（回溯），超时，能通过 74/75 个测试用例

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

// 深度优先搜索（回溯），超时，能通过 74/75 个测试用例
private static class SolutionV2020DFS {
    Set<Integer> visited;
    public boolean canJump(int[] nums) {
        if (null == nums || nums.length < 2) {
            return true;
        }
        // 已访问过的，无法跳到末尾的结点
        visited = new HashSet<>(nums.length);
        return dfs(nums, 0);
    }

    // 深度优先搜索
    private boolean dfs(int[] nums, int start) {
        if (visited.contains(start)) {
            return false;
        }
        // 优化，i 从 nums[start] 往前 遍历，也就是从跳的最远的位置开始dfs
        for (int i = nums[start]; i >= 1; i--) {
            if (start + i >= nums.length - 1) {
                return true;
            }
            if (!visited.contains(start + i)) {
                if(dfs(nums, start + i)) {
                    return true;
                }
                visited.add(start + i);
            }
        }
        return false;
    }
}

BFS超时

广度优先搜索，层次遍历，超时，能通过 70/75 个用例

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

// 广度优先搜索，层次遍历，超时，能通过 70/75 个用例
private static class SolutionV2020BFS {
    public boolean canJump(int[] nums) {
        if (null == nums || nums.length < 2) {
            return true;
        }
        Set<Integer> visited = new HashSet<>(nums.length);
        // 队列 queue 存放下次可跳跃到的结点的下标，类似层次遍历
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            visited.add(current);
            // 从当前点可以跳到哪些点
            for (int i = 1; i <= nums[current]; i++) {
                int next = current + i;
                // 若能直接跳到末尾则结束
                if (next >= nums.length - 1) {
                    return true;
                }
                if (!visited.contains(next)) {
                    queue.offer(next);
                }
            }
        }
        return false;
    }
}

---

GitHub代码

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

---