LeetCode 刷题【55. 跳跃游戏】

55. 跳跃游戏

自己做

解1：逐个检查

class Solution {
public:bool Jump(vector<int>& nums, int idx){if(idx == (int)nums.size() - 1)     //抵达终点，直接返回return true;if(nums[idx] == 0)       //如果跳到头了，还没有抵达终点，说明无法抵达return false;int max = 0;int max_idx = 0;                            for(int i = 1; i <= nums[idx]; i++){            //尝试跳跃1、2、3、4...nums[idx]格，看哪个能跳最远if(idx + i < (int)nums.size() && i + nums[idx + i] > max){max = i + nums[idx + i];                //更新跳跃距离最大值max_idx = idx + i;                      //更新下标}if(max_idx >= (int)nums.size() - 1)             //超出索引范围则说明可以抵达终点return true;}return Jump(nums, max_idx);                 //找到能跳跃最远的下标后面，递归继续往下找}bool canJump(vector<int>& nums) {return Jump(nums, 0);}
};

解2：遍历回溯

class Solution {
public:bool canJump(vector<int>& nums) {int i = 0;              //起始位置int end = 0;            //终止位置后一格while(i >= 0 && i < (int)nums.size() - 1){if(nums[i] == 0 && end < i + 1){    // 此路不通 => end < i + 1限制取最远终止位置end = i + 1;     //记录终止位置的后一格位置}if(i + nums[i] >= end)   //能跳跃到终止位置的后一个位置，把i移动到终止位置后一格的位置并且更新新的终止位置i = end++;              else                    //不能跳到终止位置后一个位置，回退上一格i--;}if(i == (int)nums.size() - 1)       //抵达终点return true;else                                //不能抵达终点return false;}
};