题目链接：55. 跳跃游戏

题解：

这个是45题跳跃游戏的简化版！

题目简述：

本题和 LeetCode刷题-45.跳跃游戏II一样，上一题是要计算到达终点的最小步数！本题不一定能走到终点，问是否能走到终点！

题解一：

首先：能跳到的位置一定是连续的一段，即某个位置跳不到，后面位置一定跳不到！

反证法： 假如能跳到i + 1位置，跳不到i位置，那么跳到i + 1位置的位置应该在i位置之前，因为i位置无法跳到，无法从他开始跳，那么该位置可以调到i + 1一定可以跳到i，矛盾！假设不成立，即跳到的位置一定是连续的一段！

解法，一模一样：

同样是具有单调性的动态规划，找到第一个可以到达当前位置i的位置即可！若last已经到了当前位置i，说明到不了当前位置i，也就到不了最后的终点，直接返回false

否则：说明全部点都能到达，返回true

时间复杂度：O(n)

空间复杂度：O(1)

AC代码一：

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

题解二：

另一种解释：基本和题解一类似！

使用j表示从可以跳到的最远位置，i表示扫描到的位置！

  • 若j < i：说明当前能跳到的最远位置到不了i，即到不了终点，直接返回false
  • 否则：更新j，即j = max(j, i + nums[i])，即从第i个位置可以跳多远，更新一下j

初始化：j = 0，能跳到的最远处为起点！

AC代码二：

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