Алгоритмы на массивах · модуль 10 · окно переменного размера
Глава 10.10
Практика, шпаргалка
и домашнее задание
В этой главе работа на паре по стартовому набору lesson_10: четыре функции, 39 тестов и замер. Затем вопросы для контроля по КТП, шпаргалка, словарь модуля и домашнее задание: довести решения, найти три ошибки на границе окна и решить новую задачу с LeetCode. В конце — порядок сдачи и что будет на занятии 11.
- Категория
- Практика
- Время на паре
- Около 60 минут после 30 минут теории
- Проверка
- pytest, 39 тестов
- Результат
- Папка
portfolio/lesson_10с решениями, замером и заметкой
§1Стартовый набор
В архиве всё, что нужно для работы на паре и дома. Функции в solution.py пустые: в каждой стоит raise NotImplementedError, поэтому до начала работы все 39 тестов падают. Тесты границ из главы 10.6 в tests.py те же, к ним добавлены тесты задач и сравнение с перебором.
| Функция в solution.py | Задача | Глава |
|---|---|---|
longest_within | 0 · самый длинный отрезок в пределах лимита, схема прохода | 10.3 |
shortest_window | 1 · минимальный отрезок с суммой не меньше S, задача КТП | 10.4 |
longest_unique | 2 · подстрока без повторов, задача КТП | 10.5 |
total_fruit | расширение · LeetCode 904 | 10.8 |
§2Порядок работы на паре
Работа идёт в папке lesson_10 на своём компьютере, нужен Python с pytest. Если Python ещё не настроен, начните с песочниц в главах 10.3–10.5: там те же функции пишутся прямо на странице и проверяются похожими тестами. Сдаётся всё равно solution.py с зелёным pytest.
- Скопируйте папку
lesson_10вportfolio/lesson_10/личного репозитория и выполнитеpython -m pytest tests.py -v. Все 39 тестов должны упасть: так проверяется, что pytest нашёл файлы и запустил тесты. - До кода откройте
initial_attempt.txtи запишите вопросы к условиям задач 1 и 2 и примеры с ответами: «отрезка нет», сумма точно равнаs, пустая строка, повторы. Образец — глава 10.2. - Напишите
longest_within. Проверка:python -m pytest tests.py -k within. - Напишите
shortest_window. Проверка:-k shortest, затем тесты границ:-k "bad_s or shortest_edges". Если тест падает, найдите симптом в сводке главы 10.9, §1. - Напишите
longest_unique:-k unique. - Запустите замер:
python bench.py > bench_results.txt. Он идёт около 25 секунд. - Заполните
complexity_note.mdдля трёх обязательных функций. - Если осталось время —
total_fruit,-k fruit. - Если и это готово —
extra.py: единицы с заменой нулей, единицы после удаления, число подотрезков без повторов. Проверка:python -m pytest tests_extra.py -v.
Код функций есть в главах модуля. На контроле занятия условие while и состояние окна объясняются своими словами, поэтому сначала пишется своя версия по схеме из главы 10.3, не открывая код. Если тест падает, откройте пошаговый прогон нужной главы и сравните шаги со своим кодом.
§3Что сдаётся с пары
Работа на паре принята, когда
python -m pytest tests.py -k within — без падений.-k shortest, -k unique и тесты границ -k "bad_s or edges" — без падений.initial_attempt.txt вопросы и примеры к обеим задачам.bench_results.txt с выводом bench.py на своей машине.while и место записи ответа — контроль КТП.§4Вопросы для контроля
В КТП контроль занятия записан так: «Кандидат объясняет условие while и состояние окна. Проверяются дубликаты и пустая строка». Ниже эти требования разложены на вопросы и на то, что должно прозвучать в ответе. Главы в правом столбце — где это разобрано.
| Вопрос | Что должно прозвучать в ответе | Где разобрано |
|---|---|---|
| Что хранится в состоянии окна и как оно меняется? | Сумма или частотная карта для окна с l по r; при расширении добавляется пришедший элемент, при сжатии убирается ушедший до сдвига l | 10.3, §4; 10.5, §3 |
| Почему у цикла такое условие? | Самый короткий отрезок — сжимаем, пока окно подходит; самый длинный — пока окно недопустимо. В задаче о подстроке достаточно проверить счётчик пришедшего символа | 10.4, §2; 10.5, §3 |
| Зачем здесь цикл while? | Одного сжатия может не хватить: на 'abba' версия с if возвращает 3 | 10.5, §7 |
| Почему вложенный while не даёт O(n²)? | l только растёт и не обгоняет r, сдвигов не больше 2n; свои числа из замера | 10.3, §5; 10.7 |
| Какие тесты проверяют дубликаты и пустую строку? | Все символы одинаковые, повтор рядом, повтор символа вне окна, пробел; пустая строка — 0 | 10.6, §5 |
| Что функция делает, если отрезка нет, и при неверном пороге? | Отрезка нет — 0, это обычный ответ; порог меньше 1 — ValueError | 10.6, §4 |
§5Шпаргалка по модулю
l = 0
for r in range(len(nums)):
добавить nums[r] в состояние
while окно недопустимо:
убрать nums[l] из состояния
l += 1
best = max(best, r - l + 1)Ответ записывается после цикла: там окно допустимо. O(n).
for r in range(len(nums)):
total += nums[r]
while total >= s:
записать длину r - l + 1
total -= nums[l]
l += 1Ответ записывается внутри цикла: после цикла окно уже не подходит. best = 0 значит «отрезка нет».
count[ch] = count.get(ch, 0) + 1
while count[ch] > 1:
count[text[l]] -= 1
l += 1Уменьшается счётчик символа на левой границе. Если условие считает ключи, len(count), ключ со счётчиком 0 удаляют.
«подряд», «подмассив», «подстрока» и ограничение на содержимое без числа k: «сумма не меньше S», «без повторов», «не больше k нулей», «не больше двух видов».
Бывают ли отрицательные числа. Что вернуть, если отрезка нет. Подходит ли сумма точно на пороге. Различается ли регистр, считается ли пробел символом. Может ли вход быть пустым.
Отрицательные числа: по сумме нельзя решить, какую границу сдвигать. Подпоследовательность: элементы не подряд. Длина задана числом: окно фиксированной длины, модуль 9.
Перебор — O(n²) в худшем случае, когда отрезка нет; на коротких ответах O(n·L). Окно — O(n) на любых данных. На 8000 элементах перебор медленнее в 4000 раз.
Запись не в том месте относительно while. > вместо >=. if вместо while. l += 1 до вычитания. count[ch] -= 1. Нет проверки s < 1. Нет del при len(count).
§6Словарь модуля
| Термин | Что означает | Где введён |
|---|---|---|
| Окно переменного размера | Правая граница идёт по списку, левая сдвигается вслед за ней, пока этого требует условие допустимости | 10.1 |
| Условие допустимости | Требование задачи к отрезку, записанное как проверка за O(1) по состоянию окна | 10.1, 10.3 |
| Расширение, сжатие | Сдвиг правой границы с добавлением элемента в состояние; сдвиг левой с удалением элемента из состояния | 10.1, 10.3 |
| Подходящее окно | Окно, для которого выполнено условие задачи на самый короткий отрезок | 10.4 |
| Частотная карта | Словарь «значение → сколько раз оно встречается в окне» | 10.5 |
| Граничный вход | Вход на краю допустимого: пустой, из одного элемента, без ответа, с порогом точно на сумме | 10.6 |
| Инвариант окна | Состояние соответствует границам окна, и после цикла окно допустимо (или уже не подходит, для самого короткого) | 10.3, §8 |
| Монотонность границ | Обе границы двигаются только вправо; из неё следует O(n) для while внутри for | 10.3, §5 |
§7Домашнее задание
Максим Николаевич не хочет задавать домашнее задание. Но очень хочет
| Задача | Что сделать | Где помогут |
|---|---|---|
| 1 · Довести решения | solution.py проходит все 39 тестов. bench_results.txt — ваш замер. complexity_note.md заполнен по трём функциям: состояние окна, условие while и откуда оно следует, инвариант, время, память и таблица замера. | Главы 10.3–10.7 |
| 2 · Три ошибки на границе | В bugs_10.py функции max_ones, longest_k_distinct, shortest_at_least. Каждая верно отвечает на обычных входах и ошибается или падает на граничном. Для каждой: вход, на котором ответ неверный; падающий тест в tests_bugs_10.py; исправление одной строки; повторный прогон. Вывод pytest — в bugs_run.txt. | Глава 10.6 и сводка ошибок в главе 10.9 |
| 3 · Отрезки с произведением меньше k | Функция count_small_products(nums, k), LeetCode 713: сколько отрезков подряд имеют произведение строго меньше k. Числа от 1 и больше, k — любое целое, в том числе 0 и 1. Пример: [10, 5, 2, 6], k = 100 → 8. Время O(n), память O(1). Не меньше шести своих тестов: k = 0, k = 1, пустой список, один элемент, отрезок с произведением ровно k. | Глава 10.5, §9: подсчёт отрезков; глава 10.6: границы |
Тест к bugs_10.py засчитывается, если до исправления он падает, а после — проходит. Тест, который проходит и на ошибочной версии, ошибку не находит.
§8Порядок сдачи
| Файлы | portfolio/lesson_10/: solution.py, tests.py, bench_results.txt, complexity_note.md, initial_attempt.txt, bugs_10.py, tests_bugs_10.py, bugs_run.txt |
|---|---|
| Ветка и PR | Ветка hw-10, коммиты с содержательными сообщениями, Pull Request в собственную main. Объяснение решения проверяется по чек-листу из главы 10.6, §7 |
| Срок | До начала занятия 11 |
| Проверяем | Зелёный pytest по всем файлам; три теста к bugs_10.py, которые падают до исправления; шесть тестов к count_small_products; заметка без пустых пунктов |
| ИИ | Код и тесты пишете сами: на контроле занятия вы объясняете условие while и состояние окна своими словами. Оформление .md и редактуру формулировок можно поручить модели. Я сам так делаю всегда, поэтому и вам запрещать не буду. |
§9Что дальше
Перед занятием 11 задачи модуля можно прорешать в формате собеседования: в главе 10.11 задачи на окно переменного размера идут по этапам секции с секундомером.
Занятие 11 — префиксные суммы и запросы на диапазоне. В главе 10.2 окно не подошло к отрезкам с отрицательными числами: по сумме нельзя было решить, какую границу сдвигать. Префиксная сумма решает такие задачи иначе: сумма любого отрезка [l, r) вычисляется одной разностью двух заранее посчитанных чисел, и знак элементов на это не влияет.