일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- LeetCode
- Generator
- 프로그래머스
- Python Implementation
- kaggle
- attribute
- t1
- iterator
- 시바견
- Regular Expression
- 운영체제
- 파이썬
- 715. Range Module
- 밴픽
- 컴퓨터의 구조
- Protocol
- data science
- Python
- 315. Count of Smaller Numbers After Self
- shiba
- Substring with Concatenation of All Words
- concurrency
- 43. Multiply Strings
- 109. Convert Sorted List to Binary Search Tree
- Class
- Python Code
- DWG
- Decorator
- 30. Substring with Concatenation of All Words
- Convert Sorted List to Binary Search Tree
- Today
- Total
Scribbling
LeetCode: 715. Range Module 본문
We need to deal with ranges to solve this problem.
Below is the link of a wonderful solution.
The solution uses a single list of integers to deal with ranges, which allows us to use 'bisect' functions easily.
Personally, understanding his idea was easy, but coming up with it would have been very difficult.
Below is the code.
class RangeModule:
from bisect import bisect_left, bisect_right
def __init__(self):
self.range = []
def addRange(self, left: int, right: int) -> None:
start = bisect_left(self.range, left)
end = bisect_right(self.range, right)
new_range = []
if start % 2 == 0:
new_range.append(left)
if end % 2 == 0:
new_range.append(right)
self.range[start:end] = new_range
def queryRange(self, left: int, right: int) -> bool:
start = bisect_right(self.range, left)
end = bisect_left(self.range, right)
return start == end and start % 2 == 1
def removeRange(self, left: int, right: int) -> None:
start = bisect_left(self.range, left)
end = bisect_right(self.range, right)
new_range = []
if start % 2 == 1:
new_range.append(left)
if end % 2 == 1:
new_range.append(right)
self.range[start:end] = new_range
# 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)
addRange and removeRange functions look very alike.
The very first thing we do is looking for index (start & end) using bisect. It is very essential to notice that self.range[start:end] is affected by [left, right). In other words, we are basically finding start and end index of self.range that are affected by [left, right).
* bisect_left, bisect_right should be properly used to handle duplicates.
Next, self.range[start:end] is replaced by new_range. In my opinion, that is the beauty of this code. Both start and end index can be either odd or even. If they are even, it means they lie outside the existing ranges. On the contrary, if they are odd, it means they lie inside the existing ranges. So, for addRange function, among the two index (start & end), only even ones get to be in new_range. As a result, new range can have a form of [], [start], [end], [start, end].
The very same approach can be also used in the below problem as well.
https://leetcode.com/problems/amount-of-new-area-painted-each-day/
class Solution:
from bisect import bisect_left, bisect_right
def amountPainted(self, paint: List[List[int]]) -> List[int]:
self.ranges = []
ret = []
for left, right in paint:
ret.append(self.insertRange(left, right))
return ret
def insertRange(self, left, right):
start = bisect_left(self.ranges, left)
end = bisect_right(self.ranges, right)
residuals = []
new_range = []
if start % 2 == 0:
new_range.append(left)
residuals.append(left)
residuals += self.ranges[start:end]
if end % 2 == 0:
new_range.append(right)
residuals.append(right)
self.ranges[start:end] = new_range
ret = 0
for i in range(1, len(residuals), 2):
ret += residuals[i] - residuals[i-1]
return ret
'Computer Science > Coding Test' 카테고리의 다른 글
LeetCode: 1032. Stream of Characters (0) | 2022.03.25 |
---|---|
LeetCode: 2034. Stock Price Fluctuation (0) | 2022.03.23 |
LeetCode: 833. Find And Replace in String (0) | 2022.03.15 |
LeetCode: 772. Basic Calculator III (0) | 2022.03.11 |
LeetCode: 745. Prefix and Suffix Search (0) | 2022.03.10 |