55. 跳跃游戏

55. 跳跃游戏

描述：
给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

 1 解法1：    12 ms    9.8 MB
 2 class Solution {
 3 public:
 4     bool canJump(vector<int>& nums) {
 5         /*思路：
 6             如果当前位置i+ nums[i]到达的位置最远位置为loc
 7                 从i~i+nums[i]遍历的时候，若是j+nums[j] 超过了loc，则更新loc
 8                     判断loc是否到达了最后的位置
 9         */
10         if(nums.size()==1) return true;
11         int loc=nums[0];
12         for(int i=1;i<=loc;i++){
13             if(loc>=nums.size()-1) return true;
14             if(i+nums[i]>loc){//loc在一直更新，那么for循环也在一直变，
15                 loc=i+nums[i];
16             }
17         }
18         //若是没有答案，最后返回false即可
19         return false;
20     }
21 };

 1 解法2：    20 ms    9.8 MB
 2 
 3 class Solution {
 4 public:
 5     bool canJump(vector<int>& nums) {
 6         int loc = 0;//当前最远位置,一直在更新中，loc超过了 nums.size()-1,可以返回了
 7         for (int i = 0; i < nums.size(); i++){
 8              if (i >loc) return false;//当前遍历的位置到达i ,i>loc,但是从0到 loc,无法跳转到i,false
 9             loc = max(loc, i + nums[i]);//当前最远的位置更新loc
10             if(loc>nums.size()-1) return true;
11         }
12         return true;
13     }
14 };

 1 74 / 75 个通过测试用例
 2 状态：超出时间限制
 3 递归来做：
 4 class Solution {
 5 public:
 6     bool dg(vector<int>& nums,int loc){// loc为当前遍历的位置
 7         if(loc==nums.size()-1) return true;
 8         for(int j=1;j<=nums[loc];j++){//递归 遍历从1~nums[loc]
 9                 if(dg(nums,loc+j)==true) return true;
10          }
11         return false;
12     }
13     bool canJump(vector<int>& nums) {
14         return dg(nums,0);
15     }
16 };