Python | LeetCode

Задача: 987. Vertical Order Traversal of a Binary Tree Сложность: medium Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным. Верните пересечение этих двух списков интервалов. Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b. Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3]. Пример: Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] 👨‍💻 Алгоритм: 1⃣Инициализация указателей: Создать словарь для хранения узлов по их координатам (col, row). Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)). 2⃣Поиск пересечений: Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row). Добавить левый потомок в очередь с координатами (row + 1, col - 1). Добавить правый потомок в очередь с координатами (row + 1, col + 1). 3⃣Возврат результата: Отсортировать ключи словаря по col и затем по row. Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список. 😎 Решение: from collections import defaultdict, deque class Solution: def verticalTraversal(self, root): col_table = defaultdict(list) queue = deque([(root, 0, 0)]) while queue: node, row, col = queue.popleft() if node: col_table[col].append((row, node.val)) queue.append((node.left, row + 1, col - 1)) queue.append((node.right, row + 1, col + 1)) result = [] for col in sorted(col_table.keys()): col_table[col].sort() result.append([val for row, val in col_table[col]]) return result Ставь 👍 и забирай 📚 Базу знаний

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример: Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. 👨‍💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер. 2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1. 3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1. 😎 Решение: class Solution: def largestIsland(self, grid: List[List[int]]) -> int: def dfs(r, c, index): ans = 1 grid[r][c] = index for nr, nc in neighbors(r, c): if grid[nr][nc] == 1: grid[nr][nc] = index ans += dfs(nr, nc, index) return ans def neighbors(r, c): for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]: nr, nc = r + dr, c + dc if 0 <= nr < N and 0 <= nc < N: yield nr, nc N = len(grid) index = 2 area = [0] * (N * N + 2) for r in range(N): for c in range(N): if grid[r][c] == 1: area[index] = dfs(r, c, index) index += 1 ans = max(area) for r in range(N): for c in range(N): if grid[r][c] == 0: seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1} ans = max(a Ставь 👍 и забирай 📚 Базу знаний

Задача: 1209. Remove All Adjacent Duplicates in String II Сложность: medium Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе. Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать. Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален. Пример: Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa" 👨‍💻 Алгоритм: 1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов. 2⃣Перемещать быстрый указатель i по строке s: Копировать s[i] в s[j]. Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека. Иначе добавить 1 в стек. Если количество символов равно k, уменьшить j на k и извлечь из стека. 3⃣Вернуть первые j символов строки. 😎 Решение: class Solution: def removeDuplicates(self, s: str, k: int) -> str: counts = [] sa = list(s) j = 0 for i in range(len(sa)): sa[j] = sa[i] if j == 0 or sa[j] != sa[j - 1]: counts.append(1) else: incremented = counts.pop() + 1 if incremented == k: j -= k else: counts.append(incremented) j += 1 return "".join(sa[:j]) Ставь 👍 и забирай 📚 Базу знаний

Задача: 300. Longest Increasing Subsequence Сложность: medium Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности. Пример: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение: class Solution: def lengthOfLIS(self, nums: list[int]) -> int: if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) Ставь 👍 и забирай 📚 Базу знаний

