Python | LeetCode

Задача: 583. Delete Operation for Two Strings Сложность: medium Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [0] * (n + 1)

        for i in range(m + 1):
            temp = [0] * (n + 1)
            for j in range(n + 1):
                if i == 0 or j == 0:
                    temp[j] = i + j
                elif word1[i - 1] == word2[j - 1]:
                    temp[j] = dp[j - 1]
                else:
                    temp[j] = 1 + min(dp[j], temp[j - 1])
            dp = temp

        return dp[n]

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

Дима Билан на Yandex Ecom Open Air 8 августа Регистрируйтесь на B2B-фестиваль от Яндекса для тех, кто развивает онлайн-коммерцию. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 753. Cracking the Safe Сложность: medium Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно. После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода. Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм: 1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1]. 2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз. 3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры. 😎 Решение:

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

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

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

Задача: 1370. Increasing Decreasing String Сложность: easy Дана строка s. Переставьте символы строки, используя следующий алгоритм: Выберите наименьший символ из s и добавьте его к результату. Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его. Повторяйте шаг 2, пока не сможете выбрать больше символов. Выберите наибольший символ из s и добавьте его к результату. Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его. Повторяйте шаг 5, пока не сможете выбрать больше символов. Повторяйте шаги с 1 по 6, пока не выберете все символы из s. На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату. Верните результирующую строку после сортировки s с помощью этого алгоритма. Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        char_count = Counter(s)
        result = []
        
        while len(result) < len(s):
            for char in "abcdefghijklmnopqrstuvwxyz":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
            for char in "zyxwvutsrqponmlkjihgfedcba":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
        
        return ''.join(result)

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

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

Задача: 895. Maximum Frequency Stack Сложность: hard Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека. Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.group = {}
        self.maxfreq = 0

    def push(self, val: int) -> None:
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        if f > self.maxfreq:
            self.maxfreq = f
            self.group[f] = []
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 203. Remove Linked List Elements Сложность: easy Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка. Пример:

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

👨‍💻 Алгоритм: 1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev. 2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next. 3️⃣Верните sentinel.next. 😎 Решение:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        sentinel = ListNode(0)
        sentinel.next = head
        
        prev, curr = sentinel, head
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        
        return sentinel.next

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

Как самостоятельно читать анализы и выявлять заболевания Научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой. Это бесплатно. На открытом уроке вы: ✅научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой; ✅узнаете о каких дефицитах может рассказать этот недорогой анализ; ✅научитесь составлять план работы с этим анализом без лекарств; ✅ узнаете, как стать нутрициологом, где искать клиентов и как зарабатывать от 100 000 рублей, не выходя из дома При регистрации вы получите подарок - конспект урока. После урока по этому конспекту вы сможете самостоятельно разобрать свой общий анализ крови. Чтобы зарегистрироваться на урок - переходите по ссылке. ⚡Урок бесплатный, поэтому количество мест ограничено. Зарегистрироваться #реклама 16+ pro-telo1.com О рекламодателе

Задача: 1514. Path with Maximum Probability Сложность: medium Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i]. Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха. Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5. Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1. 2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v]. 3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз. Верните max_prob[end]. 😎 Решение:

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        maxProb = [0.0] * n
        maxProb[start] = 1.0

        for _ in range(n - 1):
            hasUpdate = False
            for j in range(len(edges)):
                u, v = edges[j]
                pathProb = succProb[j]
                if maxProb[u] * pathProb > maxProb[v]:
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = True
                if maxProb[v] * pathProb > maxProb[u]:
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = True
            if not hasUpdate:
                break

        return maxProb[end]

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

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels Сложность: hard Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель. Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали. Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели. Вы должны написать алгоритм со сложностью менее O(mn). Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно. 2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника: left = min(left, x) right = max(right, x + 1) top = min(top, y) bottom = max(bottom, y + 1) 3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top). 😎 Решение:

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        left = self.searchColumns(image, 0, y, 0, m, True)
        right = self.searchColumns(image, y + 1, n, 0, m, False)
        top = self.searchRows(image, 0, x, left, right, True)
        bottom = self.searchRows(image, x + 1, m, left, right, False)
        return (right - left) * (bottom - top)

    def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = top, (i + j) // 2
            while k < bottom and image[k][mid] == '0':
                k += 1
            if (k < bottom) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

    def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = left, (i + j) // 2
            while k < right and image[mid][k] == '0':
                k += 1
            if (k < right) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

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

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

Задача: 1037. Valid Boomerang Сложность: easy Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией. Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

def isBoomerang(points):
    (x1, y1), (x2, y2), (x3, y3) = points
    return (x1 != x2 or y1 != y2) and (x1 != x3 or y1 != y3) and (x2 != x3 or y2 != y3) and (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0

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

Карго Бишкек Москва Доставка грузов из Кыргызстана и Китая в Россию. Узнайте стоимость на сайте! Узнать больше Продавец: Росс Карго. ОГРНИП: 31828313 #реклама rosscargo.kg О рекламодателе

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример:

Input: values = [1,2,3]
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:

def minScoreTriangulation(values):
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
                
    return dp[0][n - 1]

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

Ликвидация склада LADA в Тюмени ⚡ Автодилер LADA (ВАЗ). Полный модельный ряд в наличии. Скидки до 40% всю неделю. Успей купить новый автомобиль по низкой цене! Специальное предложение: - Выгода до 200 000₽ по trade-in - Автокредит без первоначального взноса - Комплект зимней резины в подарок ⚡ Акция! Новая Lada Granta в кредит от 2 289 ₽/мес. Только до конца месяца! 📞 Адрес автосалона: Тюмень, ул. Уездная, д. 2 ✅ Гарантированная скидка 30 000₽ за заявку онлайн! Перейти на сайт Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Финансовые услуги оказывает: ПАО Сбербанк, АО "ТБанк". #реклама vashalada72.ru О рекламодателе

Задача: 869. Reordered Power of 2 Сложность: medium Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем. Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки. Пример:

Input: n = 1
Output: true

👨‍💻 Алгоритм: 1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations. 2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1. 3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false. 😎 Решение:

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        A = list(map(int, str(N)))
        return self.permutations(A, 0)
    
    def isPowerOfTwo(self, A) -> bool:
        if A[0] == 0:
            return False
        N = int(''.join(map(str, A)))
        return N & (N - 1) == 0
    
    def permutations(self, A, start) -> bool:
        if start == len(A):
            return self.isPowerOfTwo(A)
        for i in range(start, len(A)):
            A[start], A[i] = A[i], A[start]
            if self.permutations(A, start + 1):
                return True
            A[start], A[i] = A[i], A[start]
        return False

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

Стратегическая инвестиция: бутик-отель в билиси Премиальный актив в центре Тбилиси - готовый бизнес с подтверждённым потенциалом роста. Отель включает 39 уникальных номеров, ресторан, современный тренажёрный зал и террасу. Ключевые показатели: - Стабильная заполняемость 60–70% - Высокие рейтинги: 4.3 на TripAdvisor, 8.2 на Agoda - Общая площадь: 1966 м² - Преимущества объекта: - Прозрачная структура владения - Полная готовность к эксплуатации - Престижное расположение Написать в Telegram #реклама ru.grovehotelgeorgia.com О рекламодателе