05 August 2008
范围模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为半开区间的范围并查询它们。
半开区间 [left, right) 表示所有实数 x，其中 left <= x < right。
实现 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class RangeModule {
/*
https://leetcode.com/problems/range-module/discuss/108910/Java-TreeMap
*/
TreeMap<Integer, Integer> map;
public RangeModule() {
map = new TreeMap<>();
}
public void addRange(int left, int right) {
if (right <= left) {
return;
}
Integer start = map.floorKey(left);
Integer end = map.floorKey(right);
if (start == null && end == null) {
map.put(left, right);
} else if (start != null && map.get(start) >= left) {
map.put(start, Math.max(map.get(end), Math.max(map.get(start), right)));
} else {
map.put(left, Math.max(map.get(end), right));
}
// clean up intermediate intervals
Map<Integer, Integer> subMap = map.subMap(left, false, right, true);
Set<Integer> set = new HashSet(subMap.keySet());
map.keySet().removeAll(set);
}
public boolean queryRange(int left, int right) {
Integer start = map.floorKey(left);
if (start == null) {
return false;
}
return map.get(start) >= right;
}
public void removeRange(int left, int right) {
if (right <= left) {
return;
}
Integer start = map.floorKey(left);
Integer end = map.floorKey(right);
if (end != null && map.get(end) > right) {
map.put(right, map.get(end));
}
if (start != null && map.get(start) > left) {
map.put(start, left);
}
// clean up intermediate intervals
Map<Integer, Integer> subMap = map.subMap(left, true, right, false);
Set<Integer> set = new HashSet(subMap.keySet());
map.keySet().removeAll(set);
}
}
/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule obj = new RangeModule();
* obj.addRange(left,right);
* boolean param_2 = obj.queryRange(left,right);
* obj.removeRange(left,right);
*/