leetcode 55 题解

发表于

题目：

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

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

Example 2:

1
2
3
4
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.

题解：

这是一道标明为Greedy类型的题目，可以用贪心算法来解，问题就在于如何判断对这道题目来说何为“局部最优解”。

这道题的意思是从下标为0的位置开始，每个位置上有这次可以跳跃的最长距离，问能否达到终点。一开始我想到的方法是找此次跳跃距离覆盖的位置中跳跃距离最长的位置，但这个方法是错误的，当输入为[4 2 0 0 1 1 4 4 4 0 4 0]时，它在判断第一步跳到哪里的时候会选择位置1（元素2）而不是位置4（元素1），这就导致了当它从新的位置进行跳跃时，其后两个元素都为0，于是就判断无法达到终点了，然而实际是可以的。

从上述例子可以发现，尽管1小于2，但它所能达到的位置与终点的距离比2更近，所以在这道题中局部最优应该是选择能够达到的位置距离终点最短的元素作为此次跳跃的目的地。代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool canJump(vector<int>& nums) {
    int size = nums.size();
    if(nums.size() == 1) return true;
    for(int i = 0; i < size; i++){
        if(nums[i] == 0){
            return false;
        }
        int min = size - nums[i + 1] - i - 1, pos = i + 1;
        for(int j = i + 1; j <= i + nums[i]; j++){
            if(j == size - 1){
                return true;
            }
            pos = (size - nums[j] - j) <= min ? j : pos;
            min = (size - nums[j] - j) <= min ? size - nums[j] - j : min;
        }
        i = pos - 1;
    }
}

升级

做完这道题后我发现了一道名为Jump Game Ⅱ的题目，原来是这道题的升级版，要求不仅给出判断能否达到终点，还要给出跳跃的步数。因为实际上我们刚才找到的就是最短的路径了，所以只需要稍微修改一下代码就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int jump(vector<int>& nums) {
    int count = 0;
    int size = nums.size();
    if(nums.size() == 1) return 0;
    for(int i = 0; i < size; i++){
        count++;
        if(nums[i] == 0){
            return false;
        }
        int min = size - nums[i + 1] - i - 1, pos = i + 1;
        for(int j = i + 1; j <= i + nums[i]; j++){
            if(j == size - 1){
                return count;
            }
            pos = (size - nums[j] - j) <= min ? j : pos;
            min = (size - nums[j] - j) <= min ? size - nums[j] - j : min;
        }
        i = pos - 1;
    }
}