成都彩票网站建设,wordpress 弹框,wordpress网站特别卡,浙江建设银行官方网站2023-03-29每日一题
一、题目编号
715. Range 模块二、题目链接
点击跳转到题目位置
三、题目描述
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left x right 的实数 x 。
实…2023-03-29每日一题
一、题目编号
715. Range 模块二、题目链接
点击跳转到题目位置
三、题目描述
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) 中当前正在跟踪的每个实数。
示例 1 提示
1 left right 109在单个测试用例中对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次
四、解题代码
class RangeModule {
public:RangeModule() {}void addRange(int left, int right) {auto it intervals.upper_bound(left);if (it ! intervals.begin()) {auto start prev(it);if (start-second right) {return;}if (start-second left) {left start-first;intervals.erase(start);}}while (it ! intervals.end() it-first right) {right max(right, it-second);it intervals.erase(it);}intervals[left] right;}bool queryRange(int left, int right) {auto it intervals.upper_bound(left);if (it intervals.begin()) {return false;}it prev(it);return right it-second;}void removeRange(int left, int right) {auto it intervals.upper_bound(left);if (it ! intervals.begin()) {auto start prev(it);if (start-second right) {int ri start-second;if (start-first left) {intervals.erase(start);}else {start-second left;}if (right ! ri) {intervals[right] ri;}return;}else if (start-second left) {if (start-first left) {intervals.erase(start);}else {start-second left;}}}while (it ! intervals.end() it-first right) {if (it-second right) {it intervals.erase(it);}else {intervals[right] it-second;intervals.erase(it);break;}}}private:mapint, int intervals;
};五、解题思路
(1) 有序集合。
