Tao's Blog
0%

[Leetcode]55. Jump Game

Posted on In Comment Counts:
2.2k 2 mins.

题目描述

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.

例子

例子 1

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

例子 2

Input: nums = [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.

限制

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i] <= 10^5

解题思路

方法一：暴力法(回溯)

思路是在每一个位置都尝试每一个能走的步骤，最后看能不能到终点，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canJump(vector<int>& nums) {

        return canJumpAtIndex(nums, 0);
    }

private:

    bool canJumpAtIndex(const vector<int>& nums, int index) {
        if (index >= nums.size() - 1) {
            return true;
        }

        for (int step = 1; step <= nums[index]; step++) {
            if (canJumpAtIndex(nums, index + step)) {
                return true;
            }
        }

        return false;
    }
};

由于没有记忆每一次的结果，所以导致中间有很多重复计算；
时间复杂度：O(n!)
空间复杂度：O(1) (不算递归堆栈的空间)

方法二：带记忆的暴力法

根据方法一可以做一些优化，通过一个数组作为 memo 记录走过的 index 可以显著提升速度，代码如下：

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
30
31
32
33
34
class Solution {
public:
    bool canJump(vector<int>& nums) {

        visited_index = vector<bool>(nums.size(), false);

        return canJumpAtIndex(nums, 0);

    }

private:

    vector<bool> visited_index;

    bool canJumpAtIndex(const vector<int>& nums, int index) {
        if (index >= nums.size() - 1) {
            return true;
        }

        if (visited_index[index]) {
            return false;
        }

        visited_index[index] = true;

        for (int step = 1; step <= nums[index]; step++) {
            if (canJumpAtIndex(nums, index + step)) {
                return true;
            }
        }

        return false;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

方法三： 贪心算法

维护一个最远能到的index furthest_index，然后遍历一边数组同时更新 furthest_index 直到到指定位置，或者到furthest_index，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canJump(vector<int>& nums) {

        // greedy
        int furthest_index = 0;
        int current_index = 0;
        while (current_index <= furthest_index && current_index < nums.size()) {
            furthest_index = max(furthest_index, current_index + nums[current_index]);
            current_index++;
        }

        return furthest_index >= nums.size() - 1;

    }
};

时间复杂度：O(n)
空间复杂度：O(1)