题目描述：给你一个非负整数数组 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;
}
};
学到的总结：
- 从后往前遍历