Python | LeetCode

#medium Задача: 311. Sparse Matrix Multiplication Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно. Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

👨‍💻 Алгоритм: 1⃣Инициализация результирующей матрицы Создайте результирующую матрицу result размером m x n, заполненную нулями. 2⃣Хранение ненулевых элементов Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map. 3⃣Вычисление произведения Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j]. 😎 Решение:

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        n = len(mat1)
        k = len(mat1[0])
        m = len(mat2[0])
        
        ans = [[0] * m for _ in range(n)]
        
        for rowIndex in range(n):
            for elementIndex in range(k):
                if mat1[rowIndex][elementIndex] != 0:
                    for colIndex in range(m):
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
        
        return ans

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 672. Bulb Switcher II Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность: Кнопка 1: Переключает состояние всех лампочек. Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...). Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...). Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...). Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия. Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок. Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

👨‍💻 Алгоритм: 1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны. 2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций. 3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества. 😎 Решение:

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        seen = set()
        n = min(n, 6)
        shift = max(0, 6 - n)
        for cand in range(16):
            bcount = bin(cand).count('1')
            if bcount % 2 == m % 2 and bcount <= m:
                lights = 0
                if ((cand >> 0) & 1) > 0: lights ^= 0b111111 >> shift
                if ((cand >> 1) & 1) > 0: lights ^= 0b010101 >> shift
                if ((cand >> 2) & 1) > 0: lights ^= 0b101010 >> shift
                if ((cand >> 3) & 1) > 0: lights ^= 0b100100 >> shift
                seen.add(lights)
        return len(seen)

Ставь 👍 и забирай 📚 Базу знаний

🧠 Machine Learning — авторский канал, где собрана вся база по ИИ и машинному обучению. Senior разработчик AI-алгоритмов и автономных агентов, разбирает гайды, редкую литературу и код топовых моделей машинного обучения и искусственного интеллекта. В 2025 году ИИ выйдет на совершенно новый уровень тот, кто не успеет за прогрессом - отстанет, а кто разберется - сорвет куш. Стоит подписаться: t.me/ai_machinelearning_big_data

#medium Задача: 310. Minimum Height Trees Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом. Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT). Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке. Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом. Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

👨‍💻 Алгоритм: 1⃣Создание списка смежности Создайте список смежности, представляющий граф. 2⃣Удаление листьев Начните с удаления всех листьев. Лист — это узел с одной гранью. В каждой итерации удаляйте текущие листья и обновляйте список смежности. Новые листья будут вершинами, которые стали листьями после удаления предыдущих листьев. 3⃣Повторение процесса Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT). 😎 Решение:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        
        from collections import defaultdict, deque
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        leaves = deque()
        for i in range(n):
            if len(adj[i]) == 1:
                leaves.append(i)
        remaining_nodes = n
        while remaining_nodes > 2:
            leaves_size = len(leaves)
            remaining_nodes -= leaves_size
            for _ in range(leaves_size):
                leaf = leaves.popleft()
                neighbor = adj[leaf].pop()
                adj[neighbor].remove(leaf)
                if len(adj[neighbor]) == 1:
                    leaves.append(neighbor)
        
        return list(leaves)

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 670. Maximum Swap Дано целое число num. Вы можете поменять местами две цифры не более одного раза, чтобы получить число с наибольшим значением. Верните число с наибольшим значением, которое можно получить. Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

👨‍💻 Алгоритм: 1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно. 2⃣Проверяем, что не добавили ведущий ноль. Фактически, проверять это не нужно, так как изначальное число его не содержит. 3⃣Возвращаем максимальное значение из всех кандидатов. 😎 Решение:

class Solution:
    def maximumSwap(self, num: int) -> int:
        A = list(str(num))
        ans = A[:]
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                A[i], A[j] = A[j], A[i]
                for k in range(len(A)):
                    if A[k] != ans[k]:
                        if A[k] > ans[k]:
                            ans = A[:]
                        break
                A[i], A[j] = A[j], A[i]
        return int(''.join(ans))

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 309. Best Time to Buy and Sell Stock with Cooldown Дан массив prices, где prices[i] — цена данной акции в i-й день. Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями: После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать). Пример:

