Jump Game 和Jump Game II---LeetCode

今天我们来看一下LeetCode的第55题和第45题：Jump Game和Jump Game II，原题连接：Jump GameII，Jump Game；个人认为这是两道典型的贪心算法题目。Jump Game的大意为：给定一组非负整数，每个整数代表着当前位置能够跳的最大的步数，判断能否从开始位置到达末尾。如：

A = [2,3,1,1,4], return true.

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

Jump Game II的大意为：返回到达末尾的最小步数，如

A = [2,3,1,1,4], return 2.

先来看看Jump Game：

仍然采用“局部最优和全局最优算法”，局部最优维护着从当前位置开始，以当前位置的值为最大步数，所能跳到的最远的地方，即局部最优localLength=i+nums[i]；而全局最优维护着截止到当前位置，所能调到的最远距离，即globalLength=max（globalLength，localLength）；

代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==0)
            return true;
        int size=nums.size();
        int i=0;
        int globalLength=nums[i];
        int localLength=nums[i];
        while(i<size){
           // localLength=localLength>nums[i]?localLength:nums[i];
            localLength=nums[i];
            globalLength=globalLength>localLength?globalLength:localLength;
            if((i+globalLength)>=size-1)
                return true;
            if(globalLength==0)
                return false;
            
            i++;
            globalLength--;
        }
        return false;
    }
};

对于Jump GameII，因为是要找的调到最后位置的最小步数，仍然使用贪心策略，我们维护两个变量，当前步数所能跳到的最远距离，以及下一步数所能跳到的最远距离，代码如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        int size=nums.size();
        int steps=0;
        int globalLength=0;//当前步数所能跳到的最远距离
        int localLength=0;//下一步数所能跳到的最远距离
        for(int i=0;i<size;i++){
            if(i>globalLength){//当当前步数不能到达终点时候

  steps++;//步数加一
                globalLength=localLength;//当前步数最远距离更新
            }
            localLength=localLength>(i+nums[i])?localLength:(i+nums[i]);//在当前步数所能到达的范围内，寻找下一步所能到达的最远距离
        }
        return steps;
    }
};

Jump Game 和Jump Game II---LeetCode

浏览过的版块