55.跳跃游戏

题目描述：给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

第一次尝试：尝试用了递归，结果超出时间限制了

class Solution {
public:bool canArrive(vector<int>& nums, int end){if(!end) return true;int index = end-1;while(index>= 0){if(index + nums[index] >= end){ //该坐标能到达if(canArrive(nums, index))  //判断能不能到达index这个坐标return true;            //如果能，则返回true}index--;}return false;}bool canJump(vector<int>& nums) {int end = nums.size()-1;return canArrive(nums, end);}
}; 	// 73 / 172 个通过的测试用例，超出时间限制

第二次尝试：跟官方解思路差不多，但是没有想的很完善，如果最大步数正好跳到了0就死路了。

class Solution {
public:bool canJump(vector<int>& nums) {int end = nums.size() - 1;int index = 0;if (nums[0] >= end) return true;while (nums[index] && index < end + 1) {int step = nums[index];int maxStep = 0;for (int i = 1; i <= step; i++) {if (index + i + nums[index + i] >= end)  //能到达return true;maxStep = max(maxStep, index + i + nums[index + i]);}index = maxStep;    //跨最大一步}return false;}
};	// 167 / 172 个通过的测试用例  [5,9,3,2,1,0,2,3,3,1,0,0]

思路：

从后往前遍历，以last_point为终点，不断找能到达last_point的点，并且替换last_point。
最后如果last_point为0，则代表能到达最后一个下标

代码+解析：

class Solution {
public:bool canJump(vector<int>& nums) {int end = nums.size() - 1;if (nums[0] >= end) return true;int index = end-1;  //从倒数第二个开始遍历int last_point = end;     //最靠近目标点且能到达的点while (index>=0) {//if (index == 0) return true;if (index + nums[index] >= last_point) {last_point = index;}index--;}if (last_point == 0) return true;return false;}
};

学到的总结：

1. 从后往前遍历