题目

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

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

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

示例 1:

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

示例 2:

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

题解

注意,下面说明中的位置从1开始,不是从0开始

最开始的思路就是暴力遍历,首先在第一个位置上,我们知道了最大可跳跃的距离,那我们就从1开始到最大距离进行遍历,当前位置加上跳跃的距离,之后再次进行该递归操作,继续往下遍历,终止条件是当前位置加上跳跃的距离大于了数组的长度,那说明为真,如果遍历完都无法大于数组的长度,那么说明无法跳跃到终点,返回为假。

以题目给的例子2, 3, 1, 1, 4来说,首先我们在第一个位置上,可跳跃的最大距离是2,那么我们可跳1次,也可跳2次。如果跳一次,我们就在第二个位置上,可跳跃的距离是3,我们依旧可以选择跳1次,那么我们在位置3上,再跳一次,跳到位置4,再跳一次,跳到位置5,到达终点。

以例子3, 2, 1, 0, 4为例,首先我们在第一个位置上,可跳跃最大为3,我们首先跳1次,跳到位置2, 再跳一次,到位置3,再跳一次,到位置4,这个时候可跳最大距离为0,无法再跳了。

那么我们回去,在位置2上,我们跳2次,又跳到了位置4,没办法继续。

我们再回头回到位置1,我们选择跳2次,跳到位置3,而我们知道位置3是不行的,那么我们返回到位置1。我们选择跳3次,跳到了位置4,没办法继续进行下去。这个时候所有的可能性都试完了,没有找到路径大于数组的长度,我们得出结论无法跳跃到终点。

这种方式复杂度肯定非常高,为了降低复杂度,需要使用一定的空间进行备份数据,进行剪枝。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool interCanJump(int *nums, int pos, int count, map<int, bool> &backups) {
   int curr_steps = nums[pos];
   // 如果结果存在,直接返回,不再递归查找
   if (backups.find(pos) != backups.end()) {
       return backups[pos];
   }

   // 当前位置+跳跃距离大于数组长度,返回真
   if (pos + curr_steps >= count - 1) {
       backups[pos] = true;
       return true;
   }

   // 在当前位置上递归遍历所有跳跃距离
   for (int i = curr_steps; i >= 1; i--) {
       if (interCanJump(nums, pos + i, count, backups))
           return true;
   }

   backups[pos] = false;
   return false;
}

bool canJump(vector<int>& nums) {
   if (nums.empty())return false;
   map<int, bool> backups;

   return interCanJump(&nums[0], 0, nums.size(), backups);
}

但在leetcode上运行后,发现当数据特别大时,将会运行超时。显然还有更加优化的算法。

这道题实际上属于动态规划,这个时候我们就要开始想怎么往动态规划上凑。在上面的实现中,效率低的一个主要原因是我们进行了很多无效的遍历,虽然有很多重复的遍历被我们存储,但依旧有很多情况是没有必要遍历的。

我们实际需要的是在当前的位置下,我们最远可以跳到的最远距离是哪里。这依旧是个求最值的问题,即我们能够跳的最远距离是哪里?如果最远距离都不大于数组长度,那么结果肯定是假。如果大于,那么结果就是真。

那么我们想该怎么求最远的距离。

依旧以例子2, 3, 1, 1, 4来说,我们当前在位置1,这个时候我们有2种选择,要么跳1步,要么跳2步。如果跳1步,那么会到位置2,可跳跃的最大长度为3,那么如果选择跳1步,可跳的最远距离是1 + 1 + 3,我们在位置1上,跳了1步,之后又可最多跳3步,所以我们最远可跳到位置5。

如果我们在位置1上选择跳2步,那么我们到位置3,位置3的最大距离为1,那么这种情况下的最远距离是 1 + 2 + 1,结果为4,这种方式肯定显然不如第一种方式,所以我们选择第一种方式。

当我们选择第一种方式后,我们发现跳到的最大距离已经大于等于数组的长度,那么我们的结果就为真了。

再拿例子3, 2, 1, 0, 4来说,我们在位置1上,选择有3种,如果跳1次,那么在位置2,位置2上的最大距离为2,那么最大距离为:1 + 1 + 2,结果为4。

如果跳2次,那么最大距离为:1 + 2 + 1,结果依旧为4。如果跳3次,那么结果为:1 + 3 + 0,结果依旧为4。

几种方式相同,那么我们选最大的跳3次,当我们到位置4后,我们发现当前最大可跳跃距离为0,这个时候无法进行下去了,那么直接返回假。

经过上面的说明,会发现这道题实际上是个贪心,当前局部最优结果便是最终的最优结果。

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool canJump(vector<int>& nums) {
    if (nums.empty())return false;
    
    int pos = 0;
    // 如果可跳跃距离小于数组长度就一直循环
    while (pos + nums[pos] < nums.size() - 1) {
        int tmp_pos = pos;
        int max_step = 0;
        
        // 如果可跳跃距离为0,说明没办法再前进,那么返回假
        if (nums[tmp_pos] == 0) return false;

        // 在当前位置下,查找可跳跃的最远距离,并保存对应的位置
        for (int i = 1; i <= nums[tmp_pos]; i++) {
            if (tmp_pos + i + nums[tmp_pos + i] >= max_step) {
                max_step = tmp_pos + i + nums[tmp_pos + i];
                pos = tmp_pos + i;
            }
        }
    }

    return true;
}

这种方式下,就可完成题目,不再会出现超时问题。主要原因是,我们只找可跳跃的最长的那个距离,不再像第一种方式那样,长的、短的全都尝试一遍,无用的跳跃方式太多,导致复杂度上升。

这个时候,再来看网上相关的题解,发现实际上有更简单的方法,实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
bool canJump(vector<int>& nums) {
    if (nums.empty())return false;
    
    int max_step = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (i > max_step) {
            return false;
        }

        max_step = max(nums[i] + i, max_step);
    }

    return true;
}

实际上自己实现的第二种方式已经跟这个很像了,但确实没有这个优化程度高。

这个实现的思想是,我们记录一个可以走的最远长度max_step,当我们开始往前跳时,判断我们是否在这个最远可走的范围内,如果不在,那么就返回假。

如果在,我们更新下最远可跳的位置,最远可跳的位置是max_step = max{ i + nums[i], max_step}。然后依次往前走。

再看下自己的实现,实际上所想的有点接近这个思想,找到最远可跳的位置,之后更新位置,再往前找最远可跳的位置,依次往前,判断是否可到达终点,但自己实现的复杂度太高了,水平还是有限。