Python | LeetCode

Задача: 1463. Cherry Pickup II Сложность: hard Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j). У вас есть два робота, которые могут собирать вишни: Робот №1 находится в левом верхнем углу (0, 0), а Робот №2 находится в правом верхнем углу (0, cols - 1). Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам: Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1). Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой. Когда оба робота находятся в одной клетке, только один из них собирает вишни. Оба робота не могут выходить за пределы матрицы в любой момент времени. Оба робота должны достичь нижней строки в матрице grid. Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

👨‍💻 Алгоритм: 1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2). 2⃣Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов. 3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов. 😎 Решение:

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[0] * n for _ in range(n)] for _ in range(m)]
        
        for row in range(m - 1, -1, -1):
            for col1 in range(n):
                for col2 in range(n):
                    result = grid[row][col1]
                    if col1 != col2:
                        result += grid[row][col2]
                    if row != m - 1:
                        max_cherries = 0
                        for new_col1 in range(col1 - 1, col1 + 2):
                            for new_col2 in range(col2 - 1, col2 + 2):
                                if 0 <= new_col1 < n and 0 <= new_col2 < n:
                                    max_cherries = max(max_cherries, dp[row + 1][new_col1][new_col2])
                        result += max_cherries
                    dp[row][col1][col2] = result
        return dp[0][0][n - 1]

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

Профессия «Аналитик данных». Рассрочка 0% Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 официальный государственный диплом 🎓если после курса не найдёте работу — мы возвращаем деньги и это зафиксировано в договоре 🎓 рассрочка 0% на 24 мес., то есть без переплаты 🎓 бессрочный доступ к лекциям и материалам, которые продолжают обновляться 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше Финансовые услуги оказывает: ПАО "Сбербанк", АО "Тинькофф Банк" и др.. #реклама 16+ eduson.academy О рекламодателе

Задача: 27. Remove Element Сложность: easy Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val. Учитывайте количество элементов в nums, которые не равны val как k. Чтобы вас приняли, вам необходимо сделать следующее: - Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums. - Вернуть k. Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2, nums = [2,2,_,_]  

👨‍💻 Алгоритм: 1️⃣Инициализируем указатель k для отслеживания позиции уникальных элементов. 2️⃣Проходим по массиву, копируя элементы, которые не равны val, на место указателя k. 3️⃣Возвращаем k — количество элементов, не равных val. 😎 Решение:

class Solution:  
    def removeElement(self, nums: List[int], val: int) -> int:  
        k = 0  

        for i in range(len(nums)):  
            if nums[i] != val:  
                nums[k] = nums[i]  
                k += 1  

        return k

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Подать заявку #реклама 16+ eduson.academy О рекламодателе

Задача: 563. Binary Tree Tilt Сложность: easy Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева. Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 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

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 133. Clone Graph Сложность: medium Дана ссылка на узел в связанном неориентированном графе. Верните глубокую копию (клон) графа. Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей. Пример:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

👨‍💻 Алгоритм: 1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов. 2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных. 3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла. 😎 Решение:

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        if not node:
            return node

        visited = {}
        queue = deque([node])
        visited[node] = Node(node.val, [])

        while queue:
            n = queue.popleft()
            for neighbor in n.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val, [])
                    queue.append(neighbor)
                visited[n].neighbors.append(visited[neighbor])
        return visited[node]

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

Как атакуют разработчиков? DevSecOps-трек на IT IS conf ИИнновации в безопасной разработке: как атакуют и спасают разработчика. На примерах из практики Денис Макрушин — директор по продуктам безопасной разработки в Yandex, расскажет, как распознавать такие угрозы и выстраивать устойчивость внутри разработки. • Ключевые угрозы и точки компрометации в процессе разработки • Подходы к снижению рисков на этапе SDLC • Без маркетинга — только применимые решения Выступление состоится 19 июня. Узнать больше #реклама 16+ itisconf.ru О рекламодателе

Задача: 1531. String Compression II Сложность: hard Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной. Найдите минимальную длину сжатой версии строки s после удаления не более k символов. Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм: 1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования. 2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить. 3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия. 😎 Решение:

