跳跃游戏(c++)_c++跳跃数组

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

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

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

示例 1:

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

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

思路：这道题一开始想的是将不合格的全部剔除，最后发现，那样做通过的例子总是差几个，不能全部ac,最后没办法了，看一下这个思路。
这个思路的主要想法是：我们设置一个k,代表能过跳到的最大地方（即数组索引的最大），判断条件就是当某个数组索引（不是最后一个数组数字索引）大于k时，直接返回false；当遍历完成时，那么就返回true

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for(int i =0;i<nums.size();i++){
            if(i>k)
                return false;
            k = max(k,i+nums[i]);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

还可以用动态规划的方法解决这个问题，当最后一个可以到达的时候，考虑前一个能不能到达，当都能到达的时候就好了

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //动态规划
        int size = nums.size();
        if(size==0){
            return false;
        }
        vector<bool>dp(size);
        dp[0]=true;
        for(int i=1;i<size;i++){
            for(int j=0;j<i;j++){
                // 如果之前的j节点可达，并且从此节点可以到跳到i
                if(dp[j]&&nums[j]+j>=i){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[size-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我们记录一个的坐标代表当前可达的最后节点，这个坐标初始等于size-1

然后我们每判断完是否可达，都向前移动这个坐标，直到遍历结束。

如果这个坐标等于0，那么认为可达，否则不可达。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //贪心算法
        int size = nums.size();
        if(size==0){
            return false;
        }
        int pos = size-1;
        for(int j=size-1;j>=0;j--){
            // 逐步向前递推
            if(nums[j]+j>=pos){
                pos = j;
            }
        }
      return pos==0;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18