leetcode-55. Jump Game · Array

题面

这个题面挺简单的，不难理解。给定非负数组，每一个元素都可以看作是一个格子。其中每一个元素值都代表当前可跳跃的格子数，判断是否可以到达最后的格子。

样例

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

算法

只要存在一条路径可以到达最后就说明可以。我们可以从后往前看，只要前面存在元素索引加上其元素值大于目标元素索引值，就代表从前面格子可以跳到目标格子。只要我们从后往前判断满足该条件就向前滑动，即目标格子更新成为前面的格子，直到数组头则代表都能走通；否则，走不通。

倒叙遍历数组，定义target为数组尾，判断索引值+元素值 > target ？target = 该索引 ：不做处理；

便利结束，判断 target = 0 ? true : false

评价

时间复杂度：O(n) 只需要遍历一次数组。

空间复杂度：O(1)

源码

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         int len = nums.size();
 5         if(len <= 1)
 6             return true;
 7         
 8         int target = len -1;
 9         for(int i = target-1; i >= 0; i--)
10         {
11             if(nums[i] + i >= target)
12                 target = i;
13         }
14         
15         return target == 0;
16     }
17 };