Range模块是跟踪数字范围的模块。
设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象
void addRange(int left, int right) :
添加 半开区间 [left, right)，跟踪该区间中的每个实数。
添加与当前跟踪的数字部分重叠的区间时，
应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) :
只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true
否则返回 false 。
void removeRange(int left, int right) :
停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
输入：[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]。
输出：[null, null, null, true, false, true]。
这是力扣715的题。用有序表。 动态开点线段树也行。
这道题是java运行速度远远领先go，但这是特例。其他力扣题，基本是持平的。
内存上来说，java是go的好几倍。
综合来说，go比java省资源。
rust自然是最省资源的，运行速度也是最快的。
代码用rust编写，代码如下：
use std::collections::BTreeMap;
struct RangeModule {
map: BTreeMap<i32, i32>,
}
impl RangeModule {
fn new() -> Self {
Self {
map: BTreeMap::new(),
}
}
fn add_range(&mut self, left: i32, right: i32) {
if right <= left {
return;
}
let start = self.map.range(..=left).last();
let mut start_key = 0;
let mut start_value = 0;
if !start.is_none() {
start_key = *start.unwrap().0;
start_value = *start.unwrap().1;
}
let end = self.map.range(..=right).last();
let mut end_key = 0;
let mut end_value = 0;
if !end.is_none() {
end_key = *end.unwrap().0;
end_value = *end.unwrap().1;
}
if start.is_none() && end.is_none() {
self.map.insert(left, right);
} else if !start.is_none() && start_value >= left {
self.map.insert(start_key, get_max(end_value, right));
} else {
self.map.insert(left, get_max(end_value, right));
}
let mut sets: Vec<i32> = vec![];
for (k, _) in self.map.range(left+1..=right) {
sets.push(*k);
}
for s in sets.iter() {
self.map.remove(s);
}
}
fn query_range(&mut self, left: i32, right: i32) -> bool {
let start = self.map.range(..=left).last();
let mut start_key = 0;
let mut start_value = 0;
if !start.is_none() {
start_key = *start.unwrap().0;
start_value = *start.unwrap().1;
}
if start.is_none() {
return false;
}
return start_value >= right;
}
fn remove_range(&mut self, left: i32, right: i32) {
if right <= left {
return;
}
let start = self.map.range(..=left).last();
let mut start_key = 0;
let mut start_value = 0;
let mut start_is_none = true;
if !start.is_none() {
start_key = *start.unwrap().0;
start_value = *start.unwrap().1;
start_is_none = false;
}
let end = self.map.range(..=right).last();
let mut end_key = 0;
let mut end_value = 0;
let mut end_is_none = true;
if !end.is_none() {
end_key = *end.unwrap().0;
end_value = *end.unwrap().1;
end_is_none = false;
}
if !end_is_none && end_value > right {
self.map.insert(right, end_value);
}
if !start_is_none && start_value > left {
self.map.insert(start_key, left);
}
let mut sets: Vec<i32> = vec![];
for (k, _) in self.map.range(left..right) {
sets.push(*k);
}
for s in sets.iter() {
self.map.remove(s);
}
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}执行结果如下：
