Алгоритмы с нуля
Массивы и строки: свободное припоминание
Припоминание сильнее перечитывания. На каждый промпт проговори или запиши полный ответ по памяти, прежде чем открыть модельный — именно усилие припоминания закрепляет приём и его предусловие.
Восстанови стержень юнита — почему непрерывность задаёт всю стоимость, почему two pointers и sliding window — O(n), что меняет prefix sum, чего стоит in-place и в чём ловушка конкатенации строк — не подглядывая в уроки.
- 01Почему непрерывность массива даёт и силу (O(1) индексация), и слабость (O(n) вставка в середину)?
- 02Two pointers бывает в двух формах. Назови их, для чего каждая, и предусловие, на котором держится two-sum с концов.
- 03Почему sliding window — O(n), а не O(n²), даже когда в вариативной версии есть вложенный while?
- 04Что покупает prefix-массив, чего он стоит и когда это неподходящий инструмент?
- 05Что точно означает in-place, чего он стоит и назови две ключевые техники in-place из юнита.
- 06Строка алгоритмически — это массив, но построение её через повторный += в цикле — O(n²). Объясни почему и дай фикс.
Если ты смог восстановить каждый ответ по памяти, ты держишь стержень юнита: непрерывность задаёт всю таблицу стоимости (O(1) индекс, O(n) сдвиг, O(1) амортизированный append); two pointers и sliding window достигают O(n) движением только вперёд за один проход; two-sum с концов требует отсортированного входа; prefix sum меняет O(n) памяти на O(1) запросы по диапазону на статичных данных; in-place покупает O(1) памяти ценой разрушения входа; а строки — это массивы, что наказывают конкатенацию в цикле за O(n²) — складывай в массив и join.