[LeetCode] 55. Jump Game (JS)

5 個月前

內容目錄 隱藏

題目

給定一個整數陣列 nums ，陣列中的每個元素代表在該位置的最大跳躍長度。

如果可以到達最後一個索引傳回 true ，否則傳回 false 。

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.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

解題思路

這題的標籤是動態規劃/貪婪演算法。

第一眼看到題目和範例的時候我以為每個元素都只跳最大步數，還在想怎麼會這麼簡單：

var canJump = function(nums) {
    let index = 0
    const maxIndex = nums.length - 1

    while (index < maxIndex) {
        const steps = nums[index]
        if (steps === 0) {
            return false
        }
        index += steps
    }

    return true
};

試了幾個例子之後才發現不一定都跳最大步數，所以需要改一下上面的程式碼。

注意：

不是每個索引都要跳最大長度

不是一定要剛好跳到最後一個索引的位置，可以超過

完整程式碼

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let farthest = 0 // 當前可以到達的最遠位置
    let index = 0 // 當前索引
    const maxIndex = nums.length - 1 // 最後一個索引

    while (index <= farthest) {
        farthest = Math.max(farthest, index + nums[index])
        if (farthest >= maxIndex) {
            return true
        }
        index++
    }

    return false // 無法到達最後一個索引，返回 false
};

之所以是 index++ 而不是 index += nums[index] 是為了逐步檢查每個索引位置，避免直接跳躍到下一個位置錯過了最佳路徑。