贪心算法：跳跃游戏 🍈

今日份的刷题训练，依旧是在leetcode当中做题，继续贪心算法的练习吧。

跳跃游戏

题目地址： https://leetcode-cn.com/problems/jump-game/solution/

题目描述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例

示例 1：

输入：nums = [2,3,1,1,4]
输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false

解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

在本题当中，如果按照正常思路是一步步遍历走下去，如果不成功就返回，再走另一条路线。（这种方式当然可以，不过是暴力求解，中间还会用到递归）

所以面对这类题目，需要先理清逻辑，找到思路。

在本题中，可以先逆向思考，因为要到达终点，所以可以看看从终点往前，只需要找到可以起跳点的index + 步数大于等于终点位置即可。

当然寻找可以起跳点也需要遍历，设置一个最大距离maxDis，如果当前数组元素的index小于等于maxDis，那么该点可以作为起跳点。

作答：

var canJump = function(nums) {
   if (nums.length <= 1) return true;
    let maxDis = 0, needDis = nums.length - 1;  // maxDis 最远距离   needDis 终点位置
   
    for(let i = 0; i < needDis; i++) {
        if (i <= maxDis) {  // 起跳点位置 <= 最远距离
            maxDis = maxDis > nums[i] + i ? maxDis : nums[i] + i;
            if (needDis <= maxDis) {
                return true;
            } 
        }
    }
    return false;
};

最远距离maxDis也是在不断动态变化的，这样才能把全部起跳点都进行尝试。这题在leetcode的跳跃游戏应该是最简单的一道了，后面关于此题的变种会更加麻烦。

相较于之前的跳跃游戏，本次的题目难度就要大了一些

跳跃游戏Ⅱ

题目地址： https://leetcode-cn.com/problems/jump-game-ii/

题目描述：

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

题目分析

本题的跳跃与之前相同，不过要考虑跳跃次数最少的情况。在本题中的贪心做法就是从该起跳点到达下一点时的，下一点能够到达的最远位置，选距离最远的的点为下一点。

本题我自己一开始的解答是使用了递归：

定义递归方法jump，有两个参数，start是起跳点位置，end是当前起跳点能到达的边界值。每起跳一次steps步数+1。 在jump方法内根据起跳位置和end位置判断下一次的起跳点，如果下一次的起跳点上面的跳跃能大于等于终点位置，steps步数再次加1，返回steps。否则将下次起跳点的位置和最远距离传入jump，继续进行递归，直到达到终点

var jump = function(nums) {
    if (nums.length <= 1) return 0;
    // needDis 终点位置   steps跳跃步数
    let needDis = nums.length - 1, steps = 0;
    function jump(start, end) {
        let maxDis = 0, curIndex = 0;
        steps ++;
        for(let i = start; i <= end; i++) { 
            if ( maxDis <= nums[i] + i ) {
                maxDis = nums[i] + i;
                curIndex = i;
            }
            if (maxDis >= needDis) {
                if (i != 0) { steps ++; }
                return steps;
            }
        }
        return jump(curIndex, curIndex + nums[curIndex])
    }
    
    steps = jump(0, nums[0]);
    return steps;
};

当然，我之后也看了别人的解答，突然觉得自己的递归解答就不香了。思路总体是相同的，不过在代码上差距就出现了

这是同样根据思路来的

let steps = 0, start = 0, end = 1;
while (end < nums.length) {
    let maxDis = 0;
    steps ++;
    for(let i = start; i < end; i++) {
        maxDis = Math.max(maxDis, i + nums[i]);  // 当前跳跃能到达的最远距离
    }
    start = end;  // 下一次起跳范围起点
    end = maxDis + 1; // 下一次起跳范围终点
}
return steps;

发现其实内部的i会把每一个点都走一遍，所以可以进行简化。 只需要在一次steps完成时，更新下一次 能跳到最远的距离， 并以此刻作为时机来更新steps次数。

let steps = 0, maxDis = 0, end = 0, needDis = nums.length - 1;
for(let i = 0; i < needDis ; i++ ) {
    maxDis = Math.max(maxDis, i + nums[i]); 
    if ( i == end ) {
        steps++;
        end = maxDis;
    }
}
return steps;

这里就会发现大佬们的代码执行效率和内存消耗都比我的递归好多了，解答只是第一步，如果能优化代码就更好了

跳跃游戏Ⅲ

接下来趁热打铁，继续再做一道跳跃游戏

题目地址： https://leetcode-cn.com/problems/jump-game-iii/

题目描述：

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例

输入：arr = [4,2,3,0,3,1,2], start = 5

输出：true

解释：
到达值为 0 的下标 3 有以下可能方案

方案一：下标 5 -> 下标 4 -> 下标 1 -> 下标 3

方案二：下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

题目分析

本题其实更考验的不是贪心算法，而是遍历方式。

我的解答其实和上一道做法类似，递归进行（算是深度优先遍历，能够不用递归求解就不用，效率和内存消耗过大）

设置jump跳跃方法，参数是当前跳跃点位置和当前跳跃点能跳跃的距离。

• 在跳跃时记录下已经跳跃过的点
• 判断当前跳跃点位置是否超出数组
• 当前跳跃点向左向右能跳的点数值是否为0
• 如果没有，继续进行跳跃，此时跳跃点为左跳点、右跳点（并且跳跃点没有被记录过）。

var canReach = function(arr, start) {
    if (arr[start] == 0) return true;
    let len = arr.length, hasPass = [];
    function jump(curPos, jumpDis) {
        hasPass.push(curPos);
        if (curPos > len && curPos < 0) {
            return false;
        } else {
            if (arr[curPos + jumpDis] == 0 || arr[curPos - jumpDis] == 0) { return true; } else {
                if (curPos + jumpDis <= len && hasPass.indexOf(curPos + jumpDis) == -1) {
                    let resr = jump(curPos + jumpDis, arr[curPos + jumpDis]);
                    if (resr) { return true; } 
                }
                if (curPos - jumpDis >= 0 && hasPass.indexOf(curPos - jumpDis) == -1) {
                    let resl = jump(curPos - jumpDis, arr[curPos - jumpDis]);
                    if (resl) { return true; } 
                }
                return false
            }
        }
    }
    let res = jump(start, arr[start]);
    return res;
};

别人的题解大多使用的是广度遍历，所以在这里再写一下广度遍历：

其实广度遍历也非常简单，首先从起点开始，将起点加入hasSteps和queue数组

• 定义两个数组，hasSteps为已经查询数组，queue数组为当前广度层级下跳跃点数组
• queue数组，对queue作while循环，进入循环后获取queue[0]作为当前跳跃点，并移除最后一位跳跃点（因为最后一位肯定是上一层的跳跃点了）
• 判断当前跳跃点的数值是否为0， 成立返回true
• 否则将此跳跃点的下一层跳跃点加入hasSteps和queue数组，当然加入前先判断是否超过数组范围和已经查询过

跳跃层级图：

let hasSteps = [], queue = [];
hasSteps.push(start);
queue.push(start);
while( queue.length > 0) {
    let curIndex = queue[0];
    queue.shift();  // 移除最后一位跳跃点
    if (arr[curIndex] == 0) return true;
    let left = curIndex - arr[curIndex], right = curIndex + arr[curIndex];
    if ( left >= 0 && hasSteps.indexOf(left) == -1 ) {
        hasSteps.push(left);
        queue.push(left)
    }
    if (right < arr.length && hasSteps.indexOf(right) == -1 ) {
        hasSteps.push(right);
        queue.push(right);
    }
}

return false;