Posted on 2023-01-28 15:29
Uriel 閱讀(54)
評論(0) 編輯 收藏 引用 所屬分類:
模擬 、
閑來無事重切Leet Code
構建一個data stream，有以下三種操作：
SummaryRanges() -> Initializes the object with an empty stream.
void addNum(int value) -> Adds the integer value to the stream.
int[][] getIntervals() -> Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi]. The answer should be sorted by starti.
Discussion中有人使用python的Sorted List，其實不必，參考->https://leetcode.com/problems/data-stream-as-disjoint-intervals/solutions/531106/python-solution-using-bisect-to-do-binary-search-beating-99-5-in-time/
初始化兩個intervals：[[-10001, -10001], [10001, 10001]] （比data stream小1或者大1即可），每次插入時調用bisect.bisect返回該插入在何處，通過判斷當前要插入的值是否與前一個或者后一個區間有overlap來決定是否需要合并區間
1 #352
2 #Runtime: 115 ms (Beats 100%)
3 #Memory: 18.5 MB (Beats 88.46%)
4
5 class SummaryRanges(object):
6
7 def __init__(self):
8 self.ds = [[-10001, -10001], [10001, 10001]]
9
10 def addNum(self, value):
11 """
12 :type value: int
13 :rtype: None
14 """
15 idx = bisect.bisect(self.ds, [value])
16 l1, l2 = self.ds[idx - 1]
17 r1, r2 = self.ds[idx]
18 if l2 == value - 1 and r1 == value + 1:
19 self.ds = self.ds[ : idx - 1] + [[l1, r2]] + self.ds[idx + 1 : ]
20 elif l2 == value - 1:
21 self.ds[idx - 1][1] = value
22 elif r1 == value + 1:
23 self.ds[idx][0] = value
24 elif l2 < value - 1 and r1 > value + 1:
25 self.ds = self.ds[ : idx] + [[value, value]] + self.ds[idx : ]
26
27
28 def getIntervals(self):
29 """
30 :rtype: List[List[int]]
31 """
32 return self.ds[1 : -1]
33
34
35
36 # Your SummaryRanges object will be instantiated and called as such:
37 # obj = SummaryRanges()
38 # obj.addNum(value)
39 # param_2 = obj.getIntervals()