資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告