Программирование: строки, числа и стандартные алгоритмы
Схемы обработки строк, делителей, сортировки и больших наборов данных.
На экзамене
Задания 24, 25 и 26. Нужно выбрать алгоритм для строки, целых чисел или большого набора записей и соблюсти ограничения входа.
Формулы и факты
| Формулировка | Схема | Что хранить |
|---|---|---|
| Максимальная допустимая серия | Один проход со сбросом | Текущую и максимальную длину |
Не более k нарушений | Скользящее окно | Левую границу и число нарушений |
| Вхождения образца | Окно или список позиций | Позиции и границы фрагмента |
| Частоты значений | Словарь | Количество для каждого значения |
| Упорядочивание записей | Сортировка | Главный и дополнительные ключи |
- Окон длины
mв последовательности длиныn:n - m + 1. - Последний начальный индекс подстроки длины
m:n - mпри нумерации с 0. - Делители числа
nдостаточно искать парами до \lfloor\sqrt{n}\rfloor. - Для полного квадрата парные делители совпадают и добавляются один раз.
| Алгоритм | Типичная сложность |
|---|---|
| Один проход | O(n) |
| Делители одного числа | O(sqrt(n)) |
| Сортировка | O(n log n) |
Алгоритм
- Определи кандидата: символ, подстрока, число, пара или набор записей.
- Запиши точное условие допустимости и требуемый результат.
- Выбери схему по таблице; для чисел сначала применяй дешевые проверки.
- Выведи границы цикла из размера кандидата, не подбирай их на глаз.
- Для сортировки задай правило равенства ключей; жадный выбор используй только с обоснованием.
- Проверь начало, конец, пустой результат, полный квадрат и равные ключи.
- Сверь оптимизированное решение с полным перебором на маленьком наборе.
Ловушки
- Путают: завершенную серию и серию в конце строки. Сверь: обновляй максимум в проходе или после цикла.
- Путают: пересекающиеся и непересекающиеся вхождения. Сверь: не пропускай пересечения без требования условия.
- Путают: два парных делителя полного квадрата. Сверь: добавь корень один раз.
- Путают: главный ключ и полный порядок сортировки. Сверь: задай дополнительные ключи.
- Путают: локально удобный и доказанно жадный выбор. Сверь: найди контрпример полным перебором.