Python | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多
网络:8 970
订阅者
-1024 小时
-327 天
-10330 天
帖子存档
8 970
Задача: 641. Design Circular Deque
Сложность: medium
Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.
Пример:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4]👨💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:
class MyCircularDeque:
def __init__(self, k: int):
self.k = k
self.deque = [0] * k
self.front = 0
self.rear = 0
self.size = 0
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.front = (self.front - 1) % self.k
self.deque[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
self.deque[self.rear] = value
self.rear = (self.rear + 1) % self.k
self.size += 1
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.k
self.size -= 1
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.rear = (self.rear - 1 + self.k) % self.k
self.size -= 1
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.deque[self.front]
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.deque[(self.rear - 1 + self.k) % self.k]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.k8 970
Нужны 7 желающих для работы с искусственным интеллектом.
Работа из дома. График свободный.
Пришло задание — изучили — выполнили — получили свои деньги.
Деньги вы получаете в зависимости от сложности задания. Например:
За задание могут платить 500-10.000 рублей.
В зависимости от сложности.
500 рублей — это около 5-30 минут.
10 000 руб. это 5-6 часов.
Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д.
💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т.
Мы обучим вас сами:
— 3 дня уроков по 30 минут
— Домашки с проверкой
⚡ Набор заканчивается завтра.
Для регистрации жмите кнопку "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
neuromachina.ru
О рекламодателе
8 970
Задача: 1506. Find Root of N-Ary Tree
Сложность: medium
Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.
Верните корень N-арного дерева.
Пример:
Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.class Solution:
def findRoot(self, tree: List['Node']) -> 'Node':
seen = set()
for node in tree:
for child in node.children:
seen.add(child.val)
for node in tree:
if node.val not in seen:
return node8 970
Получите удаленную подработку, где платят 5.000 ₽ в день
Нужно заполнять карточки товаров на ВБ, писать описания товаров и отвечать на отзывы.
Все это вы делаете из дома. Бесплатная регистрация только сегодня!
Опыт, знания и город — не важны! От вас требуется только телефон.
Занятость 3-6 часов в день.
График свободный. Заработок зависит от вас. Над вами нет никаких начальников. А самое важное, у вас не будет нужды просыпаться в 6 утра на работу.
Для старта в профессии нужно пройти бесплатное 3х-дневное обучение:
✅ Прямые эфиры, где вы поймете суть профессии
✅ Домашки с проверкой и оплатой бонусами
✅ Платим 10 тыс за каждую выполненную домашку
Все кто пройдет курс, получат сертификат от школы с образовательной лицензией.
⚡ Начинаем в понедельник!
Жмите снизу "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
course.wildcard.ru
О рекламодателе
8 970
Задача: 409. Longest Palindrome
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
Input: s = "abccccdd" Output: 7👨💻 Алгоритм: 1⃣Создайте словарь для подсчета количества каждого символа в строке. 2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома. 3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа. 😎 Решение:
def longestPalindrome(s):
charCount = {}
for char in s:
charCount[char] = charCount.get(char, 0) + 1
length = 0
oddFound = False
for count in charCount.values:
if count % 2 == 0:
length += count
else:
length += count - 1
oddFound = True
return length + 1 if oddFound else length8 970
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
if k <= arr[0] - 1:
return k
k -= arr[0] - 1
n = len(arr)
for i in range(n - 1):
currMissing = arr[i + 1] - arr[i] - 1
if k <= currMissing:
return arr[i] + k
k -= currMissing
return arr[-1] + k8 970
Задача: 1236. Web Crawler
Сложность: medium
Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы http://leetcode.com/problems и http://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы http://example.org/test и http://example.com/abc не находятся под одним и тем же именем хоста.
Пример:
Input: urls = [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.google.com", "http://news.yahoo.com/us" ] edges = [[2,0],[2,1],[3,2],[3,1],[0,4]] startUrl = "http://news.yahoo.com/news/topics/" Output: [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.yahoo.com/us" ]👨💻 Алгоритм: 1⃣Извлечение имени хоста: Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок. 2⃣Использование очереди для BFS: Начинаем с начального URL и помещаем его в очередь. Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста. 3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную. 😎 Решение:
class HtmlParser:
def getUrls(self, url: str) -> [str]:
pass
def extractHostname(url):
from urllib.parse import urlparse
parsed_url = urlparse(url)
return parsed_url.netloc
def crawl(startUrl: str, htmlParser: HtmlParser) -> [str]:
from collections import deque
hostname = extractHostname(startUrl)
visited = set()
queue = deque([startUrl])
visited.add(startUrl)
while queue:
url = queue.popleft()
for next_url in htmlParser.getUrls(url):
if next_url not in visited and extractHostname(next_url) == hostname:
visited.add(next_url)
queue.append(next_url)
return list(visited)8 970
Задача: 1043. Partition Array for Maximum Sum
Сложность: medium
Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84👨💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:
def maxSumAfterPartitioning(arr, k):
n = len(arr)
dp = [0] * n
for i in range(n):
max_val = 0
for j in range(1, k + 1):
if i - j + 1 >= 0:
max_val = max(max_val, arr[i - j + 1])
if i - j >= 0:
dp[i] = max(dp[i], dp[i - j] + max_val * j)
else:
dp[i] = max(dp[i], max_val * j)
return dp[-1]8 970
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
currentNode = head
lastMNode = head
while currentNode:
mCount, nCount = m, n
while currentNode and mCount > 0:
lastMNode = currentNode
currentNode = currentNode.next
mCount -= 1
while currentNode and nCount > 0:
currentNode = currentNode.next
nCount -= 1
lastMNode.next = currentNode
return head8 970
От гипотезы до сделки — в одной инфраструктуре
⚡ «Финам» собрал сервисы алготрейдера так, что выход одного становится входом следующего: AI-скринер находит кандидатов по 200+ метрикам, «машина времени» проверяет гипотезы, Spread Insight сторожит арбитражные спреды, Trade API доводит до исполнения.
• Бесплатные курсы, медиа и разборы кейсов
• Поддержка инженеров по каждому звену
• Конкурсы: сравните свой алгоритм с другими в равных условиях
✅ Запустите первую сквозную стратегию в одном контуре.
Информация не является индивидуальной инвестиционной рекомендацией и не гарантирует доходности. Инвестиции связаны с риском.
Перейти на сайт
Финансовые услуги оказывает: АО «Инвестиционная компания «ФИНАМ».
#реклама 16+
broker.finam.ru
О рекламодателе
8 970
Задача: 977. Squares of a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке.
Пример:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].👨💻 Алгоритм: 1⃣Создайте массив квадратов каждого элемента. 2⃣Отсортируйте массив квадратов. 3⃣Верните отсортированный массив квадратов. 😎 Решение:
class Solution:
def sortedSquares(self, nums: list[int]) -> list[int]:
ans = [num * num for num in nums]
ans.sort()
return ans8 970
Вся правда о комиссиях — от ИИ на данных FinamTrade
ИИ-агенты забираются в банковские процессы — а ваши счета пока разбираются вручную. Считать вручную долго.
💻 Finam MCP передаёт ваши счета, позиции и историю сделок в привычный AI-клиент (ChatGPT, Claude и др.). Дальше вы просто спрашиваете ИИ: динамика портфеля, прибыль и убытки, комиссии, графики — ответ по реальным данным FinamTrade.
• Счета, история сделок и заявок — прямо в чате с ИИ
• Интерактивные графики, списки наблюдения, заметки
• Несколько счетов в одном запросе, работает и с демо
• Токен за пару минут в FinamTrade, сервис бесплатный
✅ Дополнительный софт не нужен. Сгенерируйте MCP-токен и задайте ИИ первый вопрос о своих сделках.
Информация не является индивидуальной инвестиционной рекомендацией и не гарантирует доходности. Инвестиции связаны с риском.
Попробовать
Финансовые услуги оказывает: АО «Инвестиционная компания «ФИНАМ».
#реклама 16+
broker.finam.ru
О рекламодателе
8 970
Задача: 462. Minimum Moves to Equal Array Elements II
Сложность: medium
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]👨💻 Алгоритм: 1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива. 2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k. 3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом. 😎 Решение:
class Solution:
def minMoves2(self, nums: List[int]) -> int:
ans = float('inf')
minval = min(nums)
maxval = max(nums)
for i in range(minval, maxval + 1):
sum_moves = 0
for num in nums:
sum_moves += abs(num - i)
ans = min(ans, sum_moves)
return int(ans)8 970
Встречай смартфон Honor — с выгодой для себя!
✅ Стильный дизайн
✅ Заряд надолго
✅ Качественные фото
✅ Быстрая и плавная работа
Выбирай свой Honor по привлекательной цене!
Купить
#реклама
market.yandex.ru
О рекламодателе
8 970
Задача: 1056. Confusing Number
Сложность: easy
Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.
Пример:
Input: n = 6 Output: true👨💻 Алгоритм: 1⃣Преобразуй число в строку для удобства работы с его цифрами. Используй словарь для хранения соответствий цифр при повороте на 180 градусов. 2⃣Пройди по цифрам числа, проверяя, что все цифры действительны и заменяя их на соответствующие при повороте. 3⃣Проверь, что перевернутая строка отличается от исходной. 😎 Решение:
def isConfusingNumber(n):
rotation_map = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
n_str = str(n)
rotated_str = ""
for char in n_str:
if char not in rotation_map:
return False
rotated_str = rotation_map[char] + rotated_str
return rotated_str != n_str8 970
Задача: 104. Maximum Depth of Binary Tree
Сложность: easy
Дан корень бинарного дерева, верните его максимальную глубину.
Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: 3👨💻 Алгоритм: 1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2️⃣Для данной задачи подойдет несколько способов. 3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 18 970
Криптошок и рекорд США — дислокации не ищут вручную
⚡ Spread Insight: монитор арбитражных аномалий на МосБирже и криптобиржах, конструктор спредов любой сложности, бэктест на истории, AI-помощник для формул и разбора идей.
• Скринер аномалий: коинтеграция, отклонения, потенциал по историческим данным
• Своя пара из акций, фьючерсов, валют или крипты
• Калькулятор позиции с учётом комиссий
• Алерты в Telegram, когда спред выходит за рамки
✅ Включите мониторинг своих спредов в Spread Insight.
Информация не является индивидуальной инвестиционной рекомендацией и не гарантирует доходности. Инвестиции связаны с риском.
Перейти на сайт
Финансовые услуги оказывает: АО «Инвестиционная компания «ФИНАМ».
#реклама 16+
broker.finam.ru
О рекламодателе
8 970
Задача: 997. Find the Town Judge
Сложность: easy
В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Создание счетчиков доверия: Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку. 2⃣Подсчет доверия: Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют. 3⃣Проверка условий судьи: Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1. 😎 Решение:
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if not trust and n == 1:
return 1
trust_count = [0] * (n + 1)
trusted_by = [0] * (n + 1)
for a, b in trust:
trust_count[a] += 1
trusted_by[b] += 1
for i in range(1, n + 1):
if trust_count[i] == 0 and trusted_by[i] == n - 1:
return i
return -18 970
Аналитика портфеля без смены брокера: «Финам AI-скринер»
📊 Менять брокера ради аналитики больше не нужно: «Финам AI-скринер» подключает счёт у стороннего брокера по токену на чтение и отдаёт диагностику по каждой бумаге. Функция бесплатная, подключение занимает пару минут.
• 15+ умных сигналов по акциям и облигациям
• Прогнозы по трём ценовым сценариям
• Рейтинг риска и доходности, расчёт дивидендов и купонов
• Виртуальные портфели: проверьте идею без реальных денег
✅ Добавьте счёт в AI-скринер и пройдите диагностику портфеля.
Информация не является индивидуальной инвестиционной рекомендацией и не гарантирует доходности. Инвестиции связаны с риском.
Попробовать
Финансовые услуги оказывает: АО «Инвестиционная компания «ФИНАМ».
#реклама 16+
broker.finam.ru
О рекламодателе
8 970
Задача: 436. Find Right Interval
Сложность: medium
Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.
Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.
Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.
Пример:
Input: intervals = [[1,2]] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.👨💻 Алгоритм: 1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j. 2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже. 3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки. 😎 Решение:
class Solution:
def findRightInterval(self, intervals):
endIntervals = intervals[:]
hash = {tuple(interval): i for i, interval in enumerate(intervals)}
intervals.sort(key=lambda x: x[0])
endIntervals.sort(key=lambda x: x[1])
j = 0
res = [-1] * len(intervals)
for i in range(len(endIntervals)):
while j < len(intervals) and intervals[j][0] < endIntervals[i][1]:
j += 1
res[hash[tuple(endIntervals[i])]] = -1 if j == len(intervals) else hash[tuple(intervals[j])]
return res