Python | LeetCode

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по 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

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

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

Задача: 1162. As Far from Land as Possible Сложность: medium Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1. Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|. Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

👨‍💻 Алгоритм: 1⃣Итерируйте по матрице и вставьте координаты ячеек с землёй в очередь. Инициализируйте переменную distance значением -1 для хранения текущего шага обхода в ширину (BFS). Также создайте копию матрицы visited для пометки ячеек с водой как посещённые, чтобы не вставлять их снова в очередь. 2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance. 3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1). 😎 Решение:

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [row[:] for row in grid]
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    q.append((i, j))
        
        distance = -1
        while q:
            qSize = len(q)
            for _ in range(qSize):
                landCell = q.popleft()
                for dir in directions:
                    x, y = landCell[0] + dir[0], landCell[1] + dir[1]
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and visited[x][y] == 0:
                        visited[x][y] = 1
                        q.append((x, y))
            distance += 1
        
        return -1 if distance == 0 else distance

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

Стать бэкендером в Яндексе за несколько дней 12–17 апреля устраиваем Week Offer Backend: за несколько дней можно пройти технические секции и попасть в Яндекс. Для этого нужно зарегистрироваться и решить несколько задач в Контесте. Ищем классных бэкенд-разработчиков с опытом работы от 3 лет на C++, Python, Java/Kotlin или Go, готовых работать в офисном или гибридном режиме в России. Вы сможете выбрать одну из команд: Яндекс Пэй, Яндекс ID, Яндекс Плюс, Яндекс Сплит, Яндекс Сейвы, Яндекс 360. Можно пообщаться с нанимающими менеджерами и выбрать самый интересный проект. Если всё пройдёт хорошо, сразу же получите офер. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 1063. Number of Valid Subarrays Сложность: hard Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        ans = 0
        st = []
        
        for i in range(len(nums)):
            while st and nums[i] < nums[st[-1]]:
                ans += (i - st.pop())
            st.append(i)
        
        while st:
            ans += (len(nums) - st.pop())
        
        return ans

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