Python | LeetCode

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 421. Maximum XOR of Two Numbers in an Array Сложность: medium Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n. Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

👨‍💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        max_num = max(nums)
        L = len(bin(max_num)) - 2

        max_xor = 0
        for i in range(L - 1, -1, -1):
            max_xor <<= 1
            curr_xor = max_xor | 1
            prefixes = {num >> i for num in nums}
            if any(curr_xor ^ p in prefixes for p in prefixes):
                max_xor = curr_xor
        return max_xor

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

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

Задача: 634. Find the Derangement of An Array Сложность: medium В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7. Пример:

Input: n = 3
Output: 2

👨‍💻 Алгоритм: 1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:

def countDerangements(n: int) -> int:
    MOD = 10**9 + 7
    if n == 0:
        return 1
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 0
    for i in range(2, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
    return dp[n]

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

Задача: 624. Maximum Distance in Arrays Сложность: medium Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние. Пример:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4

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

def maxDistance(arrays):
    min_val = arrays[0][0]
    max_val = arrays[0][-1]
    max_distance = 0
    
    for i in range(1, len(arrays)):
        max_distance = max(max_distance, abs(arrays[i][-1] - min_val), abs(arrays[i][0] - max_val))
        min_val = min(min_val, arrays[i][0])
        max_val = max(max_val, arrays[i][-1])
    
    return max_distance

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

Регистрируйтесь на вебинар SIEM UserGate 💻Расскажет о том, как экосистема и SIEM UserGate помогает бороться с фишинговыми атаками в рамках демонстрации конкретного кейса. На вебинаре будет: - Вступительное слово - Экспертиза UserGate и сценарий конкретного кейса - Демонстрация кейса защиты от фишинговой атаки - Ответы на вопросы 👌Расскажем, как защитить вашу компанию. Регистрируйтесь — будет интересно! Зарегистрироваться #реклама 16+ webinar.usergate.com О рекламодателе

Задача: 187. Repeated DNA Sequences Сложность: medium ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'. Например, "ACGAATTCCG" — это последовательность ДНК. При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК. Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке. Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

👨‍💻 Алгоритм: 1️⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10): Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿]. В противном случае вычисляем скользящий хеш из предыдущего значения хеша. 2️⃣Проверяем хеш в хешсете: Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод. В противном случае добавляем хеш в хешсет. 3️⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности. 😎 Решение:

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L, n = 10, len(s)
        if n <= L:
            return []
        a = 4
        aL = pow(a, L)
        to_int = {"A": 0, "C": 1, "G": 2, "T": 3}
        nums = [to_int.get(s[i]) for i in range(n)]

        h = 0
        seen, output = set(), set()
        for start in range(n - L + 1):
            if start != 0:
                h = h * a - nums[start - 1] * aL + nums[start + L - 1]
            else:
                for i in range(L):
                    h = h * a + nums[i]
            if h in seen:
                output.add(s[start : start + L])
            seen.add(h)
        return output

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

Задача: 593. Valid Square Сложность: medium Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат. Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке. Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов). Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

class Solution:
    def dist(self, p1, p2):
        return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2

    def check(self, p1, p2, p3, p4):
        return self.dist(p1, p2) > 0 and \
               self.dist(p1, p2) == self.dist(p2, p3) == self.dist(p3, p4) == self.dist(p4, p1) and \
               self.dist(p1, p3) == self.dist(p2, p4)

    def validSquare(self, p1, p2, p3, p4):
        return self.check(p1, p2, p3, p4) or \
               self.check(p1, p3, p2, p4) or \
               self.check(p1, p2, p4, p3)

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

Битрикс24 полностью переосмыслили и обновили интерфейс Теперь он простой, воздушный как зефир/ Главные фичи релиза — ИИ-ассистент с голосовым вводом, формы онлайн-записи с оплатой и овербукингом и совершенно новое на рынке — ИИ-агенты в бизнес-процессах. ✨А ещё тонна новых ИИ-сценариев: искусственный интеллект здесь теперь пушит повторные продажи, помогает разбудить спящих клиентов, а еще настраивает за вас CRM и даже оценит софт-скиллы после созвона. 😊Такое обновление мы ждали. Узнать больше #реклама 16+ lightness.bitrix24.ru О рекламодателе

Задача: 521. Longest Uncommon Subsequence I Сложность: easy Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1. Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них. Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