Input: prices = [1]
Output: 0

👨‍💻 Алгоритм: 1⃣Инициализация состояний Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи. 2⃣Обновление состояний Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день. 3⃣Определение максимальной прибыли В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли. 😎 Решение:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        hold = -prices[0]
        sold = 0
        cooldown = 0
        
        for i in range(1, n):
            new_hold = max(hold, cooldown - prices[i])
            new_sold = hold + prices[i]
            new_cooldown = max(cooldown, sold)
            
            hold = new_hold
            sold = new_sold
            cooldown = new_cooldown
        
        return max(sold, cooldown)

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 669. Trim a Binary Search Tree Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ. Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ. Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

👨‍💻 Алгоритм: 1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла. 2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла. 3⃣В противном случае обрезаем обе стороны дерева. 😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        if root.val > high:
            return self.trimBST(root.left, low, high)
        if root.val < low:
            return self.trimBST(root.right, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 1530. Number of Good Leaf Nodes Pairs Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance. Верните количество хороших пар листовых узлов в дереве. Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

👨‍💻 Алгоритм: 1⃣ Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла. 2⃣ Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS. 3⃣ Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество. 😎 Решение🐍

class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        graph = defaultdict(list)
        leafNodes = set()
        self.traverseTree(root, None, graph, leafNodes)
        ans = 0
        for leaf in leafNodes:
            bfsQueue = deque([leaf])
            seen = set([leaf])
            for i in range(distance + 1):
                size = len(bfsQueue)
                for _ in range(size):
                    currNode = bfsQueue.popleft()
                    if currNode in leafNodes and currNode != leaf:
                        ans += 1
                    for neighbor in graph[currNode]:
                        if neighbor not in seen:
                            bfsQueue.append(neighbor)
                            seen.add(neighbor)
        return ans // 2

    def traverseTree(self, currNode, prevNode, graph, leafNodes):
        if not currNode:
            return
        if not currNode.left and not currNode.right:
            leafNodes.add(currNode)
        if prevNode:
            graph[prevNode].append(currNode)
            graph[currNode].append(prevNode)
        self.traverseTree(currNode.left, currNode, graph, leafNodes)
        self.traverseTree(currNode.right, currNode, graph, leafNodes)

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 565. Array Nesting Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1]. Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила: Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k. Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее. Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат. Верните длину самого длинного множества s[k]. Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

👨‍💻 Алгоритм: 1⃣Создайте массив для отслеживания посещенных элементов. 2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент. 3⃣Обновите максимальную длину найденного множества. 😎 Решение:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        visited = [False] * len(nums)
        max_length = 0
        
        for i in range(len(nums)):
            if not visited[i]:
                start = i
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_length = max(max_length, count)
        
        return max_length

Ставь 👍 и забирай 📚 Базу знаний

Учишь Python, но как дело доходит до собственного кода — всё, кирдык? 😥 На форумах только одно: «Больше практиковаться!» А толку? Ноль понимания и никакой поддержки от профи… Плавали - знаем)) Поэтому специально для тебя - чат Python-щиков 🤝 Что получишь? 1️⃣ Сможешь задавать любые вопросы без страха и осуждения и получать ответы за минуты, а не часы поиска в инете 2️⃣ Регулярные плюшки в виде стримов от препода с 15-ти летним опытом 3️⃣ Общение с единомышленниками и заряд мотивации ➡️ А еще, забирай в закрепе БЕСПЛАТНЫЙ вводный курс по Python Короче, всё для прокачки! Залетай к нам — ссылка на чат (тык)

#easy Задача: 563. Binary Tree Tilt Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева. Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка. Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла. 2⃣Для каждого узла вычислите сумму значений левого и правого поддерева, а также их наклон, добавляя наклон к общей сумме. 3⃣Верните общую сумму наклонов всех узлов. 😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.total_tilt = 0
        
        def sum_and_tilt(node):
            if not node:
                return 0
            left_sum = sum_and_tilt(node.left)
            right_sum = sum_and_tilt(node.right)
            node_tilt = abs(left_sum - right_sum)
            self.total_tilt += node_tilt
            return node.val + left_sum + right_sum
        
        sum_and_tilt(root)
        return self.total_tilt

