数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中的范围模块
假设我们想要一个范围模块。这是一个跟踪数字范围的模块。我们的任务是高效地设计和实现以下接口。
- addRange(left, right)。这将是半开区间 [left, right)，跟踪该区间中的每个实数。现在，添加与当前跟踪的数字部分重叠的区间应添加区间中尚未跟踪的任何数字。
- queryRange(left, right)。当区间 [left, right) 中的每个实数当前都正在被跟踪时，这将返回 true。
- removeRange(left, right)，这将停止跟踪当前在区间 [left, right) 中被跟踪的每个实数。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个映射 m
- 定义一个函数 addRange()，它将接收 left、right
- removeRange(left, right)
- m[left] := right
- it := m 中 left 的位置
- 如果它不等于 m 的第一个元素，并且其前面元素的第二个值与 left 相同，则：
- (减少它 1)
- 它的第二个值 := right
- 从 m 中删除 left
- 如果它不等于 m 的最后一个元素的前一个元素，并且其下一个元素的第一个值与 right 相同，则：
- 它的第二个值 := 下一个(it) 的第二个值
- 从 m 中删除下一个(it)
- 定义一个函数 queryRange()，它将接收 left、right
- it := m 的一个子部分的位置，所有值都小于 left
- 如果 m 为空或 it 与 m 的第一个元素相同，则：
- 返回 false
- (减少它 1)
- 当 it 的第二个值 >= right 时返回 true
- 定义一个函数 removeRange()，它将接收 left、right
- 如果 m 为空，则：
- 返回
- it := m 的一个子部分的位置，所有值都大于 left
- 如果它不等于 m 的第一个元素，则：
- (减少它 1)
- 定义一个数组 v
- 当 (it 不等于 m 的最后一个元素并且 it 的第一个值 < right) 时，执行：
- 如果 it 的第一个值 < left 并且 it 的第二个值 > left，则：
- temp := it 的第二个值
- it 的第二个值 := left
- 如果 temp > right，则：m[right] := temp
- 否则，当 it 的第一个值 >= left 时，则：
- 将 it 的第一个值插入 v 的末尾
- 如果 it 的第二个值 > right，则：
- m[right] := it 的第二个值
- (增加它 1)
- 如果 it 的第一个值 < left 并且 it 的第二个值 > left，则：
- 对于初始化 i := 0，当 i < v 的大小，更新 (增加 i 1) 时，执行：
- 从 m 中删除 v[i]
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class RangeModule {
public:
map <int, int> m;
RangeModule() {
}
void addRange(int left, int right) {
removeRange(left, right);
m[left] = right;
map <int, int> :: iterator it = m.find(left);
if(it != m.begin() && prev(it)->second == left){
it--;
it->second = right;
m.erase(left);
}
if(it != prev(m.end()) && next(it)->first == right){
it->second = next(it)->second;
m.erase(next(it));
}
}
bool queryRange(int left, int right) {
map <int, int> :: iterator it = m.upper_bound(left);
if(m.empty() || it == m.begin())return false;
it--;
return it->second >= right;
}
void removeRange(int left, int right) {
if(m.empty())return;
map <int, int> :: iterator it = m.lower_bound(left);
if(it != m.begin())it--;
vector <int> v;
while(it != m.end() && it->first < right){
if(it->first < left && it->second > left){
int temp = it->second;
it->second = left;
if(temp > right){
m[right] = temp;
}
}else if(it->first >= left){
v.push_back(it->first);
if(it->second > right){
m[right] = it->second;
}
}
it++;
}
for(int i = 0; i < v.size(); i++){
m.erase(v[i]);
}
}
};
main(){
RangeModule ob;
ob.addRange(10,20);
ob.removeRange(14,16);
cout << (ob.queryRange(10,14)) << endl;
cout << (ob.queryRange(13,15)) << endl;
cout << (ob.queryRange(16,17));
}输入
Add range (10,20) Remove Range (14,16) Check ranges (10,14), (13,15), (16,17)
输出
1 0 1
更新于：2020年6月2日
233 次查看
广告