Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
👨💻 Алгоритм:
1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.
2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.
3⃣Создайте новую строку, удалив все помеченные скобки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
👨💻 Алгоритм:
1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.
2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.
3⃣Создайте новую строку, удалив все помеченные скобки.
😎 Решение:
def minRemoveToMakeValid(s):
stack = []
s = list(s)
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
elif s[i] == ')':
if stack:
stack.pop()
else:
s[i] = ''
while stack:
s[stack.pop()] = ''
return ''.join(s)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 436. Find Right Interval
Сложность: medium
Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.
Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.
Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.
Пример:
👨💻 Алгоритм:
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 изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
Задача: 997. Find the Town Judge
Сложность: easy
В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Создание счетчиков доверия:
Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку.
2⃣Подсчет доверия:
Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют.
3⃣Проверка условий судьи:
Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 -1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 104. Maximum Depth of Binary Tree
Сложность: easy
Дан корень бинарного дерева, верните его максимальную глубину.
Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.
Пример:
👨💻 Алгоритм:
1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).
2️⃣Для данной задачи подойдет несколько способов.
3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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) + 1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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 в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Преобразуй число в строку для удобства работы с его цифрами.
Используй словарь для хранения соответствий цифр при повороте на 180 градусов.
2⃣Пройди по цифрам числа, проверяя, что все цифры действительны и заменяя их на соответствующие при повороте.
3⃣Проверь, что перевернутая строка отличается от исходной.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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_str
Ставь 👍 и забирай 📚 Базу знаний
Задача: 462. Minimum Moves to Equal Array Elements II
Сложность: medium
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 977. Squares of a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке.
Пример:
👨💻 Алгоритм:
1⃣Создайте массив квадратов каждого элемента.
2⃣Отсортируйте массив квадратов.
3⃣Верните отсортированный массив квадратов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 ans
Ставь 👍 и забирай 📚 Базу знаний
💊2
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка.
Инициализируйте lastMNode на голову связанного списка.
2⃣Итерация по списку:
Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.
Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.
Продолжайте итерацию по n узлам.
3⃣Удаление узлов:
Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка.
Инициализируйте lastMNode на голову связанного списка.
2⃣Итерация по списку:
Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.
Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.
Продолжайте итерацию по n узлам.
3⃣Удаление узлов:
Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.
😎 Решение:
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 head
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1043. Partition Array for Maximum Sum
Сложность: medium
Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1⃣Инициализация:
Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.
2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.
3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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]
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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 не находятся под одним и тем же именем хоста.
Пример:
👨💻 Алгоритм:
1⃣Извлечение имени хоста:
Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок.
2⃣Использование очереди для BFS:
Начинаем с начального URL и помещаем его в очередь.
Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста.
3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
👨💻 Алгоритм:
1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.
2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.
3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
👨💻 Алгоритм:
1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.
2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.
3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.
😎 Решение:
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] + k
Ставь 👍 и забирай 📚 Базу знаний
Задача: 409. Longest Palindrome
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
👨💻 Алгоритм:
1⃣Создайте словарь для подсчета количества каждого символа в строке.
2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.
3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 length
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1506. Find Root of N-Ary Tree
Сложность: medium
Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.
Верните корень N-арного дерева.
Пример:
👨💻 Алгоритм:
1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.
2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.
3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
👨💻 Алгоритм:
1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.
2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.
3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.
😎 Решение:
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 node
Ставь 👍 и забирай 📚 Базу знаний