45 跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

题解

给两种贪心解法和动态规划的解法

题解1

首先是贪心算法的on2 版本，基础思路是看当前所在步能跳出去的步数中，选下一步能跳最远的那个格子。举例来说： [2,3,1,1,4]。第一步能够跳到3和1的位置。这时候要决定跳到哪个位置是最优的。很显然3是最优的，因为3的位置能最远跳到4的位置，而1的位置只能够跳到下一个1的位置。

javascript

var jump = function (nums) {
    if (nums.length === 1) {
        return 0
    }
    let count = 0
    let startIndex = 0
    while (true) {
        //先走一步
        count++
        //当前步能走到的最远处
        const currentMax = nums[startIndex] + startIndex
        let nextMax = currentMax
        let nextMaxIndex = startIndex
        //在最远的可选范围之内，试探下一次可以选的位置
        for (let i = startIndex; i <= currentMax; i++) {
            if (i < nums.length) {
                if (nextMax < nums[i] + i) {
                    nextMax = nums[i] + i
                    nextMaxIndex = i
                }
            }
        }
        //如果当前已经可以到达最远处
        if (currentMax >= nums.length - 1) {
            break;
        }
        //替换成下一次的位置继续
        startIndex = nextMaxIndex
    }

    return count
}

题解2

动态规划的方法。这题动态规划的方法也是非常容易想到的。

按照动态规划的三部曲： 1.定义dp数组和下标的含义: 我们设dp[i]为以i为结尾的最小跳跃次数。 2.定义递推公式: dp[i] = min(dp[j]) + 1,当且仅当 nums[j] + j >= i, 且 0<=j<i 3.递推公式的初始值和递归的顺序dp[0] = 0 (默认站在第0个位置), dp[1] = 1 （因为都可以跳，所以只要跳一次就可以），递推顺序是从前往后

javascript

var jumpByDp = function(nums) {
    const dp = Array(nums.length).fill(999999)
    dp[0] = 0
    dp[1] = 1
    for(let i=2;i<nums.length;i++) {
        for(let j=0;j<i;j++) {
            if(nums[j] + j >= i) {
                if(dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1
                }
            }
        }
    }
    return dp[nums.length - 1]
}

题解3

贪心算法的继续改良。我们可以拿一次遍历就可以做到判断出跳几次的问题，那是怎么做到的。

打个比方，有一些接驳车，这些接驳车能够一格格的换，也能够按照当前的数值多开几站。同时你可以在每一站都能换接驳车。比如2,3,1,1,4 从位置0开出的车能在3停，也能在1停，但是最远只能到1。这时候必须要换接驳车，你可以换从3开过来的接驳车，他最远能够开到4的位置。

那我们就可以这样想，假设我们现在是2的位置，我们一直坐在车上，当到3时，我们观察这个车能到4的位置，我们心里就知道这是目前能够开到最远的地方，然后我们不换接驳车，到1的位置时，我们又看到这时候最远只能到下一个1，又因为这个接驳车到终点了，我们必须要跳（换个车），我们肯定要选能够跑到最远的车（也就是从3号开出来的），此时我们最远能够到的最远位置就变了。

下面就是这个算法的核心

javascript

let currentIndexMax = 0
let nextIndexMax = 0

for(let i=0;i<nums.length;i++) {
    const currentMax = nums[i] + i

    //还没到站的情况下，偷偷记录下当前所有班次能到的最大的值
    if(i<=currentIndexMax) {
        if(currentMax > nextIndexMax) {
            nextIndexMax = currentMax
        }
    }

    //到终点了,必须换车了
    if(i === currentIndexMax) {
        //立马切换成我们刚刚记录下的最远的车次
        currentIndexMax = nextIndexMax
    }
}

那么再考虑边界条件后吗，可以写出如下代码：

javascript

var jumpByTanxin2 = function (nums) {
    if (nums.length === 1) {
        return 0
    }
    let count = 1
    let startMax = nums[0]
    let nextMax = nums[0]
    //这里只到第n-2个位置
    for (let i = 1; i < nums.length - 1; i++) {
        //当前i能够达到的最远位置
        const currentMax = nums[i] + i
        //如果还在范围内，那么更新下一次最大的值来备用
        if (i <= startMax) {
            if (currentMax > nextMax) {
                nextMax = currentMax
            }
        }
        //一旦到达最大位置，这时候必须跳
        if (i === startMax) {
            count++;
            startMax = nextMax
        }
    }
    return count
}

45 跳跃游戏II ​

题解 ​

题解1 ​

题解2 ​

题解3 ​

45 跳跃游戏II

题解

题解1

题解2

题解3