Python | LeetCode

Задача: 651. 4 Keys Keyboard Сложность: medium Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш. Пример:

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

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

def maxA(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        for j in range(2, i):
            dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
    return dp[n]

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

⚡️Готовиться к собеседованиям стало проще! Женя Янченко, backend-dev и руководитель разработки, cделала конспекты самой популярной книги по архитектуре систем — «Высоконагруженные приложения» Мартина Клеппмана (книга с кабанчиком). Подробные разборы репликации, шардирования, транзакций: ▶️ ЧИТАТЬ КОНСПЕКТ КАБАНЧИКА В канале Женя разбирает и другие технические темы, особенно те, которые могут пригодиться на собесе по system design: 🟡 CAP-теорема простыми словами 🟡 Сравнение Kafka и RabbitMQ 🟡 API Gateway 🟡 Load Balancer А как же алгоритмы? Они тоже есть! В феврале Женя объявила челлендж — решить 300 задач за год 😱 и недавно стала делать разборы популярных задач: 🟡Разбор паттерна "Два указателя" Истории из опыта, рекомендации и ответы на вопросы: 🟡«Ты не оправдываешь ожиданий» и что с этим делать 🟡Про манипуляции менеджеров 🟡Как я боролась с неуверенностью в себе 🟡«Просто нажми кнопку» или история одного релиза 📝 и ещё 100+ полезных технических и жизненных постов. Подписывайтесь, чтобы не потерять полезный канал @jane_yanchenko

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

Задача: 600. Non-negative Integers without Consecutive Ones Сложность: hard Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц. Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

👨‍💻 Алгоритм: 1⃣Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц. 2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x. 3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц. 😎 Решение:

class Solution:
    def findIntegers(self, num: int) -> int:
        def check(n):
            i = 31
            while i > 0:
                if (n & (1 << i)) != 0 and (n & (1 << (i - 1))) != 0:
                    return False
                i -= 1
            return True

        count = 0
        for i in range(num + 1):
            if check(i):
                count += 1
        return count

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

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 1122. Relative Sort Array Сложность: easy Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1. Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания. Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        countMap = {value: 0 for value in arr2}
        remaining = []
        result = []

        for value in arr1:
            if value in countMap:
                countMap[value] += 1
            else:
                remaining.append(value)

        remaining.sort()

        for value in arr2:
            result.extend([value] * countMap[value])

        result.extend(remaining)
        return result

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

Задача: 738. Monotone Increasing Digits Сложность: medium Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами. Пример:

Input: n = 10
Output: 9

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

def monotoneIncreasingDigits(n):
    digits = list(str(n))
    mark = len(digits)
    
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            mark = i
            digits[i - 1] = str(int(digits[i - 1]) - 1)
    
    for i in range(mark, len(digits)):
        digits[i] = '9'
    
    return int("".join(digits))

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

Задача: 24. Swap Nodes in Pairs Сложность: medium Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы). Пример:

Input: head = [1,2,3,4]  
Output: [2,1,4,3]  

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

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:  
    if not (head and head.next):  
        return head  
    head, head.next, head.next.next = head.next, head, self.swapPairs(head.next.next)  
    return head

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

Задача: 366. Find Leaves of Binary Tree Сложность: medium Дан корень бинарного дерева, соберите узлы дерева следующим образом: Соберите все листовые узлы. Удалите все листовые узлы. Повторяйте, пока дерево не станет пустым. Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

👨‍💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -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 __init__(self):
        self.pairs = []

    def getHeight(self, node):
        if not node:
            return -1
        leftHeight = self.getHeight(node.left)
        rightHeight = self.getHeight(node.right)
        currHeight = max(leftHeight, rightHeight) + 1
        self.pairs.append((currHeight, node.val))
        return currHeight

    def findLeaves(self, root):
        self.getHeight(root)
        self.pairs.sort()
        solution = []
        currentHeight = -1
        for height, val in self.pairs:
            if height != currentHeight:
                solution.append([])
                currentHeight = height
            solution[-1].append(val)
        return solution

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

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 410. Split Array Largest Sum Сложность: easy Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива. Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

