LeetCode 筆記 - 715. Range Module

Posted on

題目在此 715. Range Module

請實作一個 RangeModule 類別來追蹤數字區間的添加、移除和查詢操作。這個類別應該支援以下方法：

  1. addRange(left: int, right: int)
    添加一個區間 [left, right)，表示從 left 到 right（不包含 right）的所有數字都被追蹤。
  2. removeRange(left: int, right: int)
    移除一個區間 [left, right)，表示從 left 到 right（不包含 right）的所有數字不再被追蹤。
  3. queryRange(left: int, right: int) -> bool
    查詢區間 [left, right) 是否完全被追蹤。如果區間內的所有數字都被追蹤，則返回 true，否則返回 false。

解題思維

這題的關鍵在於有效地管理和查詢數字區間。我們可以使用一個排序的列表來存儲已追蹤的區間，並利用二分搜尋來快速定位區間的插入點和查詢點。

addRange

當我們添加一個新的區間 [left, right) 時，我們需要找到這個區間應該插入的位置，並檢查是否與現有的區間重疊。如果有重疊，我們需要合併這些區間。

理解關鍵應該是要搞清楚用二元搜尋尋找 left 和 right 回傳值的意義，搞懂之後就不難了。

queryRange

查詢區間 [left, right) 是否完全被追蹤，我們可以使用二分搜尋來找到 right 的位置，然後檢查 right 左邊的區間是否包含 left。

removeRange

這是這題最複雜的操作，因為我們需要處理部分重疊的情況。當我們移除一個區間 [left, 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class RangeModule:

    def __init__(self):
        # use list to maintain a sorted list

        self.ranges = []

    def _search(self, target):

        # binary search
        # always return the index >= target

        left = 0
        right = len(self.ranges) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if self.ranges[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left
        
    def addRange(self, left: int, right: int) -> None:

        if not self.ranges:
            self.ranges.append([left, right])
            return

        start = self._search(left)
        # left <= start
        # left <= start left
        # so we need to check the pre left is in range or not

        if start > 0 and left <= self.ranges[start - 1][1]:
            start -= 1

        end = self._search(right + 1)
        # right + 1 <= end left
        # so **not include end**

        # 確定合併後的區間，先以 [left, right] 為基礎
        merged_left, merged_right = left, right

        # 如果 start 到 end 之間有舊區間，就用它們的邊界來擴大合併範圍
        if start < end:
            merged_left = min(left, self.ranges[start][0])
            merged_right = max(right, self.ranges[end - 1][1])

        # start to end merge to one big range
        self.ranges[start : end] = [[merged_left, merged_right]]

    def queryRange(self, left: int, right: int) -> bool:

        idx = self._search(right)
        # right <= idx left

        # so if idx == 0, means not found
        if idx == 0:
            return False

        # check range

        return self.ranges[idx - 1][0] <= left and right <= self.ranges[idx - 1][1]
        

    def removeRange(self, left: int, right: int) -> None:

        if not self.ranges:
            return

        start = self._search(left)
        if start > 0 and left <= self.ranges[start - 1][1]:
            start -= 1

        end = self._search(right + 1)
        if start >= end:
            return

        to_add = []
    
        # 處理第一個可能被部分切除的區間
        if self.ranges[start][0] < left:
            to_add.append([self.ranges[start][0], left])

        if right < self.ranges[end - 1][1]:
            to_add.append([right, self.ranges[end - 1][1]])

        self.ranges[start:end] = to_add

# 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)

也許你也會想看看