Python | LeetCode

описание

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv

← к каналу @easy_python_task

9 194

подписчиков

Охват к подписчикам

10,4%

ERR

Реакции к просмотрам

0,04%

9 на 27 постов

Пересылки к просмотрам

0,42%

Постов в день

0,4

всего 21

Где отзываются чаще

доля реакций к просмотрам

12 авг.без подписи0,21%
4 июл.Задача: 503. Next Greater Element II Сложность: medium Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums. Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа. Пример: Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2. 👨‍💻 Алгоритм: 1⃣Инициализация Создайте массив res той же длины, что и nums, и заполните его значениями -1. 2⃣Поиск следующего большего элемента Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл. 3⃣Возврат результата Верните массив res. 😎 Решение: class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) res = [-1] * n for i in range(n): for j in range(1, n): if nums[(i + j) % n] > nums[i]: res[i] = nums[(i + j) % n] break return res Ставь 👍 и забирай 📚 Базу знаний0,20%
17 июл.Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний0,15%
26 июл.Задача: 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]))] Ставь 👍 и забирай 📚 Базу знаний0,15%
7 июл.Задача: 1263. Minimum Moves to Move a Box to Their Target Location Сложность: hard Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1. Пример: Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 3 👨‍💻 Алгоритм: 1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков. 2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков. 3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния. 😎 Решение: from collections import deque def minPushBox(grid): m, n = len(grid), len(grid[0]) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] def valid(x, y): return 0 <= x < m and 0 <= y < n and grid[x][y] != '#' def bfs(start): queue = deque([start]) visited = set([start]) while queue: px, py, bx, by, pushes = queue.popleft() if (bx, by) == target: return pushes for dx, dy in directions: npx, npy = px + dx, py + dy if valid(npx, npy) and (npx, npy, bx, by, pushes) not in visited: if (npx, npy) == (bx, by): nbx, nby = bx + dx, by + dy if valid(nbx, nby) and (npx, npy, nbx, nby, pushes + 1) not in visited: queue.append((npx, npy, nbx, nby, pushes + 1)) visited.add((npx, npy, nbx, nby, pushes + 1)) else: queue.append((npx, npy, bx, by, pushes)) visited.add((npx, npy, bx, by, pushes)) return -1 for i in range(m): for j in range(n): if grid[i][j] == 'S': player = (i, j) elif grid[i][j] == 'B': box = (i, j) elif grid[i][j] == 'T': target = (i, j) return bfs((*player, *box, 0)) Ставь 👍 и забирай 📚 Базу знаний0,14%
2 авг.Задача: 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:]) Ставь 👍 и забирай 📚 Базу знаний0,11%
28 июн.Задача: 389. Find the Difference Сложность: easy Даны две строки s и t. Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию. Верните букву, которая была добавлена в t. Пример: Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added. 👨‍💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение: class Solution: def findTheDifference(self, s: str, t: str) -> str: sorted_s = sorted(s) sorted_t = sorted(t) for i in range(len(sorted_s)): if sorted_s[i] != sorted_t[i]: return sorted_t[i] return sorted_t[len(sorted_s)] Ставь 👍 и забирай 📚 Базу знаний0,09%
12:11Онлайн-магистратура для IT: ИТМО, МИФИ + Яндекс Программы онлайн-магистратуры ИТМО и МИФИ в партнёрстве с Яндексом. Актуальные знания, практическое обучение и гибкий график. Учитесь, совмещая с работой. Доступна господдержка оплаты, отсрочка от армии Перейти на сайт #реклама 16+ practicum.yandex.ru О рекламодателе0,00%
11:06Задача: 971. Flip Binary Tree To Match Preorder Traversal Сложность: medium Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order. Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект: Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage. Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1]. Пример: Input: root = [1,2], voyage = [2,1] Output: [-1] Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage. 👨‍💻 Алгоритм: 1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1]. 2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка. 3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage. 😎 Решение: class Solution: def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]: self.flipped = [] self.index = 0 self.voyage = voyage self.dfs(root) if self.flipped and self.flipped[0] == -1: return [-1] return self.flipped def dfs(self, node): if node: if node.val != self.voyage[self.index]: self.flipped = [-1] return self.index += 1 if self.index < len(self.voyage) and node.left and node.left.val != self.voyage[self.index]: self.flipped.append(node.val) self.dfs(node.right) self.dfs(node.left) else: self.dfs(node.left) self.dfs(node.right) Ставь 👍 и забирай 📚 Базу знаний0,00%
14 авг.без подписи0,00%
12 авг.без подписи0,00%
12 авг.Задача: 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 Ставь 👍 и забирай 📚 Базу знаний0,00%