欣迪

出處: https://leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

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

可以先參考比較點簡單的上一題: 解題 52. Jump Game

這題要找到最靠到達終點所需要的最少步數:

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
  	// 如果 nums 不到一格,或是只有一格,回傳 0 步
    if (nums.length <= 1) return 0
  	// 最後一步的 index
    const endIdx = nums.length - 1
    // 起始的 index
    let current = 0
    // 因為已經排除 0 步的情形,所以這邊的至少需要 1 步
    let step = 1
    //  未到終點前,必須一直往前找最大可前進的步數
    while (current + nums[current] < endIdx) {
      	// 利用目前能走的步數,找出最可以走多步的可能性
        let max = null
        let maxIdx = null
        for (let i = current + 1; i < current + nums[current] + 1; i++) {
            let distance = current + nums[i] + i
            if (distance > max) {
                max = distance
                maxIdx = i
            }
        }
      	// 完成後移動到最佳位置,並把移動次數加 1
        current = maxIdx
        step++
    }
    return step
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。