Задача: 968. Binary Tree Cameras Сложность: hard Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми. Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева. Пример: Input: root = [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement. 👨‍💻 Алгоритм: 1⃣Рекурсивное решение (solve): Для каждого узла определите три состояния: - [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел. - [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры. - [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера. Рассчитайте эти состояния для левого и правого поддеревьев. 2⃣Рассчёт состояний: Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1. Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2. Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии. 3⃣Минимальное количество камер: Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2. 😎 Решение: class Solution: def minCameraCover(self, root: TreeNode) -> int: def solve(node): if not node: return 0, 0, float('inf') L = solve(node.left) R = solve(node.right) mL12 = min(L[1], L[2]) mR12 = min(R[1], R[2]) d0 = L[1] + R[1] d1 = min(L[2] + mR12, R[2] + mL12) d2 = 1 + min(L[0], mL12) + min(R[0], mR12) return d0, d1, d2 return min(solve(root)[1:]) Ставь 👍 и забирай 📚 Базу знаний

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,4,7],[2,5,8],[3,6,9]] 👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение: class Solution: def transpose(self, A): return [[A[r][c] for r in range(len(A))] for c in range(len(A[0]))] Ставь 👍 и забирай 📚 Базу знаний

Задача: 1248. Count Number of Nice Subarrays Сложность: medium Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример: Input: arr = [1,2] Output: 2 👨‍💻 Алгоритм: 1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1. 2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц. 3⃣Подсчитайте количество таких подмассивов и верните этот результат. 😎 Решение: def numberOfSubarrays(nums, k): def atMost(nums, k): count = 0 left = 0 res = 0 for right in range(len(nums)): if nums[right] % 2 == 1: count += 1 while count > k: if nums[left] % 2 == 1: count -= 1 left += 1 res += right - left + 1 return res return atMost(nums, k) - atMost(nums, k - 1) Ставь 👍 и забирай 📚 Базу знаний

Задача: 1057. Campus Bikes Сложность: medium В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример: Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0] 👨‍💻 Алгоритм: 1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список. 2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда. Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы. 3⃣Заполни и верни массив назначений. 😎 Решение: def assignBikes(workers, bikes): pairs = [] for i, (wx, wy) in enumerate(workers): for j, (bx, by) in enumerate(bikes): distance = abs(wx - bx) + abs(wy - by) pairs.append((distance, i, j)) pairs.sort() result = [-1] * len(workers) bike_taken = [False] * len(bikes) worker_assigned = [False] * len(workers) for distance, worker_idx, bike_idx in pairs: if not worker_assigned[worker_idx] and not bike_taken[bike_idx]: result[worker_idx] = bike_idx bike_taken[bike_idx] = True worker_assigned[worker_idx] = True return result Ставь 👍 и забирай 📚 Базу знаний

Задача: 418. Sentence Screen Fitting Сложность: medium Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом. Пример: Input: sentence = ["hello","world"], rows = 2, cols = 8 Output: 1 👨‍💻 Алгоритм: 1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце. 2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов. 3⃣Если следующая позиция является пробелом, увеличивайте счетчик. Если нет, уменьшайте счетчик, пока не найдете пробел, чтобы избежать разрыва слова. 😎 Решение: def wordsTyping(sentence, rows, cols): sentence_str = " ".join(sentence) + " " length = len(sentence_str) pos = 0 for _ in range(rows): pos += cols if sentence_str[pos % length] == " ": pos += 1 else: while pos > 0 and sentence_str[(pos - 1) % length] != " ": pos -= 1 return pos // length Ставь 👍 и забирай 📚 Базу знаний

Задача: 1024. Video Stitching Сложность: medium Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1. Пример: Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10 Output: 3 👨‍💻 Алгоритм: 1⃣Сортировка клипов: Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке. 2⃣Выбор клипов: Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон. Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1. 3⃣Проверка покрытия: Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1. 😎 Решение: class Solution { public: int videoStitching(vector<vector<int>>& clips, int T) { sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]); }); int end = -1, end2 = 0, res = 0; for (const auto& clip : clips) { if (end2 >= T || clip[0] > end2) break; if (end < clip[0] && clip[0] <= end2) { res++; end = end2; } end2 = max(end2, clip[1]); } return end2 >= T ? res : -1; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 652. Find Duplicate Subtrees Сложность: medium Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов. Пример: Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] 👨‍💻 Алгоритм: 1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева. 2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления. 3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев. 😎 Решение: from collections import defaultdict class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def findDuplicateSubtrees(root): def serialize(node): if not node: return "#" serial = f"{node.val},{serialize(node.left)},{serialize(node.right)}" count[serial] += 1 if count[serial] == 2: result.append(node) return serial count = defaultdict(int) result = [] serialize(root) return result Ставь 👍 и забирай 📚 Базу знаний

Задача: 716. Max Stack Сложность: hard Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример: Input ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] Output [null, null, null, null, 5, 5, 1, 5, 1, 5] 👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение: class MaxStack: def __init__(self): self.stack = [] self.max_stack = [] def push(self, x): self.stack.append(x) if not self.max_stack or x >= self.max_stack[-1]: self.max_stack.append(x) def pop(self): x = self.stack.pop() if x == self.max_stack[-1]: self.max_stack.pop() return x def top(self): return self.stack[-1] def peekMax(self): return self.max_stack[-1] def popMax(self): max_val = self.max_stack.pop() buffer = [] while self.stack[-1] != max_val: buffer.append(self.stack.pop()) self.stack.pop() while buffer: self.push(buffer.pop()) return max_val Ставь 👍 и забирай 📚 Базу знаний