Python | LeetCode

#medium Задача: 718. Maximum Length of Repeated Subarray Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах. Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

def findLength(nums1, nums2):
    dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
    max_len = 0
    for i in range(len(nums1) - 1, -1, -1):
        for j in range(len(nums2) - 1, -1, -1):
            if nums1[i] == nums2[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

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

#easy Задача: 717. 1-bit and 2-bit Characters У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным. Пример:

Input: bits = [1,0,0]
Output: true

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

def isOneBitCharacter(bits):
    i = 0
    while i < len(bits) - 1:
        i += bits[i] + 1
    return i == len(bits) - 1

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

ТОП 2 канала для тех кто увлекатеся хакингом и кибербезопасностью: Этичный Хакер — крупнейший в СНГ канал по информационной безопасности. OSINT, анонимность, пентест, социальная инженерия. Лаборатория Хакера — авторский канал от специалиста по ИБ. Новости даркнета, сетевая разведка, обзоры инструментов с github, полезные подборки.

Инвестиции в отельный бизнес. Вложения в ₽ заработок в $ International Investment предлагает портфельные инвестиции в пятизвездочный отель на Черноморском побережье Грузии. Сумма вложения — от $40 000 (или эквивалент в рублях). Фиксированная доходность 12% годовых по договору, заверенному Министерством юстиции Грузии. Срок инвестиции 3 года, с возможностью пролонгации или обратного выкупа по первоначальной цене. Инвестор становится совладельцем 5* отеля от мирового бренда. По окончании срока вложений портфель продлевается, либо мы выкупаем его по первоначальной цене, обеспечивая сохранность средств. Оставьте заявку на консультацию и получите подробную информацию о проекте. Узнать больше #реклама ge.internationalinvestment.biz О рекламодателе

#medium Задача: 776. Split BST Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target. Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p. Верните массив из двух корней двух поддеревьев в порядке. Пример:

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

👨‍💻 Алгоритм: 1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое. 2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 😎 Решение:

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

class Solution:
    def splitBST(self, root: TreeNode, target: int) -> List[TreeNode]:
        if not root:
            return [None, None]
        
        if root.val > target:
            left = self.splitBST(root.left, target)
            root.left = left[1]
            return [left[0], root]
        else:
            right = self.splitBST(root.right, target)
            root.right = right[0]
            return [root, right[1]]

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

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

#hard Задача: 716. Max Stack Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:

class MaxStack:

    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self):
        x = self.stack.pop()
        if x == self.max_stack[-1]:
            self.max_stack.pop()
        return x

    def top(self):
        return self.stack[-1]

    def peekMax(self):
        return self.max_stack[-1]

    def popMax(self):
        max_val = self.max_stack.pop()
        buffer = []
        while self.stack[-1] != max_val:
            buffer.append(self.stack.pop())
        self.stack.pop()
        while buffer:
            self.push(buffer.pop())
        return max_val

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

Новые возможности Yandex Search API 20 февраля в 12:00 (мск) пройдёт бесплатный онлайн-вебинар для владельцев сайтов и аналитических сервисов. Вы узнаете, как использовать поисковые технологии для повышения эффективности своего бизнеса. Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

#medium Задача: 775. Global and Local Inversions Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1]. Число глобальных инверсий — это количество различных пар (i, j), где: 0 <= i < j < n nums[i] > nums[j] Число локальных инверсий — это количество индексов i, где: 0 <= i < n - 1 nums[i] > nums[i + 1] Верните true, если количество глобальных инверсий равно количеству локальных инверсий. Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

👨‍💻 Алгоритм: 1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1. 2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии. 3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false. 😎 Решение:

class Solution:
    def isIdealPermutation(self, A: List[int]) -> bool:
        N = len(A)
        for i in range(N):
            for j in range(i + 2, N):
                if A[i] > A[j]:
                    return False
        return True

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

Бесплатный курс по UX/UI-дизайну с нуля C нуля сделаете портфолио из 4+ работ и узнаете всё о профессии UX/UI дизайнера на практике: - дизайн сайтов и интерфейсов приложений - графический дизайн - веб-дизайн С личным наставником и разбором работ 🎓 Подать заявку #реклама 16+ yudaevschool24.online О рекламодателе

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

#hard Задача: 774. Minimize Max Distance to Gas Station Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k. Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию. Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций. Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

👨‍💻 Алгоритм: 1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x. 2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов. 3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций. 😎 Решение:

class Solution:
    def minmaxGasDist(self, stations: List[int], K: int) -> float:
        N = len(stations)
        deltas = [0] * (N-1)
        for i in range(N-1):
            deltas[i] = stations[i+1] - stations[i]

        dp = [[0] * (K+1) for _ in range(N-1)]
        for i in range(K+1):
            dp[0][i] = deltas[0] / (i+1)

        for p in range(1, N-1):
            for k in range(K+1):
                bns = float('inf')
                for x in range(k+1):
                    bns = min(bns, max(deltas[p] / (x+1), dp[p-1][k-x]))
                dp[p][k] = bns

        return dp[N-2][K]

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

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

