当前位置: 首页 > news >正文

2023-11-12 LeetCode每日一题(Range 模块)

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:map<int, int> intervals;
};

五、解题思路

(1) 有序集合。

http://www.lryc.cn/news/226912.html

相关文章:

  • 【六袆 - Framework】Angular-framework;前端框架Angular发展的由来0001;
  • JAVA集合学习
  • 【Linux】语言层面缓冲区的刷新问题以及简易模拟实现
  • Mac安装与配置eclipse
  • TCP协议(建议收藏)
  • Interactive Analysis of CNN Robustness
  • Java,多线程,线程的通信机制
  • ArcGIS进阶:栅格计算器里的Con函数使用方法
  • 小程序多文件上传 Tdesign
  • Java多线程锁
  • 【Docker】Web应用通过jar打包成WAR文件
  • Elasticsearch 外部词库文件更新
  • OpenTiny Vue 组件库支持 Vue2.7 啦!
  • 蒙特卡罗算法
  • python爬虫hook定位技巧、反调试技巧、常用辅助工具
  • Jmeter —— jmeter参数化实现
  • Day57_《MySQL索引与性能优化》摘要
  • 蓝桥杯每日一题2023.11.11
  • 『Linux升级路』基础开发工具——vim篇
  • 【Excel】补全单元格值变成固定长度
  • HackTheBox-Starting Point--Tier 2---Base
  • 算法导论笔记4:散列数 hash
  • 知识蒸馏概述及开源项目推荐
  • jupyter notebook中markdown改变图像大小
  • SpringGateWay——yml文件配置详解
  • Haproxy实现七层负载均衡
  • k8s最详细集群部署
  • Redis底层数据结构:字典
  • upload 文件自动上传写法,前后端 下载流文件流
  • Python文件、文件夹操作汇总