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

原创

福大大架构师每日一题

发布于 2022-09-15 21:45:08

4360

发布于 2022-09-15 21:45:08

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
    }
}

执行结果如下：