Python | LeetCode

Задача: №44. Wildcard Matching Сложность: hard При наличии входных строк s и шаблона p реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой "?" и "*", где: - "?" соответствует любому отдельному символу. - "*" соответствует любой последовательности символов (включая пустую последовательность). Соответствие должно охватывать всю входную строку (не частичное). Пример:

Input: s = "adceb", p = "*a*b"  
Output: true  

👨‍💻 Алгоритм: 1️⃣Используем динамическое программирование, создаем матрицу dp для хранения промежуточных результатов. 2️⃣Инициализируем dp[0][0] = True (пустая строка соответствует пустому шаблону). 3️⃣Заполняем dp, учитывая, что "?" заменяет любой символ, а "*" может заменять любую последовательность символов. 😎 Решение:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
        
        return dp[m][n]

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

Освойте Data Engineering Получи шанс стать частью команды в LEFT JOIN 🎓Чему научитесь: » использовать Python для анализа данных » составлять продвинутые SQL-запросы » самостоятельно извлекать данные из хранилищ » разрабатывать понятные отчеты и презентации 📊Научим правильно готовить данные любых размеров и сложности ✨Кому подойдет обучение: » аналитикам данных, которые хотят лучше разобраться в ETL-процессах » инженерам данных, которые уже работают с хранилищами и хотят систематизировать свои знания. » BI-разработчикам, освоить архитектуру современных хранилищ и научиться их проектировать ❤️Мы поможем подготовиться к поиску работы😊 Ограниченное количество мест на курс Узнать больше #реклама 16+ karpov.courses О рекламодателе

Я боялся, что провалю собеседование. Так появился easyoffer Когда я только начинал искать первую работу программистом, меня пугала мысль, что я просто не смогу ответить на вопросы на собеседовании. Типа… ты потратил месяцы на то, чтобы учиться, писал pet-проекты, собирал резюме, рассылаешь отклики — и всё может закончиться на одном-единственном вопросе, на который ты не знаешь ответ. Я реально боялся. Я смотрел видео mock-собеседований на YouTube, останавливал каждое, выписывал вопросы в Notion. Потом вручную писал к ним ответы. И потом ещё по нескольку раз перечитывал. Такой вот "тренажёр" на коленке. 📎 (там на картинке — один из моих реальных списков в Notion, ставь 🔥 если тоже так делал) В какой-то момент я посчитал — у меня уже было выписано больше 500 вопросов. Я почувствовал ужас. Потому что невозможно всё это зазубрить. А что, если спросят как раз тот, к которому я не успел подготовиться?.. Тогда и пришла идея А что если понять, какие из вопросов встречаются чаще всего? Чтобы не учить всё подряд, а сфокусироваться на главном. Так родился easyoffer. Сначала — просто как пет-проект, чтобы показать в резюме и подготовиться к собесам. А потом оказалось, что он реально помогает людям. За первые месяцы его посетили сотни тысяч человек. И я понял: это больше, чем просто пет-проект. Сейчас я делаю EasyOffer 2.0 И уже не один, а вместе с вами. В новой версии будут: – вопросы из реальных собесов, с фильтрацией по грейду, компании, типу интервью – тренажёр с карточками (по принципу интервальных повторений — как в Anki) – база задач с интервью – тренажёр «реальное собеседование», чтобы отрепетировать как в жизни Каждая фича упрощает и сокращает время на подготовку. Все эти штуки я бы мечтал иметь, когда сам готовился к собеседованиям. Я делаю всё на свои деньги. Никаких инвесторов. Только вы и я. Если вы хотите помочь — сейчас самое важное время. Краудфандинг уже стартовал. Благодаря нему я смогу привлечь больше людей для разработки, сбору и обработки собеседований. Все, кто поддержат проект до релиза, получат: 🚀 1 год PRO-доступа по цене месячной подписки. Его можно активировать в любое время, например когда начнете готовится к собесам. ➕ Доступ к закрытому бета-тесту Поддержать 👉 https://planeta.ru/campaigns/easyoffer Спасибо, что верите в этот проект 🙌

Задача: 688. Knight Probability in Chessboard Сложность: medium На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1). Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении. Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда. Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски. Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы. Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

👨‍💻 Алгоритм: 1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня. 2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j]. 3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность. 😎 Решение:

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        dp[0][row][column] = 1

        for moves in range(1, k + 1):
            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        prevI, prevJ = i - direction[0], j - direction[1]
                        if 0 <= prevI < n and 0 <= prevJ < n:
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8

        return sum(map(sum, dp[k]))

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

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

Задача: 904. Fruit Into Baskets Сложность: medium Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать. Пример:

Input: fruits = [1,2,1]
Output: 3

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

