欣迪

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

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

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

說明如下:

只要全部都是正數一定可以到達終點,但是中間會可能會有 0,所以一但遇到 0 ,我就往回看 0 的前幾步能不能順利地跳過它。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  	// 只有一個的時候,自己本身就是終點,所以回 true
    if (nums.length === 1) return true
  	// 開始迴圈
    for(let i = 0; i < nums.length - 1; i++) {
      	// 所有正數都沒問題可以跳過
        if (nums[i] > 0) continue
      	// 遇到 0 了,往前倒回去看看,等不能跳過 0
        if (nums[i] === 0) {
            let goThrowZero = false
            for (let j = i - 1; j >= 0; j--) {
                if (nums[j] + j > i) {
                    goThrowZero = true
                    break
                }
            }
          	// 跳不過就可以中斷迴圈直接給 false 了
            if ( !goThrowZero ) return false
        }
    }
    return true
}

訂閱 IT-Monk

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

作者介紹 - 欣迪

欣迪

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