Python | LeetCode

Узнайте, какая профессия в IT вам подходит. Бесплатно! Пройдите тест на профессию и забирайте: ✅ Бесплатную карьерную консультацию с экспертом ✅ Доступ к чат-боту с гайдами по профессиям и заданиями для самопроверки ✅ Мини-курсы для погружения в IT и дизайн, чтобы точнее выбрать направление ✨130 000 человек уже прошли профтестирование и выбрали перспективную профессию в IT или дизайне Пройдите тест за 5 минут! Начать #реклама 16+ free.skillfactory.ru О рекламодателе

#medium Задача: 737. Sentence Similarity II Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм: 1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false. 2⃣Построить граф схожести слов с использованием словаря. 3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях. 😎 Решение:

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    
    graph = {}
    for x, y in similarPairs:
        if x not in graph:
            graph[x] = []
        if y not in graph:
            graph[y] = []
        graph[x].append(y)
        graph[y].append(x)
    
    def dfs(word1, word2, visited):
        if word1 == word2:
            return True
        visited.add(word1)
        for neighbor in graph.get(word1, []):
            if neighbor not in visited and dfs(neighbor, word2, visited):
                return True
        return False
    
    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and not dfs(w1, w2, set()):
            return False
    
    return True

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

Бесплатный курс по дизайну в FIGMA Онлайн-программа с наставником и чатом. Осторожно! 80% практики. По результату обучения у вас будет портфолио из нескольких работ. Сертификат о прохождении курса. Возможность пройти полное обучение и получить гарантированное трудоустройство! Учитесь дизайну у профессионалов. Переходи по кнопки: "Узнать больше" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#hard Задача: 736. Parse Lisp Expression Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

class Solution:
    def evaluate(self, expression: str) -> int:
        def evaluate(expression, env):
            if expression[0] != '(':
                if expression[0].isalpha():
                    return env[expression]
                return int(expression)
            
            tokens = tokenize(expression)
            if tokens[0] == 'let':
                for i in range(1, len(tokens) - 2, 2):
                    env[tokens[i]] = evaluate(tokens[i + 1], env)
                return evaluate(tokens[-1], env)
            elif tokens[0] == 'add':
                return evaluate(tokens[1], env) + evaluate(tokens[2], env)
            elif tokens[0] == 'mult':
                return evaluate(tokens[1], env) * evaluate(tokens[2], env)
        
        def tokenize(expression):
            tokens, token, parens = [], '', 0
            for char in expression:
                if char == '(':
                    parens += 1
                    if parens == 1:
                        continue
                elif char == ')':
                    parens -= 1
                    if parens == 0:
                        tokens.append(tokenize(token))
                        token = ''
                        continue
                elif char == ' ' and parens == 1:
                    if token:
                        tokens.append(token)
                        token = ''
                    continue
                token += char
            if token:
                tokens.append(token)
            return tokens
        
        return evaluate(expression, {})

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

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

#medium Задача: 735. Asteroid Collision Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

def asteroidCollision(asteroids):
    stack = []
    
    for asteroid in asteroids:
        while stack and asteroid < 0 < stack[-1]:
            if stack[-1] < -asteroid:
                stack.pop()
                continue
            elif stack[-1] == -asteroid:
                stack.pop()
            break
        else:
            stack.append(asteroid)
    
    return stack

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

Устали от переключений между рабочими приложениями? Переходите в Битрикс24. ✨Общение в мессенджере, продажи в CRM, регулярные синки по видео, задачи, проекты и помощь с креативом от ИИ-ассистента. Всё это в едином Битрикс24, а не в десятках приложений. Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

#easy Задача: 734. Sentence Similarity Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    
    similar = {}
    for x, y in similarPairs:
        if x not in similar:
            similar[x] = set()
        if y not in similar:
            similar[y] = set()
        similar[x].add(y)
        similar[y].add(x)
    
    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and (w1 not in similar or w2 not in similar[w1]):
            return False
    
    return True

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

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

#easy Задача: 733. Flood Fill Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

def floodFill(image, sr, sc, color):
    original_color = image[sr][sc]
    if original_color == color:
        return image
    
    def dfs(x, y):
        if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
            return
        image[x][y] = color
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
    
    dfs(sr, sc)
    return image

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

