leetcode-715 Range Module

发表于 更新于 分类于 阅读次数：

描述

实现一个数据结构, 支持对区间的动态tracking, 分别有以下三个操作:

  • addRange(int left, int right) 新增一个左闭右开的tracking区间[left, right).
  • queryRange(int left, int right)check区间[left, right)是否正在被tracking, 返回布尔值.
  • removeRange(int left, int right) 取消tracking这个区间.

思路

维护一个listindex存当前有效的离散点. 这样这个list有以下特征:

  • index必然是坐标left和right两两成组的interval list, 在加入和删除的过程中, 会自动merge.
  • addRange(): left向左二分搜索插入点l(下标), right向右二分搜索插入点r. 如果l是偶数, 说明在它之前坐标们是两两成对的(可以在纸上画画), 当前点left没有落入任何一个已有的区间内, 对于left来说是一个独立点, 必然会存在与本轮更新后的index
    中, 那么加入new_index. right同理. 最后更新index的[l:r]段为new_index.
  • queryRange()和addRange()稍有差别. left向右二分搜索插入点l(下标), right向左二分搜索插入点r. 如果l == r, 说明这个被query的区间落在了index的离散点们标示出的一个(而不是多个)区间内.同时l和r需要满足是奇数, 否则query区间实际落入的是gap,而不是index标识的tracking区间.
  • removeRange()基本是addRange()的逆操作. 当r是奇数,说明在它之前坐标们没有两两成对, 这个点落入了已有区间中, 那么它在删除操作后会是一个新的区间边界点. 需要加入新的index中. 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
class RangeModule(object):

    def __init__(self):
        self.index = []
        
    def addRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: None
        """
        l = bisect.bisect_left(self.index, left)
        r = bisect.bisect_right(self.index, right)
        new_index = []
        if l%2==0:
            new_index.append(left)
        if r%2==0:
            new_index.append(right)
        self.index[l:r] = new_index        

    def queryRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: bool
        """
        l = bisect.bisect_right(self.index, left)
        r = bisect.bisect_left(self.index, right)
        return l == r and l%2      

    def removeRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: None
        """
        l = bisect.bisect_left(self.index, left)
        r = bisect.bisect_right(self.index, right)
        new_index = []
        if l%2==1:
            new_index.append(left)
        if r%2==1:
            new_index.append(right)
        self.index[l:r] = new_index        
        
# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)