[LeetCode] 45. Jump Game II (JS)

內容目錄 隱藏

題目

求從陣列起始位置到達末尾所需的最小跳躍次數。

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n - 1].

解題思路

nums = [2,3,1,1,4]

jumps1 第一格的最大長度為 2, 代表最遠可以跳到索引 2
jumps2 第二格的最大長度為 3, 代表最遠可以跳到索引 4 (陣列末尾)
jumpe3 第三格的最大長度為 1, 代表最遠可以跳到索引 3
...
判斷到這就結束了, 因為第二步的時候就能跳到陣列末尾, 因此再多跳幾格下去都不會是題目要求的最小步數, 因此答案為 2

首先需要一個變數 jumps 來紀錄總共跳躍的次數
再來需要一個變數 current_end 紀錄當前跳躍範圍內能到達的最遠位置
最後需要一個變數 farthest 來存能到達的最遠位置，farthest 就會是farthest 和目前索引能跳最遠距離取最大值 farthest = Math.max(farthest, i + nums[i])。
當遍歷到 current_end 時(i == current_end)代表需要再跳一次，然後更新 current_end 為 farthest

完整程式碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let jumps = 0 // 總共跳躍的次數
    let current_end = 0 // 當前跳躍範圍內能到達的最遠位置
    let farthest = 0 // 能到達的最遠位置

    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i])

        // 當遍歷到 current_end 時代表需要再跳一次
        if (i == current_end) {
            jumps++
            current_end = farthest
        }
    }

    return jumps
};

瀏覽量: 16

題目

解題思路

完整程式碼

相關文章