本文正在参加「Python主题月」,详情查看 活动链接
题目描述
这是 LeetCode 上的 1893. 检查是否区域内所有整数都被覆盖 ,难度为 简单。
Tag : 「模拟」、「树状数组」、「线段树」
给你一个二维整数数组 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
模拟
一个简单的想法是根据题意进行模拟,检查
中的每个整数,如果检查过程中发现某个整数没被
False
,所有数值通过检查则返回 True
。
代码:
class Solution {
public boolean isCovered(int[][] rs, int l, int r) {
for (int i = l; i <= r; i++) {
boolean ok = false;
for (int[] cur : rs) {
int a = cur[0], b = cur[1];
if (a <= i && i <= b) {
ok = true;
break;
}
}
if (!ok) return false;
}
return true;
}
}
复制代码
Python 3 代码:
class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
for i in range(left, right+1):
ok = False
for a, b in ranges:
if a <= i <= b:
ok = True
break
if not ok:
return False
return True
复制代码
- 时间复杂度:令
之间整数数量为 , 长度为 。整体复杂度为 - 空间复杂度:
树状数组
针对此题,可以有一个很有意思的拓展,将本题难度提升到【中等】甚至是【困难】。
将查询
修改为「四元查询数组」
,每个
包含四个指标
:代表询问
中的每个数是否在
中
的闭区间所覆盖过。
如果进行这样的拓展的话,那么我们需要使用「持久化树状数组」或者「主席树」来配合「容斥原理」来做。
基本思想都是使用
的计数情况减去
的计数情况来得出
的计数情况。
回到本题,由于数据范围很小,只有
,我们可以使用「树状数组」进行求解:
void add(int x, int u)
:对于数值
出现次数进行 操作;int query(int x)
:查询某个满足
的数值的个数。
那么显然,如果我们需要查询一个数值
是否出现过,可以通过查询
来得知。
Java 代码:
class Solution {
int n = 55;
int[] tr = new int[n];
int lowbit(int x) {
return x & -x;
}
void add(int x, int u) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
public boolean isCovered(int[][] rs, int l, int r) {
for (int[] cur : rs) {
int a = cur[0], b = cur[1];
for (int i = a; i <= b; i++) {
add(i, 1);
}
}
for (int i = l; i <= r; i++) {
int cnt = query(i) - query(i - 1);
if (cnt == 0) return false;
}
return true;
}
}
复制代码
Python 3 代码:
class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
n = 55
tr = [0] * n
def lowbit(x):
return x & -x
def add(x, u):
i = x
while i <= n:
tr[i] += u
i += lowbit(i)
def query(x):
ans = 0
i = x
while i > 0:
ans += tr[i]
i -= lowbit(i)
return ans
for a,b in ranges:
for i in range(a, b+1):
add(i, 1)
for i in range(left, right+1):
cnt = query(i) - query(i-1)
if not cnt:
return False
return True
复制代码
- 时间复杂度:令
之间整数数量为 , 为 ,常数 固定为 。建树复杂度为 ,查询查询复杂度为 。整体复杂度为 - 空间复杂度:
树状数组(去重优化)
在朴素的「树状数组」解法中,我们无法直接查询
区间中被覆盖过的个数的根本原因是「某个值可能会被重复添加到树状数组中」。
因此,一种更加优秀的做法:在往树状数组中添树的时候进行去重,然后通过
直接得出
范围内有多少个数被添加过。
这样的 Set
去重操作可以使得我们查询的复杂度从
下降到
。
由于数值范围很小,自然也能够使用数组来代替
Set
进行标记(见 P2)
Java 代码:
class Solution {
int n = 55;
int[] tr = new int[n];
int lowbit(int x) {
return x & -x;
}
void add(int x, int u) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
public boolean isCovered(int[][] rs, int l, int r) {
Set<Integer> set = new HashSet<>();
for (int[] cur : rs) {
int a = cur[0], b = cur[1];
for (int i = a; i <= b; i++) {
if (!set.contains(i)) {
add(i, 1);
set.add(i);
}
}
}
int tot = r - l + 1, cnt = query(r) - query(l - 1);
return tot == cnt;
}
}
复制代码
Java 代码:
class Solution {
int n = 55;
int[] tr = new int[n];
boolean[] vis = new boolean[n];
int lowbit(int x) {
return x & -x;
}
void add(int x, int u) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
public boolean isCovered(int[][] rs, int l, int r) {
for (int[] cur : rs) {
int a = cur[0], b = cur[1];
for (int i = a; i <= b; i++) {
if (!vis[i]) {
add(i, 1);
vis[i] = true;
}
}
}
int tot = r - l + 1, cnt = query(r) - query(l - 1);
return tot == cnt;
}
}
复制代码
- 时间复杂度:令
之间整数数量为 , 为 ,常数 固定为 。建树复杂度为 ,查询查询复杂度为 。整体复杂度为 - 空间复杂度:
线段树(不含“懒标记”)
更加进阶的做法是使用「线段树」来做,与「树状数组(优化)」解法一样,线段树配合持久化也可以用于求解「在线」问题。
与主要解决「单点修改 & 区间查询」的树状数组不同,线段树能够解决绝大多数「区间修改(区间修改/单点修改)& 区间查询」问题。
对于本题,由于数据范围只有
,因此我们可以使用与「树状数组(优化)」解法相同的思路,实现一个不包含“懒标记”的线段树来做(仅支持单点修改 & 区间查询)。
Java 代码:
class Solution {
// 代表 [l, r] 区间有 cnt 个数被覆盖
class Node {
int l, r, cnt;
Node (int _l, int _r, int _cnt) {
l = _l; r = _r; cnt = _cnt;
}
}
int N = 55;
Node[] tr = new Node[N * 4];
void pushup(int u) {
tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
}
void build(int u, int l, int r) {
if (l == r) {
tr[u] = new Node(l, r, 0);
} else {
tr[u] = new Node(l, r, 0);
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
// 从 tr 数组的下标 u 开始,在数值 x 的位置进行标记
void update(int u, int x) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].cnt = 1;
} else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) update(u << 1, x);
else update(u << 1 | 1, x);
pushup(u);
}
}
// 从 tr 数组的下标 u 开始,查询 [l,r] 范围内有多少个数值被标记
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0;
if (l <= mid) ans += query(u << 1, l, r);
if (r > mid) ans += query(u << 1 | 1, l, r);
return ans;
}
public boolean isCovered(int[][] rs, int l, int r) {
build(1, 1, N);
for (int[] cur : rs) {
int a = cur[0], b = cur[1];
for (int i = a; i <= b; i++) {
update(1, i);
}
}
int tot = r - l + 1 , cnt = query(1, l, r);
return tot == cnt;
}
}
复制代码
Python 3 代码:
class Solution:
def isCovered(self, ranges: List[List[int]], l: int, r: int) -> bool:
def pushup(u):
tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt
def build(u, l, r):
tr[u] = Node(l, r, 0)
if l != r:
tr[u] = Node(l, r, 0)
mid = l + r >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
pushup(u)
# 从 tr 数组的下标 u 开始,在数值 x 的位置进行标记
def update(u, x):
if tr[u].l == x and tr[u].r == x:
tr[u].cnt = 1
else:
mid = tr[u].l + tr[u].r >> 1
if x <= mid:
update(u << 1, x)
else:
update(u << 1 | 1, x)
pushup(u)
# 从 tr 数组的下标 u 开始,查询 [l,r] 范围内有多少个数值被标记
def query(u, l, r):
if l <= tr[u].l and tr[u].r <= r:
return tr[u].cnt
mid = tr[u].l + tr[u].r >> 1
ans = 0
if l <= mid:
ans += query(u << 1, l, r)
if r > mid:
ans += query(u << 1 | 1, l, r)
return ans
N = 55
tr = [None] * N * 4
build(1, 1, N)
for a,b in ranges:
for i in range(a, b+1):
update(1, i)
tot = r - l + 1
cnt = query(1, l, r)
return tot == cnt
class Node:
def __init__(self, l, r, cnt):
self.l = l
self.r = r
self.cnt = cnt
复制代码
- 时间复杂度:令
之间整数数量为 , 为 ,常数 固定为 。建树复杂度为 ,查询查询复杂度为 。整体复杂度为 - 空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1893
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
近期评论