Формулировки задач
и вопросы до решения

Категория

Работа с условием

Уровень

Начальный

Опирается на

Глава 10.1; глава 9.2: части условия, признаки и контракт функции

Зачем это знать

Узнавать окно переменного размера по условию и уточнять задачу до кода

§1Из чего состоит условие

Условие задачи на окно состоит из тех же частей, что в главах 8.2 и 9.2: легенда, входные данные, результат, ограничения. В задаче на окно фиксированной длины во входных данных была длина окна k. В задаче этого модуля на её месте стоят две другие части. Первая — требование к отрезку, из которого получается условие допустимости. Вторая — направление поиска: нужен самый короткий отрезок или самый длинный.

Легенда подсказывает ещё одно свойство входа. Число заказов не бывает отрицательным, поэтому каждый новый час сумму не уменьшает. От этого свойства зависит, подходит ли окно, поэтому его проверяют вопросом до решения, это разобрано в §4 и §5.

§2Восемь формулировок

Ниже восемь условий без подсказки, какую технику применить. Семь из них — пересказы задач LeetCode, ссылка в шапке карточки; условия сверены с сайтом. Восьмая — задача из статьи журнала Яндекс Образования, процитированной в главе 10.1. Кнопка под карточками подсвечивает слова, по которым узнаётся окно переменного размера.

В задачах 1004 и 1493 требование к отрезку названо не прямо. В условии говорится о замене и удалении элементов, но массив менять не нужно. «Заменить не больше k нулей» означает, что подходит любой отрезок, в котором нулей не больше k. «Удалить один элемент» означает, что в отрезке допускается не больше одного нуля. После такого пересказа обе задачи становятся поиском самого длинного отрезка со счётчиком нулей.

§3Признаки в условии

Подсвеченные слова повторяются от задачи к задаче. Технику выбирают по сочетанию трёх признаков: участок идёт подряд, его длина в условии не задана, и на содержимое участка стоит ограничение.

§4Когда окно переменного размера не подходит

Окну переменного размера нужны три условия. Участок непрерывный. Длина участка в условии не задана. Расширение окна меняет проверяемую величину только в одну сторону, а сжатие — только в обратную. Если одно из них не выполнено, нужна другая техника.

Первый случай проверен запуском. Окно, которое расширяется при сумме меньше порога и сжимается при сумме не меньше порога, запущено на списке [3, -2, 5] с порогом 5. Рядом — ответ перебора всех подотрезков.

§5Разговор с интервьюером о минимальном отрезке

Первая задача КТП занятия 10 — найти минимальный отрезок с суммой не меньше S. Слева — условие в том виде, в каком его произнёс интервьюер. Справа — вопросы. После каждого вопроса появляются ответ интервьюера и то, что он меняет в решении, а слева — новое уточнение. Порядок вопросов любой.

Первый вопрос решает, применима ли техника: при ответе «да, бывают отрицательные» решение было бы другим. Третий и пятый вопросы задают поведение функции на входах, для которых ответа нет. В КТП контроль занятия 10 требует, чтобы кандидат объяснял условие while. Это условие получается из четвёртого вопроса: знак >= в нём стоит потому, что сумма ровно s подходит.

§6Контракт функции

После разговора условие записывается как контракт: что функция принимает, что возвращает и что делает на неверном входе. В таблице для каждого ответа указано, какую часть решения он определяет.

def shortest_window(nums, s):
    """Окно переменного размера. Задача 1 занятия 10.

    nums — список целых неотрицательных чисел, может быть пустым.
    s — порог суммы, s >= 1; иначе ValueError.
    Возвращает длину самого короткого отрезка подряд с суммой не меньше s.
    Если такого отрезка нет, возвращает 0. Список не меняется.
    Время O(n), память O(1).
    """

Контракт совпадает с условием LeetCode 209 во всём, кроме двух мест. На сайте числа строго положительные, а пустого списка и неверного порога во входе не бывает. Функция из этой главы принимает более широкий вход и на входах сайта возвращает те же ответы. Для отправки на сайт её тело переносят в функцию minSubArrayLen(target, nums): там порог стоит первым параметром.

§7Вопросы к задаче о подстроке

Вторая задача КТП — найти самую длинную подстроку без повторов. Чисел и суммы в ней нет, поэтому вопросы другие: они про то, что считается символом и что считается повтором. Разговор строится так же — каждый вопрос заканчивается изменением в решении. Сама задача разобрана в главе 10.5.

def longest_unique(text):
    """Окно переменного размера с частотной картой. Задача 2 занятия 10.

    text — строка из любых символов, может быть пустой.
    Возвращает длину самой длинной подстроки, в которой все символы разные.
    Регистр различается: 'a' и 'A' — разные символы. Для пустой строки — 0.
    Время O(n), память O(m), m — число разных символов строки.
    """

§8Тестовые примеры до кода

Как и в главе 9.2, после вопросов записывают входы с ответами. Каждый пример проверяет свой класс входа: обычный случай, ответы на уточнения и случаи без ответа. Ответы получены запуском эталонных решений на Python 3.12.

Для второй задачи контроль КТП называет два класса входа прямо: «Проверяются дубликаты и пустая строка». Оба есть в таблице.

Пример 'abba' проверяет случай, когда повторяется символ, который уже вышел из окна: вторая буква a повтором для окна 'b' не является. Этот пример понадобится в главе 10.5. Все примеры из обеих таблиц войдут в тесты стартового набора.

§9Тренажёр: выберите технику

Ниже шесть условий. Для каждого выберите способ, который подходит при указанных ограничениях и работает быстрее остальных вариантов. После ответа открывается разбор верного и выбранного вариантов.