#hard Задача: 715. Range Module Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right). Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

👨‍💻 Алгоритм: 1⃣Инициализируйте класс RangeModule с пустым списком диапазонов. 2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах. 3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части. 😎 Решение:

class RangeModule:

    def __init__(self):
        self.ranges = []

    def addRange(self, left, right):
        new_ranges = []
        i = 0
        while i < len(self.ranges) and self.ranges[i][1] < left:
            new_ranges.append(self.ranges[i])
            i += 1
        while i < len(self.ranges) and self.ranges[i][0] <= right:
            left = min(left, self.ranges[i][0])
            right = max(right, self.ranges[i][1])
            i += 1
        new_ranges.append((left, right))
        while i < len(self.ranges):
            new_ranges.append(self.ranges[i])
            i += 1
        self.ranges = new_ranges

    def queryRange(self, left, right):
        for l, r in self.ranges:
            if l <= left and right <= r:
                return True
        return False

    def removeRange(self, left, right):
        new_ranges = []
        for l, r in self.ranges:
            if l < left:
                new_ranges.append((l, min(r, left)))
            if right < r:
                new_ranges.append((max(l, right), r))
        self.ranges = new_ranges

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

Ошибки в коде — ключ для атаки на веб-приложения Всего одна ошибка — и данные ваших клиентов могут оказаться в руках мошенников. Иногда достаточно одной неверной строчки кода, чтобы хакеры получили доступ к информации о пользователях. Чтобы этого не произошло, важно позаботиться о безопасности еще на начальном этапе разработки. Как это сделать, расскажут эксперты «Солара» и AppSec Solutions на вебинаре 18 февраля. Вы узнаете: ✅какие языки программирования наиболее уязвимы — исследования от AppSec Solutions, ✅как проверить веб-приложение и ПО на безопасность без навыка разработки, ✅какие новые возможности появились в Solar appScreener 3.15.0. Регистрируйтесь! Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 772. Basic Calculator III Реализуйте базовый калькулятор для вычисления простого строкового выражения. Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю. Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1]. Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval(). Пример:

Input: s = "1+1"
Output: 2

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@". 2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+". 3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке. 😎 Решение:

class Solution:
    def evaluate(self, operator, first, second):
        x = int(first)
        y = int(second)
        if operator == '+':
            return str(x)
        elif operator == '-':
            return str(-x)
        elif operator == '*':
            return str(x * y)
        else:
            return str(x // y)

    def calculate(self, s: str) -> int:
        stack = []
        curr = ""
        previousOperator = '+'
        s += "@"
        operators = set("+-*/")
        
        for c in s:
            if c.isdigit():
                curr += c
            elif c == '(':
                stack.append(previousOperator)
                previousOperator = '+'
            else:
                if previousOperator in "*/":
                    stack.append(self.evaluate(previousOperator, stack.pop(), curr))
                else:
                    stack.append(self.evaluate(previousOperator, curr, "0"))
                
                curr = ""
                previousOperator = c
                if c == ')':
                    currentTerm = 0
                    while stack[-1] not in operators:
                        currentTerm += int(stack.pop())
                    curr = str(currentTerm)
                    previousOperator = stack.pop()
        
        return sum(int(num) for num in stack)

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

⚡️Слита База из 1000+ топовых курсов и материалов для айтишников 🖥 Python: @python_baza 👩‍💻 Frontend: @frontend_baza 👩‍💻 Backend: @backend_baza 🎨 Дизайн: @design_baza 📚 Книги: @archive_baza 👩‍💻 Топ GitHub: @main_it_baza Всё лучшее про IT бесплатно — уже на Базе 🚀

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ к курсу - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#medium Задача: 487. Max Consecutive Ones II Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

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

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longestSequence = 0
        for left in range(len(nums)):
            numZeroes = 0
            for right in range(left, len(nums)):
                if nums[right] == 0:
                    numZeroes += 1
                if numZeroes <= 1:
                    longestSequence = max(longestSequence, right - left + 1)
        return longestSequence

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

Запустить рекламу в Telegram можно от 500 €. Это можно сделать с крупнейшим селлером Telegram Ads — Magnetto.pro. Это международное digital-агентство,которое: - Работает с Telegram Ads с момента появления платформы - Ведет прямой диалог с командой сервиса - Имеет экспертизу во всех современных бизнес-нишах Преимущества рекламы с Magnetto.pro: - Качественный трафик без ботов - Оперативная премодерация объектов рекламы - Оплата без наценки за курс евро–рубль Начать сотрудничество с агентством можно в двух форматах. - Full service: все задачи на себя берет Magnetto.pro. А вы держите руку на пульсе с помощью персонального менеджера и расширенного отчета по кампаниям. - Self service: вы работаете сами, но получаете доступ к кабинету и дополнительные возможности. Получить предложение #реклама magnetto.pro О рекламодателе