Ставь 👍 и забирай 📚 Базу знаний

📊 Реклама в сети телеграм каналов easyoffer ✈️ Для заказа пишите @easyoffer_adv easyoffer Backend Python | Вопросы Python | Удалёнка Python | LeetCode Python | Тесты Frontend | Вопросы Frontend | Удалёнка JavaScript | LeetCode Frontend | Тесты Java | Вопросы Java | Удалёнка Java | LeetCode Java | Тесты Тестировщик | Вопросы Тестировщик | Удалёнка Тестировщик | Тесты Data Science | Вопросы Data Science | Удалёнка Data Science | Тесты C# | Вопросы C# | Удалёнка C# | LeetCode C# | Тесты C/C++ | Вопросы C/C++ | Удалёнка C/C++ | LeetCode C/C++ | Тесты Golang | Вопросы Golang | Удалёнка Golang | LeetCode Golang | Тесты DevOps | Вопросы DevOps | Удалёнка DevOps | Тесты PHP | Вопросы PHP | Удалёнка PHP | LeetCode PHP | Тесты Kotlin | Вопросы Kotlin | Удалёнка Kotlin | LeetCode Kotlin | Тесты Swift | Вопросы Swift | Удалёнка Swift | LeetCode Swift | Тесты 📊 Реклама в сети телеграм каналов easyoffer ✈️ Для заказа пишите @easyoffer_adv

#medium Задача: 562. Longest Line of Consecutive One in Matrix Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице. Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной. Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

👨‍💻 Алгоритм: 1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal. 2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии. 3⃣Верните максимальную длину. 😎 Решение:

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return 0
        
        m, n = len(mat), len(mat[0])
        max_length = 0
        
        horizontal = [[0] * n for _ in range(m)]
        vertical = [[0] * n for _ in range(m)]
        diagonal = [[0] * n for _ in range(m)]
        anti_diagonal = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    horizontal[i][j] = (horizontal[i][j-1] if j > 0 else 0) + 1
                    vertical[i][j] = (vertical[i-1][j] if i > 0 else 0) + 1
                    diagonal[i][j] = (diagonal[i-1][j-1] if i > 0 and j > 0 else 0) + 1
                    anti_diagonal[i][j] = (anti_diagonal[i-1][j+1] if i > 0 and j < n-1 else 0) + 1
                    
                    max_length = max(max_length, horizontal[i][j], vertical[i][j], diagonal[i][j], anti_diagonal[i][j])
        
        return max_length

Ставь 👍 и забирай 📚 Базу знаний

#easy Задача: 561. Array Partition Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму. Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив nums в неубывающем порядке. 2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого). 3⃣Суммируйте выбранные элементы и верните эту сумму. 😎 Решение:

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[i] for i in range(0, len(nums), 2))

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 560. Subarray Sum Equals K Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k. Подмассив - это непрерывная непустая последовательность элементов внутри массива. Пример:

Input: nums = [1,1,1], k = 2
Output: 2

👨‍💻 Алгоритм: 1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums. 2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k. 3⃣Всякий раз, когда сумма равна k, увеличить счетчик, используемый для хранения необходимого результата. 😎 Решение:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        for start in range(len(nums)):
            for end in range(start + 1, len(nums) + 1):
                sum_ = sum(nums[start:end])
                if sum_ == k:
                    count += 1
        return count

Ставь 👍 и забирай 📚 Базу знаний

#easy Задача: 559. Maximum Depth of N-ary Tree Дано n-арное дерево, найдите его максимальную глубину. Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла. Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры). Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

👨‍💻 Алгоритм: 1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии. 2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search). 3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину. 😎 Решение:

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        elif not root.children:
            return 1
        else:
            heights = [self.maxDepth(child) for child in root.children]
            return max(heights) + 1

Ставь 👍 и забирай 📚 Базу знаний

#hard Задача: 632. Smallest Range Covering Elements from K Lists У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c. Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

