LeetCode_55_跳跃游戏

自己写的

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int length = nums.size(), scope = 0;
        bool result = false;
        priority_queue<int> q;
        q.push(0);
        if (length == 1) return true;
        if (nums[0] == 0) return false;
        for (int i = 0; i < length - 1; i++) {
            scope = nums[i];
            if (i > q.top()) return false;
            if (scope + i >= length - 1) {
                result = true;
                break;
            }
            if (nums[i] != 0) q.push(scope + i);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

重点是为了让每段覆盖都有能重合的地方，所引入了优先队列

---

代码随想录答案更简单

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true;
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

重点在于循环的条件i <= cover