Алгоритмы на массивах · модуль 9 · скользящее окно
Глава 9.10
Практика, шпаргалка
и домашнее задание
В этой главе работа на паре по стартовому набору lesson_09: пять функций, 34 теста и замер. Затем вопросы для review по контролю КТП, шпаргалка, словарь модуля и домашнее задание: довести решения, найти три ошибки на границе окна и решить новую задачу с LeetCode. В конце — порядок сдачи и что будет на занятии 10.
- Категория
- Практика
- Время на паре
- Около 70 минут после 20 минут теории
- Проверка
- pytest, 34 теста
- Результат
- Папка
portfolio/lesson_09с решениями, замером и заметкой
§1Стартовый набор
В архиве всё, что нужно для работы на паре и дома. Функции в solution.py пустые: в каждой стоит raise NotImplementedError, поэтому до начала работы все 34 теста падают. Тесты границ из главы 9.6 в tests.py те же.
| Функция в solution.py | Задача | Глава |
|---|---|---|
window_sums_slices, window_sums | 0 · сумма каждого окна срезами и сдвигом | 9.3 |
best_window | 1 · лучший отрезок длины k, задача КТП | 9.4 |
max_events | 2 · события во временном окне, задача КТП | 9.5 |
max_vowels | расширение · LeetCode 1456 | 9.4, §8 |
§2Порядок работы на паре
Работа идёт в папке lesson_09 на своём компьютере, нужен Python с pytest. Если Python ещё не настроен, начните с песочниц в главах 9.3–9.6: там те же функции пишутся прямо на странице и проверяются похожими тестами. Сдаётся всё равно solution.py с зелёным pytest.
- Скопируйте папку
lesson_09вportfolio/lesson_09/личного репозитория и выполнитеpython -m pytest tests.py -v. Все 34 теста должны упасть — так проверяется, что pytest видит файлы. - До кода откройте
initial_attempt.txtи запишите три вопроса к условию задачи 1 и пять примеров с ответами, среди нихk = 1,k = nи неверныйk. Образец — глава 9.2. - Напишите
window_sums_slices, затемwindow_sums. Проверка:python -m pytest tests.py -k sums. - Напишите
best_window. Проверка:-k best, затем тесты границ:-k "bad_k or k_is". Если тест границы падает, сравните код со строками таблицы из главы 9.6, §1. - Напишите
max_events:-k events. - Запустите замер:
python bench.py > bench_results.txt. Он идёт около 35 секунд. - Заполните
complexity_note.mdдля четырёх обязательных функций. - Если осталось время —
max_vowels,-k vowels. - Если и это готово —
extra.py: перекраска блоков, подстроки из трёх разных букв, сердитый продавец. Проверка:python -m pytest tests_extra.py -v.
Код функций есть в главах модуля. На занятии 10 окно переменной длины строится на этом коде, поэтому сначала пишется своя версия по правилу из главы, не открывая код. Если тест падает, откройте пошаговый прогон нужной главы и сравните шаги со своим кодом.
§3Что сдаётся с пары
Работа на паре принята, когда
python -m pytest tests.py -k sums — без падений.-k best, -k events и тесты границ -k "bad_k or k_is or bad_w or right_edge" — без падений.initial_attempt.txt три вопроса и пять примеров.bench_results.txt с выводом bench.py на своей машине.best_window вы можете назвать состояние окна, объяснить знак > и начальное значение best.§4Вопросы для review
В КТП контроль занятия записан так: «Оценка O(n), тесты k=0/1/n и неверного k. Git review на корректность обновления окна». Ниже эти требования разложены на вопросы и на то, что должно прозвучать в ответе. Главы в правом столбце — где это разобрано.
| Вопрос на review | Что должно прозвучать в ответе | Где разобрано |
|---|---|---|
| Почему сдвиг окна — O(n), а срезы — O(n·k)? | Срез заново читает k элементов для каждого из n − k + 1 окон; сдвиг исправляет сумму по двум изменившимся элементам за O(1). Свои числа из опыта 2 замера | 9.3, 9.7 |
| Почему вложенный while в max_events не даёт O(n²)? | l только растёт и не превышает r, за всю работу сдвигается не больше n раз | 9.5, §4 |
| Какие тесты проверяют границы и что проверяет каждый? | k = 1 — окно из одного элемента, сдвигов больше всего. k = n — одно окно, сдвигов нет. k = 0, k < 0, k > n и пустой список — ValueError | 9.6, §3 и §5 |
| Как проверить, что окно обновляется верно? | Первое окно — ровно k элементов и оно учтено; цикл с range(k, n); ушедший — nums[r − k]; сдвиг до сравнения; знак сравнения из условия | 9.6, §7 |
| Почему на неверный k — исключение? | Без проверки функция молча возвращает ответ для несуществующего окна; ValueError останавливает программу в строке вызова | 9.6, §2 и §4 |
§5Шпаргалка по модулю
total = sum(nums[:k])
best = total
for r in range(k, len(nums)):
total += nums[r] - nums[r - k]
best = max(best, total)r — пришедший, r − k — ушедший. Окно после сдвига — nums[r − k + 1:r + 1]. O(n), O(1).
l = 0
for r in range(len(times)):
while times[r] - times[l] >= w:
l += 1
best = max(best, r - l + 1)Окно [s, s + w): при >= событие на правой границе не входит. l монотонный — O(n).
«длины k», «за k минут», «подряд», «подмассив», «подстрока» — окно фиксированной длины. «сумма не меньше S», «без повторов» без числа k — окно переменной длины, занятие 10.
Что вернуть: значение, начало окна или само окно. Какое окно при равных ответах. Бывают ли отрицательные числа. Каким бывает k, что делать при k = 0 и k > n. Для окна по времени — открыта ли правая граница.
Сумма, счётчик гласных, число белых блоков — исправляются по ушедшему и пришедшему за O(1). Максимум окна так не исправить — нужен дек, занятие 25.
k = 1 — окна совпадают с элементами. k = n — одно окно, цикл не выполняется. Неверный k и пустой список — ValueError до работы с окнами.
Срезы — O(n·k): при k = 100 время ×2 по n, при k = n/2 — ×4. Сдвиг — O(n) при любом k. Элемент среза дешевле шага цикла, поэтому при малых k разница меньше оценки.
nums[r − k + 1] вместо nums[r − k]. Первое окно не в ответе. best = 0 при отрицательных. >= вместо > при «самом левом». range(k + 1, …). r − l вместо r − l + 1.
§6Словарь модуля
| Термин | Что означает | Где введён |
|---|---|---|
| Подотрезок, подмассив | Несколько элементов, которые стоят подряд; в Python — срез a[l:r] | 9.1 |
| Окно | Подотрезок, заданный полуинтервалом [l, r); длина r − l | 9.1 |
| Скользящее окно фиксированного размера | Окно длины k проходит список с шагом в одну позицию; окон n − k + 1 | 9.1, 9.3 |
| Окно переменной длины | Длину окна задаёт условие, числа k в задаче нет; занятие 10 | 9.1, 9.2 |
| Состояние окна, rolling state | Ответ для текущего окна, который исправляется при сдвиге за O(1) | 9.3 |
| Сдвиг окна | Переход к соседнему окну: плюс пришедший элемент, минус ушедший | 9.3 |
| Окно по времени | Окно [s, s + w) на оси времени; число событий в нём меняется | 9.5 |
| Монотонность указателя | Указатель движется только в одну сторону; из неё следует O(n) и для цикла while внутри for | модуль 8, 9.5 |
| Контракт функции | Что функция принимает, что возвращает и что делает на неверном входе | 9.2, 9.6 |
§7Домашнее задание
Максим Николаевич не хочет задавать домашнее задание. Но очень хочет
| Задача | Что сделать | Где помогут |
|---|---|---|
| 1 · Довести решения | solution.py проходит все 34 теста. bench_results.txt — ваш замер. complexity_note.md заполнен по четырём функциям, в таблице замера — рост времени в трёх опытах. | Главы 9.3–9.7 |
| 2 · Три ошибки на границе | В bugs_09.py функции count_strong_windows, min_window, count_in_window. Каждая верно отвечает на обычных входах и ошибается на граничном. Для каждой: вход, на котором ответ неверный; падающий тест в tests_bugs_09.py; исправление одной строки; повторный прогон. Вывод pytest — в bugs_run.txt. | Глава 9.6, особенно §1 и чек-лист review |
| 3 · Окна со средним не ниже порога | Функция count_good_windows(arr, k, threshold), LeetCode 1343: сколько окон длины k имеют среднее не меньше threshold; неверный k — ValueError. Пример: [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4 → 3. Время O(n), память O(1). Не меньше пяти своих тестов: k = 1, k = n, неверный k, окно со средним ровно на пороге. | Главы 9.3 и 9.4: сдвиг и сравнение с порогом |
Тест к bugs_09.py засчитывается, если до исправления он падает, а после — проходит. Тест, который проходит и на ошибочной версии, ошибку не ловит.
§8Порядок сдачи
| Файлы | portfolio/lesson_09/: solution.py, tests.py, bench_results.txt, complexity_note.md, initial_attempt.txt, bugs_09.py, tests_bugs_09.py, bugs_run.txt |
|---|---|
| Ветка и PR | Ветка hw-09, коммиты с содержательными сообщениями, Pull Request в собственную main. Review проводится по чек-листу из главы 9.6, §7 |
| Срок | До начала занятия 10 |
| Проверяем | Зелёный pytest по всем файлам; три теста к bugs_09.py, которые падают до исправления; пять тестов к count_good_windows; заметка без пустых пунктов |
| ИИ | Код и тесты пишете сами: на занятии 10 окно переменной длины строится на этом коде. Оформление .md и редактуру формулировок можно поручить модели. Я сам так делаю всегда, поэтому и вам запрещать не буду. |
§9Что дальше
Перед занятием 10 задачи модуля можно прорешать в формате собеседования: в главе 9.11 восемь задач на окно, каждая по этапам секции с секундомером.
Занятие 10 — скользящее окно переменного размера. Длину окна там задаёт условие: «сумма не меньше S», «без повторяющихся символов». Правая граница расширяет окно, левая сжимает его, пока условие нарушено, — так же, как левая граница в задаче о событиях из главы 9.5. По КТП на занятии решаются задачи «минимальный отрезок с суммой не меньше S» и «подстрока без повторов», LeetCode 209 и 3.