当前位置:   article > 正文

leetcode 1893. 检查是否区域内所有整数都被覆盖(差分)

leetcode 1893

leetcode 1893. 检查是否区域内所有整数都被覆盖

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖,那么请你返回 true ,否则返回 false 。

已知区间 ranges[i] = [starti, endi] ,如果整数 x 满足 starti <= x <= endi ,那么我们称整数x 被覆盖了。

示例 1:
输入:ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出:true
解释:2 到 5 的每个整数都被覆盖了:
2 被第一个区间覆盖。
3 和 4 被第二个区间覆盖。
5 被第三个区间覆盖。

示例 2:
输入:ranges = [[1,10],[10,20]], left = 21, right = 21
输出:false
解释:21 没有被任何一个区间覆盖。

提示:

  • 1 <= ranges.length <= 50
  • 1 <= starti <= endi <= 50
  • 1 <= left <= right <= 50

一:排序

  • 如果 left 在某个区间,则更新 left
class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        sort(ranges.begin(), ranges.end());
        for(auto &r : ranges){
            if(left >= r[0] && left <= r[1]){
                left = r[1] + 1;
            }
        }
        return left > right;
    }
};

二:差分数组 + 前缀和

  • 用差分数组diff 维护相邻两个整数的被覆盖区间数量变化量。
    例如diff[i] = 1, 表示 i 比 i - 1多覆盖一次。
  • 对于区间 [l, r] 时,l 比 l - 1 多 1,r + 1 比 r 少 1。所以需要将diff[l] 加上 1,并将 diff[r+1] 减去 1。
class Solution {
    //差分数组
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        int diff[52] = {0};
        for(auto &range : ranges){
            diff[range[0]]++;
            diff[range[1] + 1]--;
        }
        int sum = 0;     //前缀和
        for(int i=1; i<51; i++){
            sum += diff[i];
            //当sum <= 0时,表明当前位置没被覆盖
            if(i >= left && i <= right && sum <= 0){
                return false;
            }
        }
        return true;
    }
};

三:位运算

  • 最大数值只有50,可以用 long 类型来标记某个数是否被覆盖。
class Solution {
    //位运算标记
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        long n = 1;
        long L = n << left;
        //+1是为了相减之后保证第 right 比特位为 1
        long R = n << (right + 1);
        long mark = R - L;
        long res = 0;
        for(auto &range : ranges){
            L = n << range[0];
            R = n << (range[1] + 1);
            //或运算,只要被标记过,此位就为1
            res |= (R - L);
        }
        res &= mark;
        return res == mark;
    }
};
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/1021356
推荐阅读
相关标签
  

闽ICP备14008679号