赞
踩
这道题本身数据范围比较小,难度属于比较小的一种,但是确是一道比较好的入门前缀和与差分的题。
给你一个二维整数数组 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。
然后用另一个数组求前缀和,每个位置对应的数字就是被覆盖的次数。
- class Solution {
- public:
- bool isCovered(vector<vector<int>>& ranges, int left, int right) {
- int a[52] = {0};
- int b[52] = {0};
- for(int i = 0;i < ranges.size();i++)
- {
- a[ranges[i][0]] += 1;
- a[ranges[i][1]+1] -= 1;
- }
- for(int i = 0;i <= right;i++)
- {
- b[i+1] = b[i] + a[i];
- }
- int k = 0;
- for(int i = left+1;i <= right+1;i++)
- {
- if(b[i] > 0)
- k++;
- }
- if(k == right-left + 1)
- return true;
- else
- return false;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。