Алгоритмы на массивах · модуль 8 · два указателя
Глава 8.12
Практика, шпаргалка
и домашнее задание
В этой главе работа на паре по стартовому набору lesson_08: пять функций, 37 тестов и замер. Затем вопросы для review по КТП, шпаргалка, словарь модуля и домашнее задание: довести решения, найти три ошибки на границе и решить новую задачу на указатели навстречу. В конце — порядок сдачи и критерии.
- Категория
- Практика
- Время на паре
- Около 50 минут
- Проверка
- pytest, 37 тестов
- Результат
- Папка
portfolio/lesson_08с решениями, замером и заметкой
§1Стартовый набор
В архиве всё, что нужно для работы на паре и дома. Функции в solution.py пустые: в каждой стоит raise NotImplementedError, поэтому до начала работы все тесты падают.
§2Порядок работы на паре
Работа идёт в папке lesson_08 на своём компьютере, нужен Python с pytest. Если Python ещё не настроен, начните с песочниц в главах 8.4, 8.7, 8.8 и 8.11: там те же функции пишутся прямо на странице и проверяются похожими тестами. Сдаётся всё равно solution.py с зелёным pytest.
- Скопируйте папку
lesson_08вportfolio/lesson_08/личного репозитория и выполнитеpython -m pytest tests.py -v. Все 37 тестов должны упасть сNotImplementedError— так проверяется, что pytest видит файлы. - До кода откройте
initial_attempt.txtи запишите три вопроса к условию задачи 1 и пять примеров с ответами. Образец — главы 8.3 и 8.6. - Напишите
pair_sum_brute. Запуститеpython -m pytest tests.py -k pair: тесты для перебора должны пройти, для указателей — ещё падать. - Напишите
pair_sum. Если какой-то тест падает, найдите его в блоках «Какие тесты ловят» главы 8.9: там показано, какая ошибка его роняет и как она выглядит в прогоне. - Напишите
dedup_sortedи проверьте:-k dedup. Затемcompress:-k compress. - Запустите замер:
python bench.py > bench_results.txt. Он идёт около 20 секунд. - Заполните в
complexity_note.mdразделы для трёх обязательных функций. - Если осталось время —
move_zeros,-k zeros. - Если и это готово —
extra.py: наибольший объём воды, палиндром с пропуском знаков, тройки с нулевой суммой. Проверка:python -m pytest tests_extra.py -v.
Код функций есть в главах модуля. На занятии 9 решение объясняется без подсказок, поэтому сначала пишется своя версия по правилу из главы, не открывая код. Если тест падает, откройте пошаговый прогон нужной главы и сравните шаги со своим кодом.
§3Что сдаётся с пары
Работа на паре принята, когда
python -m pytest tests.py -k pair — 21 passed.-k dedup и -k compress без падений.initial_attempt.txt три вопроса и пять примеров.bench_results.txt с выводом bench.py на своей машине.pair_sum вы можете назвать инвариант и объяснить, почему указатели не пропускают пару, — как в главе 8.5, §6.§4Вопросы для review
В КТП контроль занятия записан так: «Сопоставить O(n²) и O(n) с экспериментом. На review объяснить монотонность указателей, границы применимости и возможное влияние сортировки на итоговую сложность». Ниже эти требования разложены на вопросы и на то, что должно прозвучать в ответе. Главы в правом столбце — где это разобрано.
| Вопрос на review | Что должно прозвучать в ответе | Где разобрано |
|---|---|---|
| Как ваш замер подтверждает O(n²) у перебора и O(n) у указателей? | При удвоении n время перебора растёт примерно в 4 раза, указателей — примерно в 2; назвать свои числа из bench_results.txt | 8.4, 8.10 |
| Что такое монотонность указателей и почему из неё следует O(n)? | Каждый указатель движется только в одну сторону и не возвращается; каждый шаг сдвигает хотя бы один, поэтому шагов не больше n | 8.5, §4 |
| Когда указатели навстречу применять нельзя? | Вход не отсортирован и нужны исходные индексы; пример из главы, где пара теряется на неотсортированном списке; запасной способ — словарь | 8.2, 8.5, 8.10 |
| Как сортировка влияет на итоговую сложность? | Если вход не отсортирован, добавляется O(n log n), и итог становится O(n log n) вместо O(n); копия списка — ещё O(n) памяти | 8.10, 8.11 |
§5Шпаргалка по модулю
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
if s == target: return (i, j)
if s < target: i += 1
else: j -= 1
return NoneНужен отсортированный вход. Каждый ход исключает один элемент. O(n), O(1).
w = 0
for r in range(len(a)):
if оставить(a[r]):
a[w] = a[r]
w += 1
del a[w:]
return ww ≤ r, запись не затирает непрочитанное. Для переноса нулей — обмен вместо записи.
«отсортирован», «пара», «сумма двух» — навстречу. «на месте», «верните длину», «подряд» — в одну сторону. «два отсортированных» — по двум спискам. «за один проход», «O(n)» — перебор исключён.
Отсортирован ли вход и в какую сторону. Можно ли взять элемент дважды. Что вернуть, если ответа нет. Индексы или значения. Можно ли менять вход. Размер n и ограничение по памяти.
i < j — когда нужна пара разных элементов (задача 1). i <= j — когда каждый элемент нужно отнести к группе (разделение). В одну сторону — for r in range(len(a)).
Перебор пар — n·(n − 1) / 2, O(n²): при удвоении n время ×4. Указатели — не больше n − 1 шагов, O(n): ×2. Словарь — O(n) и O(n) памяти. Сортировка + указатели — O(n log n).
Если пара с суммой target есть, она лежит на участке с i по j. Сортировка нужна во второй проверке: a[j] — самый большой элемент участка.
<= вместо < — пара (k, k). Перепутаны ветки — None при существующей паре. Запись вместо обмена — пропали нули. Цикл по парам соседей — пропал последний элемент.
§6Словарь модуля
| Термин | Что означает | Где введён |
|---|---|---|
| Указатель | Переменная с номером позиции в списке, значение которой меняется по правилу алгоритма | 8.1 |
| Два указателя | Техника прохода, в которой два индекса двигаются по данным и на каждом шаге сдвигается хотя бы один | 8.1 |
| Указатели навстречу | Старт с двух концов, указатели сходятся; нужен порядок в данных | 8.1, 8.4 |
| Указатели в одну сторону | Оба идут слева направо: один читает, другой пишет или ищет во второй последовательности | 8.1, 8.7 |
| Перебор, brute force | Проверка всех вариантов, например всех пар: n·(n − 1) / 2 проверок, O(n²) | 8.4 |
| Инвариант | Утверждение, верное перед каждой проверкой условия цикла; проверяется инициализацией, сохранением и завершением | 8.5 |
| Монотонность указателей | Указатель движется только в одну сторону и не возвращается; отсюда оценка O(n) | 8.5 |
| Изменение на месте | Результат записывается в тот же список, новый не создаётся; дополнительная память O(1) | 8.7 |
| Кодирование длин серий, RLE | Серия одинаковых элементов подряд записывается как элемент и число повторов | 8.7 |
| Подпоследовательность | Элементы в исходном порядке, между которыми могут быть пропуски | занятие 7, 8.7 |
| Разделение, partition | Перестановка на месте: сначала элементы с верным условием, потом остальные | 8.8 |
| Interview canvas | Порядок решения на секции: условие → уточнения → примеры → перебор → оптимизация → сложность → код → проверка | 8.11 |
§7Домашнее задание
Максим Николаевич не хочет задавать домашнее задание. Но очень хочет
| Задача | Что сделать | Где помогут |
|---|---|---|
| 1 · Довести решения | solution.py проходит все 37 тестов. bench_results.txt — ваш замер. complexity_note.md заполнен по пяти функциям, в таблице замера — рост времени при удвоении n. | Главы 8.4–8.8, 8.10 |
| 2 · Три ошибки на границе | В bugs_08.py функции count_cheap_pairs, dedup_keep_two, is_mirror. Каждая верно отвечает на обычных входах и ошибается на граничном. Для каждой: вход, на котором ответ неверный; падающий тест в tests_bugs_08.py; исправление одной строки; повторный прогон. Вывод pytest — в bugs_run.txt. | Глава 8.9, особенно §1 и сводка |
| 3 · Квадраты отсортированного списка | Функция sorted_squares(nums), LeetCode 977: nums по возрастанию, есть отрицательные; вернуть новый список квадратов по возрастанию за O(n), без sorted. Пример: [-7, -3, 0, 2, 9] → [0, 4, 9, 49, 81]. Самый большой квадрат стоит на одном из концов. Не меньше пяти своих тестов: пустой список, один элемент, все отрицательные, все положительные. | Главы 8.4 и 8.5: указатели навстречу |
Тест к bugs_08.py засчитывается, если до исправления он падает, а после — проходит. Тест, который проходит и на ошибочной версии, ошибку не ловит.
§8Порядок сдачи
| Файлы | portfolio/lesson_08/: solution.py, tests.py, bench_results.txt, complexity_note.md, initial_attempt.txt, bugs_08.py, tests_bugs_08.py, bugs_run.txt |
|---|---|
| Ветка и PR | Ветка hw-08, коммиты с содержательными сообщениями, Pull Request в собственную main |
| Срок | До начала занятия 9 |
| Проверяем | Зелёный pytest по всем файлам; три теста к bugs_08.py, которые падают до исправления; пять тестов к sorted_squares; заметка без пустых пунктов |
| ИИ | Код и тесты пишете сами: на занятии 9 решение объясняется без подсказок. Оформление .md и редактуру формулировок можно поручить модели. Я сам так делаю всегда, поэтому и вам запрещать не буду. |
§9Что дальше
Перед занятием 9 задачи модуля можно прорешать в формате собеседования: в главе 8.13 восемь задач, каждая по этапам секции с секундомером.
Занятие 9 — скользящее окно фиксированного размера. Окно — это два указателя в одну сторону, между которыми всегда одно и то же расстояние k. На каждом шаге правый указатель добавляет элемент в окно, левый убирает, и сумма или счётчик окна пересчитываются за O(1). Правило «элементов n, окон длины k — n − k + 1» из занятия 7 там понадобится сразу.