👨‍💻 Алгоритм: 1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности. 2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки. 😎 Решение:

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        else:
            return max(len(a), len(b))

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

Задача: 741. Cherry Pickup Сложность: hard Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1). После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя. Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

def cherryPickup(grid):
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for _ in range(n)]
    dp[0][0][0] = grid[0][0]

    for k in range(1, 2 * (n - 1) + 1):
        for i1 in range(max(0, k - n + 1), min(n, k + 1)):
            for i2 in range(max(0, k - n + 1), min(n, k + 1)):
                j1, j2 = k - i1, k - i2
                if 0 <= j1 < n and 0 <= j2 < n and grid[i1][j1] != -1 and grid[i2][j2] != -1:
                    max_cherries = max(
                        dp[i1 - 1][i2 - 1][k - 1] if i1 > 0 and i2 > 0 else -float('inf'),
                        dp[i1 - 1][i2][k - 1] if i1 > 0 else -float('inf'),
                        dp[i1][i2 - 1][k - 1] if i2 > 0 else -float('inf'),
                        dp[i1][i2][k - 1]
                    )
                    if max_cherries != -float('inf'):
                        dp[i1][i2][k] = max_cherries + grid[i1][j1]
                        if i1 != i2:
                            dp[i1][i2][k] += grid[i2][j2]

    return max(0, dp[n - 1][n - 1][2 * (n - 1)])

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

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

Задача: 986. Interval List Intersections Сложность: 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: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

def intervalIntersection(firstList, secondList):
    i, j = 0, 0
    result = []

    while i < len(firstList) and j < len(secondList):
        start = max(firstList[i][0], secondList[j][0])
        end = min(firstList[i][1], secondList[j][1])
        
        if start <= end:
            result.append([start, end])
        
        if firstList[i][1] < secondList[j][1]:
            i += 1
        else:
            j += 1
    
    return result

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

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! 5 занятий по теме «Промпт-инжиниринг». Регистрируйся для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 230. Kth Smallest Element in a BST Сложность: medium Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве. Пример:

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

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

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

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

Высшее образование дистанционно от 6700 ₽/мес. Поступи в Московский технологический институт в мае! — Высшее образование в московском вузе без выезда на сессии. — Полностью дистанционный онлайн-формат. — Обучайся дома, на работе, в путешествии. — Диплом государственного образца. — 73 направления и программы обучения. — Программа колледж + вуз без ЕГЭ. Скидка 10% на платное обучение при оплате за год. Подать заявку #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 1044. Longest Duplicate Substring Сложность: hard Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "". Пример:

Input: s = "banana"
Output: "ana"

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

def longestDupSubstring(s):
    n = len(s)
    mod = 2**63 - 1

    def search(length):
        p = 26
        current_hash = 0
        p_length = pow(p, length, mod)
        hashes = set()

        for i in range(length):
            current_hash = (current_hash * p + ord(s[i])) % mod
        
        hashes.add(current_hash)
        
        for i in range(length, n):
            current_hash = (current_hash * p + ord(s[i]) - ord(s[i - length]) * p_length) % mod
            if current_hash in hashes:
                return i - length + 1
            hashes.add(current_hash)
        
        return -1

    left, right = 1, n - 1
    result = ""
    
    while left <= right:
        mid = (left + right) // 2
        start = search(mid)
        if start != -1:
            result = s[start:start + mid]
            left = mid + 1
        else:
            right = mid - 1
    
    return result

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

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

Задача: 277. Find the Celebrity Сложность: medium Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них. Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле). Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть. Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1. Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

👨‍💻 Алгоритм: 1⃣Найти потенциального кандидата на знаменитость: Использовать один проход через всех людей, чтобы определить возможного кандидата. Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b. 2⃣Реализовать функцию isCelebrity(candidate): Проверить, знает ли кандидат кого-либо из людей (исключая самих себя). Проверить, знают ли все остальные кандидата (исключая самого кандидата). Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью. 3⃣Возвращение результата: Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку. В противном случае вернуть -1. 😎 Решение:

from functools import lru_cache

class Solution:
    
    @lru_cache(maxsize=None)
    def cachedKnows(self, a, b):
        return knows(a, b)
    
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if self.cachedKnows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if self.cachedKnows(i, j) or not self.cachedKnows(j, i):
                return False
        return True

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