def splitArray(nums, k):
    def canSplit(nums, k, maxSum):
        currentSum = 0
        subarrays = 1
        for num in nums:
            if currentSum + num > maxSum:
                currentSum = num
                subarrays += 1
                if subarrays > k:
                    return False
            else:
                currentSum += num
        return True
    
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        if canSplit(nums, k, mid):
            right = mid
        else:
            left = mid + 1
    return left

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

Гайд для HRD и HRBP по проведению эффективных вебинаров Как HRD и HRBP ускорить адаптацию и обучение новых сотрудников с помощью вебинаров? Гайд от МТС Линк по подготовке и проведению эффективных вебинаров. ✅ В гайде: - Как лучше использовать вебинары для онбординга и обучения новых сотрудников; - Как упростить рекрутинг и снизить нагрузку на HR-команду; - Как ускорить адаптацию новичков и сократить отток на испытательном сроке; - Как сэкономить время на организации вебинара и пригласить всех участников в 2 клика. Бонус внутри: 5 прикладных советов по контролю внимания участников во время вебинара ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 221. Maximal Square Сложность: medium Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь. Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

👨‍💻 Алгоритм: 1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения. 2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением. 3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата. 😎 Решение:

class Solution:
    def maximalSquare(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0
        dp = [0] * (cols + 1)
        maxsqlen = 0
        prev = 0
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                temp = dp[j]
                if matrix[i - 1][j - 1] == "1":
                    dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1
                    maxsqlen = max(maxsqlen, dp[j])
                else:
                    dp[j] = 0
                prev = temp
        return maxsqlen * maxsqlen

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 152. Maximum Product Subarray Сложность: Medium Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

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

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        result = nums[0]

        for i in range(len(nums)):
            accu = 1
            for j in range(i, len(nums)):
                accu *= nums[j]
                result = max(result, accu)

        return result

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

Задача: 1114. Print in Order Сложность: easy Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second(). Примечание: Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов. Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены. 2⃣Функция first(): В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено. 3⃣Функции second() и third(): В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания. В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания. 😎 Решение:

from threading import Semaphore

class Foo:
    def __init__(self):
        self.firstJobDone = Semaphore(0)
        self.secondJobDone = Semaphore(0)

    def first(self, printFirst):
        printFirst()
        self.firstJobDone.release()

    def second(self, printSecond):
        self.firstJobDone.acquire()
        printSecond()
        self.secondJobDone.release()

    def third(self, printThird):
        self.secondJobDone.acquire()
        printThird()

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

Задача: 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)

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

Используете мессенджеры для бизнеса? ✅ Объединяющий несколько аккаунтов WhatsApp, Telegram, ВКонтакте и других соцсетей в одном приложении, распределяйте заявки и управляйте перепиской сотрудников в едином мессенджере Umnico. ✨ Оцените все возможности бесплатно прямо сейчас! Зарегистрироваться #реклама 16+ umnico.com О рекламодателе

Задача: 623. Add One Row to Tree Сложность: medium Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня. Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня. Пример:

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

👨‍💻 Алгоритм: 1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня. 2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1. 3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья. 😎 Решение:

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

def addOneRow(root, val, depth):
    if depth == 1:
        return TreeNode(val, left=root)
    
    queue = [root]
    current_depth = 1
    
    while queue:
        if current_depth == depth - 1:
            for node in queue:
                node.left = TreeNode(val, left=node.left)
                node.right = TreeNode(val, right=node.right)
            break
        
        current_depth += 1
        next_queue = []
        for node in queue:
            if node.left:
                next_queue.append(node.left)
            if node.right:
                next_queue.append(node.right)
        queue = next_queue
    
    return root

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

👩‍💻 Ищем Python разработчиков. Удалёнка, релокейт платим много! Специально для Вас, собираем лучшие вакансии для Python разработчиков с прямыми контактами в Telegram на канале @it_match_python Подпишись чтобы не упустить свой шанс получить лучший оффер! ➡️ Посмотреть вакансии