class Solution:
    def __init__(self):
        self.memo = {}
        self.add = {1, 9, 99}

    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        return self.dp(s, 0, chr(ord('a') + 26), 0, k)

    def dp(self, s: str, idx: int, last_char: str, last_char_count: int, k: int) -> int:
        if k < 0:
            return float('inf') / 2

        if idx == len(s):
            return 0

        key = idx * 101 * 27 * 101 + (ord(last_char) - ord('a')) * 101 * 101 + last_char_count * 101 + k

        if key in self.memo:
            return self.memo[key]

        delete_char = self.dp(s, idx + 1, last_char, last_char_count, k - 1)
        if s[idx] == last_char:
            keep_char = self.dp(s, idx + 1, last_char, last_char_count + 1, k) + (1 if last_char_count in self.add else 0)
        else:
            keep_char = self.dp(s, idx + 1, s[idx], 1, k) + 1

        res = min(keep_char, delete_char)
        self.memo[key] = res

        return res

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

Открывайте Россию с Radisson Hotels Бронируйте на официальном сайте. Оплачивайте по прибытии. Наслаждайтесь комфортным отдыхом. Забронировать #реклама radissonhotels.com О рекламодателе

Задача: 236. Lowest Common Ancestor of a Binary Tree Сложность: medium Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях. 2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву. 3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q. 😎 Решение:

class Solution:
    def __init__(self):
        self.ans = None

    def recurseTree(self, currentNode, p, q):
        if not currentNode:
            return False

        left = self.recurseTree(currentNode.left, p, q) ? 1 : 0
        right = self.recurseTree(currentNode.right, p, q) ? 1 : 0
        mid = (currentNode == p or currentNode == q) ? 1 : 0

        if mid + left + right >= 2:
            self.ans = currentNode

        return mid + left + right > 0

    def lowestCommonAncestor(self, root, p, q):
        self.recurseTree(root, p, q)
        return self.ans

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

Специальность «Продуктовый менеджмент» 🎓Открыт набор в Университет IThub 2025-2026! Программа бакалавриата «Менеджмент» Программа создана для тех, кто хочет стать лидером в создании и развитии цифровых продуктов, соединяя бизнес, технологии и пользовательский опыт. Она идеально подходит для выпускников колледжа, включая креативные специальности. Программа сочетает знания в области управления продуктами, маркетинга и аналитики с практическими навыками работы с IT-командами. Выпускники становятся ключевыми специалистами в цифровой экономике и креативной индустрии. 📚Практические навыки + стажировки и 💰трудоустройство! ✅День открытых дверей 22 июня! Перейти на сайт #реклама 16+ univer.ithub.ru О рекламодателе

Задача: 370. Range Addition Сложность: medium Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci]. У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci. Верните arr после применения всех обновлений. Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:

def getModifiedArray(length, updates):
    result = [0] * length

    for update in updates:
        start, end, val = update
        result[start] += val
        if end + 1 < length:
            result[end + 1] -= val

    for i in range(1, length):
        result[i] += result[i - 1]

    return result

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1480. Running Sum of 1d Array Сложность: easy Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]). Верните массив текущих сумм для nums. Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

👨‍💻 Алгоритм: 1⃣Инициализация: Определите массив result. Инициализируйте первый элемент массива result первым элементом входного массива nums. 2⃣Вычисление текущих сумм: На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result. 3⃣Повторение для всех индексов: Повторите шаг 2 для всех индексов от 1 до n-1. 😎 Решение:

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = [0] * len(nums)
        result[0] = nums[0]
        for i in range(1, len(nums)):
            result[i] = result[i - 1] + nums[i]
        return result

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

Онлайн-магистратура в IT совместно с ИТМО, МИФИ и МФТИ День открытых дверей В удобное время | Онлайн Все программы 2025, общение со студентами и экспертами из вузов и Яндекса. Ответы на вопросы. Зарегистрироваться #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1207. Unique Number of Occurrences Сложность: easy Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае. Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

👨‍💻 Алгоритм: 1⃣Сохраните частоты элементов массива arr в хэш-таблице freq. 2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet. 3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false. 😎 Решение:

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1
        return len(freq) == len(set(freq.values()))

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 916. Word Subsets Сложность: medium Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке. Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

from collections import Counter

def wordSubsets(words1, words2):
    def count(word):
        return Counter(word)

    max_count = Counter()
    for word in words2:
        for char, cnt in count(word).items():
            max_count[char] = max(max_count[char], cnt)

    result = []
    for word in words1:
        word_count = count(word)
        if all(word_count[char] >= max_count[char] for char in max_count):
            result.append(word)

    return result

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе