Python | LeetCode

PostgreSQL как сервис: что это и как применяется? Сервис PostgreSQL от РТК-ЦОД позволяет быстро развернуть, эксплуатировать и масштабировать базу данных в облаке. Процесс установки и настройки полностью автоматизирован. Как наши клиенты используют PostgreSQL? — Работают в 1С — Управляют платежными системами — Ведут финансовый учет — Собирают геоданные — Работают с данными со сложной структурой — Анализируют большие массивы данных ✅30 дней бесплатно: тестируйте наш сервис с полным доступом ко всем возможностям. Оставьте заявку на www.cloud.rt.ru Узнать больше #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 744. Find Smallest Letter Greater Than Target Сложность: easy Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

def nextGreatestLetter(letters, target):
    left, right = 0, len(letters) - 1
    while left <= right:
        mid = (left + right) // 2
        if letters[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return letters[left % len(letters)]

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

Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰 Почему это работает?✨ - Минимальные вложения. - Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций. - Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями. P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊 Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре. Подать заявку #реклама 16+ kata.academy О рекламодателе

Задача: 153. Find Minimum in Rotated Sorted Array Сложность: Medium Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать: [4,5,6,7,0,1,2], если он был повернут 4 раза. [0,1,2,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива. Вы должны написать алгоритм, который работает за время O(log n). Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

👨‍💻 Алгоритм: 1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. 3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:

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

        left = 0

        right = len(nums) - 1

        if nums[right] > nums[0]:
            return nums[0]
        while right >= left:
            
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            if nums[mid - 1] > nums[mid]:
                return nums[mid]
            if nums[mid] > nums[0]:
                left = mid + 1
            else:
                right = mid - 1

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

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

Задача: 442. Find All Duplicates in an Array Сложность: medium Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды. Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство. Пример:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

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

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] == nums[i]:
                    ans.append(nums[i])
                    break
        
        return ans

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

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 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 Подпишись чтобы не упустить свой шанс получить лучший оффер! ➡️ Посмотреть вакансии