題目描述

給定一個非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標(biāo) 。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達(dá)最后一個下標(biāo)。

示例1

• 輸入：nums = [2,3,1,1,4]
• 輸出：true
• 解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個下標(biāo)。

示例2

• 輸入：nums = [3,2,1,0,4]
• 輸出：false
• 解釋：無論怎樣，總會到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個下標(biāo)。

提示

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

解法

思路一：貪心算法（盡可能去最遠(yuǎn)的位置）

如果能夠到達(dá)最遠(yuǎn)的地方，那一定能到到最遠(yuǎn)前面的任意地方。

• 遍歷數(shù)組，把每個位置都作為起始點(diǎn)，設(shè)置最遠(yuǎn)能夠到達(dá)位置為0
• 更新最遠(yuǎn)能夠到達(dá)的位置，能夠到達(dá)的最遠(yuǎn)的位置為當(dāng)前位置索引+當(dāng)前元素的值
• 如果每個位置都能夠到達(dá)，則可以成功，否則失敗

AC代碼

var canJump = function(nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        // 判斷能否到達(dá)i位置，不能則也不能夠到達(dá)終點(diǎn)，終止，直接返回結(jié)果false
        if (i > k) return false;
        // 更新能夠到達(dá)的最遠(yuǎn)位置
        k =  Math.max(k, nums[i] + i);
        // 如果能夠到達(dá)的最遠(yuǎn)位置超過終點(diǎn)，則提前跳出循環(huán)
        if (k > nums.length) {
            return true
        }
    }
    return true;
};

思路二：只要最后一步前所有的元素都大于0,就可以到達(dá)

從后往前遍歷,只要0前面的元素存在nums[i] > (0的索引 - i) 就能夠到達(dá)

AC代碼

var canJump = function(nums) {
    // 如果nums只有一個元素，則一定可以到達(dá)
    if (nums.length === 1) return true;
    let cover = 0;
    for (let i = 0; i < nums.length; i++) {
        cover = Math.max(cover, i + nums[i])
        if(cover == i && nums[i] == 0 && i !== nums.length - 1) {
            return false;
        }
        if (cover >= nums.length - 1) return true;
    }
};

總結(jié)

主要是能夠理解，最遠(yuǎn)能到達(dá)某個位置，就一定能到達(dá)它前面的任何位置。