zkkKillua's Blog
0%

55.跳跃游戏

发表于 更新于 分类于

1. 朴素

bool reach[]记录是否可以到达。
遍历nums[i]，将其可以到达的位置置为true。时间复杂度是O(n)，因为就算修改reach[]是O(n)，但是还是可能会去访问后续的元素（即使没有修改），导致需要的时间很长。空间复杂度O(n)。 

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
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1)
            return true;
        bool *reach = new bool[n] {false};

        reach[0] = true;
        for (int i = 0; i < n; i++) {
            if (!reach[i])
                continue;
            for (int k = 1; k <= nums[i]; k++) {
                if (i + k >= n)
                    break;
                if (!reach[i + k])
                    reach[i + k] = true;
                if (i + k == n - 1) {       // 适当剪枝
                    delete []reach;
                    return true;
                }
            }
        }

        bool ans = reach[n - 1];
        delete []reach;
        return ans;
    }
};

2. 记录右侧最远距离

考虑题目要求，由于可走的长度是>=0的，因此可以直接记录最远的距离，而最远距离左侧的距离一定可达。
当当前距离超过最远距离时，意味着当前距离无法到达。
时间复杂度O(n)，空间复杂度O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1)
            return true;
        int farthest = 0;

        for (int i = 0; i < n; i++) {
            if (i > farthest)
                return false;
            farthest = farthest >= i + nums[i] ? farthest : i + nums[i];
            if (farthest >= n - 1)
                break;
        }

        return true;
    }
};