2022-09-15Range模块是跟踪数字范围的模块。 设计数据结构来跟踪表示为 半开区间 的范围并查询它们。 半开区间 [left, right) 表示所有 left ＜= x ＜ righ

2022-09-15：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]。

答案2022-09-15：

这是力扣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
    }
}

执行结果如下：

左神java代码

这篇好文章是转载于：学新通技术网