[LeetCode] 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: [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.

跳跃游戏。

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给一个非负整数数组，数字代表你在该位置可以跳跃的最大长度（注意：你不一定需要跳这么远），你的起点是在数组的第一个位置。判断你是否能跳跃到数组的最后一个位置。

这题有别的解法但是我这里给出的是贪心的思路。设一个变量 k，记录最远可以到达的 index，初始化 k = 0。遍历数组的时候，一旦发现 i > k 就说明 i 点的坐标是无法达到的，返回 false；更新 k 的方式是 i + nums[i]，表示在 i 位置最远可以跳到什么位置。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > max) {
                return false;
            }
            max = Math.max(max, i + nums[i]);
        }
        return true;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > k) return false;
        k = Math.max(k, i + nums[i]);
    }
    return true;
};