def totalFruit(fruits):
    from collections import defaultdict
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        basket[fruits[right]] += 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

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

Разбуди в себе Python-программиста Python-программирование стремительно набирает популярность благодаря своей универсальности и высокой востребованности на рынке труда. Стать Python-программистом — это ваш путь к стабильной и успешной карьере в сфере технологий. Записывайтесь в лист ожидания и получите новую профессию в числе первых. Количество льготных мест ограничено, так что не упустите шанс изменить свою жизнь к лучшему. Обучим бесплатно, если ты: — В отпуске по уходу за ребёнком — Неработающая мама детей до 7 лет — Официально не работаешь или под риском увольнения — 50 лет и старше или предпенсионер — Находишься в поисках работы или хочешь повысить квалификацию на текущем рабочем месте Подать заявку #реклама 16+ osnovanie.info О рекламодателе

Задача: 42. Trapping Rain Water Сложность: hard Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя. Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

👨‍💻 Алгоритм: 1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max. 2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max. 3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans. 😎 Решение:

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

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

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

Задача: 667. Beautiful Arrangement II Сложность: medium Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию: Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них. Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

def constructArray(n, k):
    answer = []
    left, right = 1, n
    
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    
    if k % 2 == 0:
        answer.extend(range(left, right + 1))
    else:
        answer.extend(range(right, left - 1, -1))
    
    return answer

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

Скидка до 30% на вашу первую Яндекс Командировку ✨Получите скидку 30% на бронирование отеля вашей первой командировки. Все необходимые сервисы на единой платформе, для командировок по всему миру. Широкий выбор отелей и билетов. Без комиссий. Узнать больше #реклама business.go.yandex О рекламодателе Реклама на Яндексе

Задача: 762. Prime Number of Set Bits in Binary Representation Сложность: hard Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита. Пример:

Input: left = 10, right = 15
Output: 5

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

def countPrimeSetBits(left, right):
    def countBits(x):
        return bin(x).count('1')
    
    def isPrime(x):
        if x < 2:
            return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True
    
    count = 0
    for num in range(left, right + 1):
        if isPrime(countBits(num)):
            count += 1

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

От чего зависит эффективность автотестов? От их правильного написания и поддерживаемости! В QA GURU учат приручать Java, чтобы ваши автотесты работали, как часы. Вот несколько лайфхаков, о которых мы расскажем на вводном занятии уже сегодня (20:00 Мск): 1. Используйте понятные и описательные названия тестов Названия тестов должны четко отражать их цель. Это упрощает понимание кода всеми членами команды. Например: // Хорошо

public void verifyLoginWithValidCredentials() { ... }

// Плохо

public void test1() { ... }

Описательные названия помогают быстро понять, что проверяет тест, без необходимости изучения его внутренней логики. 2. Применяйте Page Object Model (POM) Page Object Model позволяет отделить логику теста от структуры веб-страницы, что делает код более модульным и удобным для поддержки при изменениях интерфейса. Пример использования: // Класс

Page Object
public class LoginPage {
    private By usernameField = By. id("username");
    private By passwordField = By. id("password");
    private By loginButton = By. id("loginBtn");

    public void enterUsername(String username) {
        driver.findElement(usernameField).sendKeys(username);
    }

    public void enterPassword(String password) {
        driver.findElement(passwordField).sendKeys(password);
    }

    public void clickLoginButton() {
        driver.findElement(loginButton).click();
    }
}

// Тестовый сценарий

LoginPage loginPage = new LoginPage(driver);
loginPage.enterUsername("john.doe");
loginPage.enterPassword("password123");
loginPage.clickLoginButton();

POM способствует повторному использованию кода и улучшает читаемость тестов. 3. Используйте параметризацию и data-driven подход Параметризованные тесты позволяют запускать один и тот же сценарий с различными входными данными, что увеличивает охват тестирования без дублирования кода.

@ ParameterizedTest
@ CsvSource({"john.doe, password123", "jane.smith, test@123"})
public void verifyLogin(String username, String password) {
    LoginPage loginPage = new LoginPage(driver);
    loginPage.enterUsername(username);
    loginPage.enterPassword(password);
    loginPage.clickLoginButton();
}

Этот подход делает тесты более гибкими и масштабируемыми. 4. Следуйте принципу AAA (Arrange, Act, Assert) Структурируйте тесты в три этапа: Arrange: подготовка данных и окружения. Act: выполнение действия. Assert: проверка результата. Пример:

@ Test
public void testAddition() {
    // Arrange
    Calculator calculator = new Calculator();

    // Act
    int result = calculator.add(2, 3);

    // Assert
    assertEquals(5, result);
}

Этот подход делает тесты более организованными и легко читаемыми. 5. Логирование и отчетность Добавляйте логирование в тесты для диагностики проблем:

