Сложность: hard
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
👨💻 Алгоритм:
1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.
2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.
3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.
😎 Решение:
class RangeModule:
def __init__(self):
self.ranges = []
def addRange(self, left, right):
new_ranges = []
i = 0
while i < len(self.ranges) and self.ranges[i][1] < left:
new_ranges.append(self.ranges[i])
i += 1
while i < len(self.ranges) and self.ranges[i][0] <= right:
left = min(left, self.ranges[i][0])
right = max(right, self.ranges[i][1])
i += 1
new_ranges.append((left, right))
while i < len(self.ranges):
new_ranges.append(self.ranges[i])
i += 1
self.ranges = new_ranges
def queryRange(self, left, right):
for l, r in self.ranges:
if l <= left and right <= r:
return True
return False
def removeRange(self, left, right):
new_ranges = []
for l, r in self.ranges:
if l < left:
new_ranges.append((l, min(r, left)))
if right < r:
new_ranges.append((max(l, right), r))
self.ranges = new_ranges
Ставь 👍 и забирай 📚 Базу знаний