👨‍💻 Алгоритм: 1⃣Инициализация и сбор всех начальных элементов Создайте массив для хранения текущих индексов каждого списка и используйте минимальную кучу для отслеживания текущих минимальных элементов из каждого списка. 2⃣Нахождение минимального диапазона Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов. 3⃣Проверка и обновление диапазона Продолжайте обновлять кучу и диапазон, пока возможно. Завершите, когда один из списков исчерпан. 😎 Решение:

from heapq import heappop, heappush

def smallestRange(nums):
    min_heap = []
    max_value = float('-inf')
    
    for i in range(len(nums)):
        heappush(min_heap, (nums[i][0], i, 0))
        max_value = max(max_value, nums[i][0])
    
    range_start, range_end = float('-inf'), float('inf')
    
    while len(min_heap) == len(nums):
        min_value, row, col = heappop(min_heap)
        
        if max_value - min_value < range_end - range_start:
            range_start, range_end = min_value, max_value
        
        if col + 1 < len(nums[row]):
            heappush(min_heap, (nums[row][col + 1], row, col + 1))
            max_value = max(max_value, nums[row][col + 1])
    
    return [range_start, range_end]

Ставь 👍 и забирай 📚 Базу знаний

#hard Задача: 358. Rearrange String k Distance Apart Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "". Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

👨‍💻 Алгоритм: 1⃣Создайте словарь частот для символов строки и определите максимальную частоту. 2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов. 3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку. 😎 Решение:

from collections import defaultdict

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = defaultdict(int)
        max_freq = 0
        
        for char in s:
            freqs[char] += 1
            max_freq = max(max_freq, freqs[char])
        
        most_chars = {char for char, freq in freqs.items() if freq == max_freq}
        second_chars = {char for char, freq in freqs.items() if freq == max_freq - 1}
        
        segments = [list() for _ in range(max_freq)]
        
        for i in range(max_freq):
            for char in most_chars:
                segments[i].append(char)
            if i < max_freq - 1:
                for char in second_chars:
                    segments[i].append(char)
        
        segment_id = 0
        
        for char, freq in freqs.items():
            if char in most_chars or char in second_chars:
                continue
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)
        
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""
        
        return "".join("".join(segment) for segment in segments)

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 435. Non-overlapping Intervals Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались. Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

👨‍💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans

Ставь 👍 и забирай 📚 Базу знаний

#hard Задача: 631. Design Excel Sum Formula Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти. Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

👨‍💻 Алгоритм: 1⃣Инициализация Создайте класс Excel, который будет инициализировать матрицу нужного размера и хранить текущие значения ячеек. Реализуйте методы для установки значений, получения значений и вычисления суммы. 2⃣Метод установки значений Реализуйте метод set, который будет изменять значение ячейки в матрице. 3⃣Метод вычисления суммы Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек. 😎 Решение:

class Excel:

    def __init__(self, height: int, width: str):
        self.mat = [[0] * (ord(width) - ord('A') + 1) for _ in range(height)]
        self.formulas = {}

    def set(self, row: int, column: str, val: int) -> None:
        self.mat[row - 1][ord(column) - ord('A')] = val
        self.formulas.pop((row, column), None)

    def get(self, row: int, column: str) -> int:
        if (row, column) in self.formulas:
            return self._evaluate_formula(row, column)
        return self.mat[row - 1][ord(column) - ord('A')]

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        self.formulas[(row, column)] = numbers
        return self._evaluate_formula(row, column)

    def _evaluate_formula(self, row: int, column: str) -> int:
        total = 0
        for number in self.formulas[(row, column)]:
            if ':' in number:
                start, end = number.split(':')
                start_row, start_col = int(start[1:]), start[0]
                end_row, end_col = int(end[1:]), end[0]
                for r in range(start_row, end_row + 1):
                    for c in range(ord(start_col), ord(end_col) + 1):
                        total += self.get(r, chr(c))
            else:
                r, c = int(number[1:]), number[0]
                total += self.get(r, c)
        return total

Ставь 👍 и забирай 📚 Базу знаний