网站建设和网络营销,温州哪里有网站,重庆美邦 网站建设,铁岭网站制作3妹#xff1a;哈哈哈哈哈哈哈哈 2哥 : 3妹看什么呢#xff0c;笑的这么开森 3妹#xff1a;2哥你快来看啊#xff0c;成都欢乐谷的NPC模仿“唐僧”#xff0c; 太搞笑了。 2哥 : 哦这个我也看到了#xff0c;真的是唯妙唯肖#xff0c;不能说像#xff0c;只能说一模一…
3妹哈哈哈哈哈哈哈哈 2哥 : 3妹看什么呢笑的这么开森 3妹2哥你快来看啊成都欢乐谷的NPC模仿“唐僧” 太搞笑了。 2哥 : 哦这个我也看到了真的是唯妙唯肖不能说像只能说一模一样。 3妹哈哈哈哈西游记翻拍都可以找他助演了~ 2哥3妹今天刷题了嘛说到模仿我们今天来做一个模块的题吧~ 3妹咦2哥你这个弯拐的有点急啊。 不过是到了刷题时间了 让我来看一下吧~ 题目
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
输入 [“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] 输出 [null, null, null, true, false, true]
解释 RangeModule rangeModule new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); 返回 true 区间 [10, 14) 中的每个数都正在被跟踪 rangeModule.queryRange(13, 15); 返回 false未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字 rangeModule.queryRange(16, 17); 返回 true 尽管执行了删除操作区间 [16, 17) 中的数字 16 仍然会被跟踪
提示
1 left right 10^9 在单个测试用例中对 addRange 、 queryRange 和 removeRange 的调用总数不超过 10^4 次
思路 列表二分查找 详见代码
java代码
class RangeModule {TreeMapInteger, Integer intervals;public RangeModule() {intervals new TreeMapInteger, Integer();}public void addRange(int left, int right) {Map.EntryInteger, Integer entry intervals.higherEntry(left);if (entry ! intervals.firstEntry()) {Map.EntryInteger, Integer start entry ! null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();if (start ! null start.getValue() right) {return;}if (start ! null start.getValue() left) {left start.getKey();intervals.remove(start.getKey());}}while (entry ! null entry.getKey() right) {right Math.max(right, entry.getValue());intervals.remove(entry.getKey());entry intervals.higherEntry(entry.getKey());}intervals.put(left, right);}public boolean queryRange(int left, int right) {Map.EntryInteger, Integer entry intervals.higherEntry(left);if (entry intervals.firstEntry()) {return false;}entry entry ! null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();return entry ! null right entry.getValue();}public void removeRange(int left, int right) {Map.EntryInteger, Integer entry intervals.higherEntry(left);if (entry ! intervals.firstEntry()) {Map.EntryInteger, Integer start entry ! null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();if (start ! null start.getValue() right) {int ri start.getValue();if (start.getKey() left) {intervals.remove(start.getKey());} else {intervals.put(start.getKey(), left);}if (right ! ri) {intervals.put(right, ri);}return;} else if (start ! null start.getValue() left) {if (start.getKey() left) {intervals.remove(start.getKey());} else {intervals.put(start.getKey(), left);}}}while (entry ! null entry.getKey() right) {if (entry.getValue() right) {intervals.remove(entry.getKey());entry intervals.higherEntry(entry.getKey());} else {intervals.put(right, entry.getValue());intervals.remove(entry.getKey());break;}}}
}
