leetcode 55 跳跃游戏

题目：55. 跳跃游戏

参考题解：跳跃游戏-代码随想录

每一步可以选择不同的长度。在跨出一步后，后面在此基础上，继续前进。很明显的回溯思路。

我按照回溯思路，码出代码，通过75/166之后，代码超时。我看了下超时的测试用例：[9997,9996,9995,……3,2,1,0,0]，需要计算 9997 ∗ 9996 ∗ … … ∗ 3 ∗ 2 ∗ 1 9997*9996*……*3*2*1 9997∗9996∗……∗3∗2∗1次。这是回溯中，最坏的一种情况。

class Solution {
public:
    bool backTracking(vector& nums, int start, int& pass){
        if(pass >= nums.size()-1)
            return true;
        
        for(int step=nums[start]; step>0; step--){
            pass += step; // 尝试向前走step
            if(backTracking(nums,start+step,pass)) return true; // 成功则层层true退出
            pass -= step; // 退回step
        }
        return false; // 当前位置，所有step尝试均为到达，返回false，进行回退
    }

    bool canJump(vector& nums) {
        int start = 0;
        int pass = 0;
        return backTracking(nums,start,pass);
    }
};

为了避免陷入方法一的问题，我们遇到0的时候，进行判断。

• 序列只有一个元素，且该元素为0，不用前进，坐享其成。
• 序列均为非负整数，只要不是0，均会前进，所以只有0需要判断。判断是否这个0是否无法绕过。

根据这个指导思想，我码出了方法二代码。但是这种方法存在一个问题，需要考虑的面面俱到。很有可能漏掉考虑某些情况。下面的代码通过141/166。

#include 
#include 

using namespace std;

class Solution {
public:
    bool canJump(vector& nums) {
        if(nums.size()==1 && nums[0]==0) // 只有一个元素，且该元素为0，不用前进，坐享其成
            return true;

        for(int i=0; i=0){ // 遇到0，只要前面的数字不都掉入这个位置，也没关系
                if(nums[j] != val)
                    break;
                j--;
                val++;
            }
            if(j>=0 && nums[j]!=0 ) // 当前0，必须在遇见之前0之前，做出决断
                continue; // 0位置可以避过，继续前进
            else
                return false; // 0位置无法避过，必然入坑之后，无法动弹，返回false
        }
        return true;
    }
};

int main(void){
    vector nums = {2,0,0};
    Solution s;
    cout< 
方法三：跨域区间 
不断向前移动，记录可以跨越到达最远的位置。当最远位置大于目标位置，成功。
 
这个思路比较简单，有效。成功通过所有测试用例。
 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    bool canJump(vector& nums) {
        int start = 0;
        int pass = start + nums[start];
        int max_pass = pass;

        if(max_pass>=nums.size()-1)
            return true;
        
        for(int i=start+1; i<=max_pass; i++){ 
            pass = i + nums[i];
            max_pass = max(max_pass,pass); // 不断前进，更新最远可到达位置
            if(max_pass >= nums.size()-1)
                return true;
        }

        return false;
    }
};

int main(void){
    vector nums = {3,2,1,0,4};
    Solution s;
    cout<