当前位置:   article > 正文

LeetCode1893.检查是否区域内所有整数都被覆盖_检查区间覆盖

检查区间覆盖

这道题本身数据范围比较小,难度属于比较小的一种,但是确是一道比较好的入门前缀和与差分的题。


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

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

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

来源:力扣(LeetCode)
链接: https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered
 


看到这题,一开始我想到的是暴力解,时间复杂度也不是很高,但是题目的意思估计是想让我们用前缀和来写:

首先建立两个数组,初始化为0,

用一个数组储存标记的数据,我们将每个区间的最左边标记+1,右边的后一个标记-1。

然后用另一个数组求前缀和,每个位置对应的数字就是被覆盖的次数。

  1. class Solution {
  2. public:
  3. bool isCovered(vector<vector<int>>& ranges, int left, int right) {
  4. int a[52] = {0};
  5. int b[52] = {0};
  6. for(int i = 0;i < ranges.size();i++)
  7. {
  8. a[ranges[i][0]] += 1;
  9. a[ranges[i][1]+1] -= 1;
  10. }
  11. for(int i = 0;i <= right;i++)
  12. {
  13. b[i+1] = b[i] + a[i];
  14. }
  15. int k = 0;
  16. for(int i = left+1;i <= right+1;i++)
  17. {
  18. if(b[i] > 0)
  19. k++;
  20. }
  21. if(k == right-left + 1)
  22. return true;
  23. else
  24. return false;
  25. }
  26. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/1021354
推荐阅读
相关标签
  

闽ICP备14008679号