LeetCode 55/45 Jump Game I/II-----Greedy**

ゝ一世哀愁。 2022-08-07 12:47 8阅读 0赞

一：[Jump Game][]

题目：

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

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

Determine if you are able to reach the last index.

For example:  
A = `[2,3,1,1,4]`, return `true`.

A = `[3,2,1,0,4]`, return `false`.

链接：https://leetcode.com/problems/jump-game/

分析：此题可以采用贪心算法，用maxStep\[i\]记录第i位置所能跳跃的最大步长，那么maxStep\[i+1\] 要么等于A\[i\]，要么等于maxStep\[i\]-1,故有递归式：maxStep\[i+1\] = max(maxStep\[i\]-1, A\[i\]); 当i+maxStep\[i\]>=n-1时就可以跳跃到终点，此时的局部最优就是全局最优解，因此是贪心算法。

代码：

class Solution {
    public:
        bool canJump(int A[], int n) {
            if(n == 0 || n == 1) return true;
            int maxStep = A[0];  // 当前位置所能跳出的最远距离 
            for(int i = 1; i < n; i++){
                if(maxStep == 0) return false;     // 上次最大跳跃数等于0 表示已经不能到这一步了 
                maxStep = max(--maxStep, A[i]);  //i位置所能跳出的最远距离等于i-1位置处跳出的最远距离-1 与他自己值的最大值
                if(i+maxStep >= n-1)return true;  // 局部最优达到全局最优
            }
            return false;
        }
    };

二： [Jump Game II][]

题目：

Given an array of non-negative integers, 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.

For example:  
Given array A = `[2,3,1,1,4]`

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.)

链接：https://leetcode.com/problems/jump-game-ii/

分析：变形II不仅要求能否到达终点，还要求解最少跳跃次数，这里仍然是贪心算法，但每步需要记录三个变量，上次跳跃的最远位置last，当前跳跃的最远位置curr以及跳跃次数ret。初始化都为0，当i++后到当前位置，如果i>curr表明目前所能跳跃的最远距离已经无法到达该位置了，故不能达到终点，return -1；如果i>last,表示上次跳跃的最远位置已经不能到达了，故需要ret++且将当前curr赋值给last；并且更新当前所能跳跃的最远距离curr = max(curr, i+A\[i\])

class Solution {
    public:
        int jump(int A[], int n) {
            int ret = 0;
            int last = 0;  // 上一跳所能到达的最远距离
            int curr = 0;   // 当前跳所能到达的最远距离
            for(int i = 0; i < n; i++){
                if(i > curr) return -1;   // i++后已经超过了当前所能到达的最远位置故无法到达
                if(i > last){    //  i++后当前位置大于上一次能跳跃的最远距离 则更新并跳跃次数++
                    last=curr;
                    ret++;
                }
                curr = max(curr, i+A[i]);   // 更新当前所能到达的最远位置
            }
            return ret;
        }
    };

[Jump Game]: https://leetcode.com/problems/jump-game/
[Jump Game II]: https://leetcode.com/problems/jump-game-ii/