log. info("Entering username: " + username);
log. info("Clicking on the login button");

Интеграция инструментов отчетности (например, Allure) помогает визуализировать результаты тестов и быстро выявлять ошибки. 6. Регулярные ревью кода Проводите регулярные ревью автотестов для повышения качества кода. Это помогает выявить потенциальные проблемы, улучшить читаемость и обеспечить соблюдение стандартов кодирования. 7. Автоматизация и CI/CD Используйте инструменты автоматизации (Maven, Gradle) для запуска тестов в рамках CI/CD пайплайнов. Это ускоряет процесс разработки и обеспечивает стабильность приложения на всех этапах. Хотите узнать больше? Присоединяйтесь уже сегодня (20:00 Мск) к бесплатному открытому уроку! 🔗 Зарегистрируйтесь на первый открытый урок по ссылке.

Бизнес образование в Moscow Business Academy (MBA) Получите современное бизнес образование от международных экспертов. ✅Более 37 направлений обучения. ✅Международные дипломы. ✅Online и очные форматы обучения. ✅Разборы практических бизнес-кейсов. Скидка на все программы online до 35%! Узнать больше #реклама 16+ moscow.mba О рекламодателе

Задача: 662. Maximum Width of Binary Tree Сложность: medium Дан корень бинарного дерева, верните максимальную ширину данного дерева. Максимальная ширина дерева - это максимальная ширина среди всех уровней. Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины. Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа. Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

from collections import deque

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

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        queue = deque([(root, 0)])
        
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            max_width = max(max_width, pos - first_pos + 1)
        
        return max_width

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 1426. Counting Elements Сложность: easy Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно. Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

class Solution:
    def countElements(self, arr: List[int]) -> int:
        def integerInArray(arr, target):
            for x in arr:
                if x == target:
                    return True
            return False
        
        count = 0
        for x in arr:
            if integerInArray(arr, x + 1):
                count += 1
        return count

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 11 апреля и приходи учиться! Старт ИТ-интенсива уже 14 апреля. Подать заявку #реклама 16+ t1.ru О рекламодателе

Привет ребята, мне на easyoffer.ru нужен: 🐍 Middle/Senior Python Developer Стек: DRF, PostgreSQL, Redis, Celery, Docker, Sentry Задачи: 🟠Разработка и поддержка REST API для новых фичей 🟠Интеграция с веб-сервисами и внешними API 🟠Подключение и поддержка платежных систем 🟠Написание юнит- и интеграционных тестов 🟠Оптимизация производительности и масштабирование 🟠Взаимодействие с ML-моделями — будет плюсом Ожидания: 🟠2+ лет опыта DRF 🟠Опыт интеграций платежных систем 🟠Опыт работы с PostgreSQL, Celery, Redis, Docker 🟠Умение проектировать архитектуру REST-API 🟠Ответственный подход к качеству кода и тестированию Опыт в стартапах и небольших командах будет плюсом Условия: – Частичная занятость (2-3 часа в день) – Удаленная работа – Свободный график – Почасовая оплата ✈ Если вас заинтересовала вакансия, напишите мне @kivaiko 1. Резюме 2. Ссылку на github 3. Комфортную ставку за час

Задача: 972. Equal Rational Numbers Сложность: hard Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа. Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов: <ЦелаяЧасть> Например, 12, 0 и 123. <ЦелаяЧасть><.><НеповторяющаясяЧасть> Например, 0.5, 1., 2.12 и 123.0001. <ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)> Например, 0.1(6), 1.(9), 123.00(1212). Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например: 1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66). Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:

from math import gcd

class Fraction:
    def __init__(self, n, d):
        g = gcd(n, d)
        self.n = n // g
        self.d = d // g

    def iadd(self, other):
        numerator = self.n * other.d + self.d * other.n
        denominator = self.d * other.d
        g = gcd(numerator, denominator)
        self.n = numerator // g
        self.d = denominator // g

class Solution:
    def isRationalEqual(self, S: str, T: str) -> bool:
        f1 = self.convert(S)
        f2 = self.convert(T)
        return f1.n == f2.n and f1.d == f2.d

    def convert(self, S: str) -> Fraction:
        state = 0
        ans = Fraction(0, 1)
        decimal_size = 0

        for part in S.split('.'):
            state += 1
            if not part:
                continue
            x = int(part)
            sz = len(part)

            if state == 1:
                ans.iadd(Fraction(x, 1))
            elif state == 2:
                ans.iadd(Fraction(x, 10 ** sz))
                decimal_size = sz
            else:
                denom = 10 ** decimal_size
                denom *= 10 ** sz - 1
                ans.iadd(Fraction(x, denom))
        return ans

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