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 仍然会被跟踪)
准备,需要了解的知识
/**
* 了解下treeMap的用法
* @param args
*/
public static void main(String[] args) {
// creating object of TreeMap<Integer, String>
TreeMap<Integer, String>
treemap = new TreeMap<Integer, String>();
// populating tree map
treemap.put(1, "One");
treemap.put(2, "Two");
treemap.put(3, "Three");
treemap.put(4, "Four");
treemap.put(5, "Five");
Map.Entry<Integer, String> higherEntry = treemap.higherEntry(3);
System.out.println("higherEntry => " + higherEntry); // higherEntry => 4=Four
Map.Entry<Integer, String> lowerEntry = treemap.lowerEntry(3);
System.out.println("lowerEntry => " + lowerEntry); // lowerEntry => 2=Two
Map.Entry<Integer, String> lastEntry = treemap.lastEntry();
System.out.println("lastEntry => " + lastEntry); // lastEntry => 5=Five
}
方法一:有序集合 / 有序映射
class RangeModule {
TreeMap<Integer, Integer> intervals;
public RangeModule() {
intervals = new TreeMap<Integer, Integer>();
}
public void addRange(int left, int right) {
Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
if (entry != intervals.firstEntry()) {
Map.Entry<Integer, 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.Entry<Integer, 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.Entry<Integer, Integer> entry = intervals.higherEntry(left);
if (entry != intervals.firstEntry()) {
Map.Entry<Integer, 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) {
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;
}
}
}
}
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/range-module/solution/range-mo-kuai-by-leetcode-solution-4utf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
网友评论