Как айтишнику быстро получить оффер Бесплатный воркшоп 20 марта Почему одному кандидату предлагают оффер после первого интервью, а другому говорят: «Мы вам перезвоним»? Причина в подаче своего опыта. Записывайся, чтобы узнать: — Как подготовиться к собеседованию — Как презентовать свой опыт так, чтобы тебя запомнили — Как проверяют hard skills и как к этому подготовиться — Как произвести хорошее впечатление, запомнится рекрутеру и сделать так, чтобы захотели работать именно с тобой Приходи на бесплатный воркшоп и узнай, как прокачать навык самопрезентации и получить работу мечты Зарегистрироваться #реклама 16+ my.mts-link.ru О рекламодателе

#hard Задача: 732. My Calendar III k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование. Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.start_times = defaultdict(int)
        self.end_times = defaultdict(int)

    def book(self, startTime, endTime):
        self.start_times[startTime] += 1
        self.end_times[endTime] += 1
        
        active = 0
        max_active = 0
        for time in sorted(self.start_times.keys()):
            active += self.start_times[time]
            if time in self.end_times:
                active -= self.end_times[time]
            max_active = max(max_active, active)
        
        return max_active

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

Разработка ПО на заказ Компания Арсис разрабатывает приложения и информационные системы с 1993 года. Реализовано более 200 проктов. Более 50 довольных клиентов из РФ, Германии, Австрии, Великобритании и США. Длительность ряда проектов превышает 25 лет. Мы сертифицированы на соответствие системе менеджмента качества ISO 9001:2015. Будем рады разработать для вас ПО на заказ. Свяжитесь с нами для получения бесплатной консультации! Получить консультацию #реклама arsis.ru О рекламодателе

#medium Задача: 731. My Calendar II Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

class MyCalendarTwo:
    def __init__(self):
        self.events = []
        self.overlaps = []

    def book(self, start, end):
        for os, oe in self.overlaps:
            if start < oe and end > os:
                return False
        for es, ee in self.events:
            if start < ee and end > es:
                self.overlaps.append((max(start, es), min(end, ee)))
        self.events.append((start, end))
        return True

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

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

#hard Задача: 730. Count Different Palindromic Subsequences Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi. Пример:

Input: s = "bccb"
Output: 6

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

def countPalindromicSubsequences(s):
    MOD = 10**9 + 7
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1
        
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                l, r = i + 1, j - 1
                while l <= r and s[l] != s[i]:
                    l += 1
                while l <= r and s[r] != s[j]:
                    r -= 1
                if l > r:
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                elif l == r:
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                else:
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
            else:
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
            dp[i][j] = (dp[i][j] + MOD) % MOD
    
    return dp[0][n - 1]

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

Обучение Data Science от онлайн-школы karpov.courses 🎓Комплексные программы обучения для начинающих и продвинутых с упором на практику Узнать больше #реклама 16+ karpov.courses О рекламодателе

#medium Задача: 729. My Calendar I Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

👨‍💻 Алгоритм: 1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий. 2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями. 3⃣Если новое событие не пересекается с существующими событиями, добавьте его в список событий и верните true. В противном случае верните false. 😎 Решение:

class MyCalendar:

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

    def book(self, start, end):
        for s, e in self.events:
            if start < e and end > s:
                return false
        self.events.append((start, end))
        return true

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

#hard Задача: 728. Self Dividing Numbers Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right]. Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

func selfDividingNumbers(_ left: Int, _ right: Int) -> [Int] {
    func isSelfDividing(_ num: Int) -> Bool {
        var n = num
        while n > 0 {
            let digit = n % 10
            if digit == 0 || num % digit != 0 {
                return false
            }
            n /= 10
        }
        return true
    }
    
    var result = [Int]()
    for num in left...right {
        if isSelfDividing(num) {
            result.append(num)
        }
    }
    return result
}

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

#hard Задача: 727. Minimum Window Subsequence Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом. Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

from collections import Counter, defaultdict

def minWindow(s1, s2):
    if not s1 or not s2:
        return ""

    dict_t = Counter(s2)
    required = len(dict_t)
    l, r = 0, 0
    formed = 0
    window_counts = defaultdict(int)
    ans = float("inf"), None, None

    while r < len(s1):
        character = s1[r]
        window_counts[character] += 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = s1[l]

            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            l += 1

        r += 1

    return "" if ans[0] == float("inf") else s1[ans[1]: ans[2] + 1]

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