55. 跳跃游戏

[webVueBlog]

55. 跳跃游戏

Description

Difficulty: 中等

Related Topics: 贪心, 数组, 动态规划

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

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

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

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 3 * 10⁴
• 0 <= nums[i] <= 10⁵

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
// 贪心
// var canJump = function(nums) {
//     // 如果只有一个，返回true
//     if (nums.length === 1) return true
//     // 记录所能到达的最大位置
//     var res = nums[0]
//     for (let i = 1; i < nums.length; i++) {
//         // 如果最大位置不能到达当前位置，则跳出
//         if (res < i) break
//         // 如果最大位置超过最后一个位置，则返回true
//         if (res >= nums.length - 1) return true
//         // 计算能到达的最大位置
//         res = res > nums[i] + i ? res : nums[i] + i
//     }
//     return false
// }

// 贪心
var canJump = function(nums) {
    let n = nums.length - 1
    let maxLen = 0
    for (let i = 0; i <= maxLen; i++) {
        maxLen = Math.max(maxLen, nums[i] + i)
        if (maxLen >= n) return true
    }
    return false
}

// 动态规划
// var canJump = function(nums) {
//     let end = nums.length - 1

//     for (let i = nums.length - 2; i >= 0; i--) {
//         if (end - i <= nums[i]) {
//             end = i
//         }
//     }

//     return end === 0
// }