[刷题防痴呆] 0055 - 跳跃游戏 (Jump Game)

题目地址

https://leetcode.com/problems/jump-game/description/

题目描述

55. 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: nums = [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: nums = [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.

思路

1. 动态规划, O(N2). 当前层能不能跳到取决于, 前面的每层中, 有可以跳到当前层, 并且前面层高与前面层可跳到的层数相加大于当前层高.
2. 贪心, O(N). 当前层和最大层相比, 如果可以到达, 则最远能到达位置为, 当前层加上当前层能到达的层数和原最大层的最大值.

关键点

• 动态规划的解法.
• can[0] = true.
• can[i] = can[j] && nums[j] + nums[j] >= i. 有一个为true, 即为true.
• 贪心的解法.
• farthest = nums[0].
• 如果 i <= farthest 更新farthest = Math.max(farthest, nums[i] + i).
• 最后看 farthest >= nums.length - 1.

代码

• 语言支持：Java

// 方法1, dynamic programming
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }
}

// 方法2, Greedy
class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (max >= i) {
                max = Math.max(max, nums[i] + i);
            }
        }
        
        return max >= nums.length - 1;
    }
}