Получите 2 очка
Паттерн/техника двух указателей
Шаблон с двумя указателями оптимизирует алгоритмы, обрабатывающие строки, отсортированные массивы или связанные списки, за счет использования двух указателей для отслеживания индексов, упрощения логики и экономии времени и места. В этом шаблоне два указателя проходят через структуру данных в тандеме, пока один или оба указателя не достигнут определенного условия.
В чем смысл?
Этот шаблон полезен, когда нам нужно проанализировать каждый элемент коллекции по сравнению с другими ее элементами.
Чтобы решить подобные проблемы, мы могли бы начать с первого индекса и выполнить цикл один или несколько раз. Хотя грубая сила или наивное решение с одним указателем будут работать, они будут производить что-то вроде временной сложности O (n²). Во многих случаях два указателя могут помочь вам найти решение с лучшим временем выполнения или сложностью пространства за счет обработки двух элементов в цикле вместо одного.
Направьте меня в правильном направлении
Многие варианты шаблона двух указателей можно классифицировать как противоположно направленные или равнонаправленные.
- В противоположном направлении — два указателя движутся в противоположном направлении.
- Равнонаправленный — два указателя движутся в одном направлении.
Противоположное направление
Один указатель начинается с начала, а другой указатель начинается с конца, двигаясь навстречу друг другу, пока они оба не удовлетворят условию.
Этот шаблон актуален, когда:
- есть целевое значение для сопоставления или дубликаты, которые необходимо удалить
- проблема связана с отсортированными массивами (или связанными списками), набором парных элементов, триплетом или даже подмассивом
- вам нужно найти набор элементов, которые удовлетворяют определенным ограничениям
Примеры проблем
- Отсортированная сумма двух
- Обратная струна
- Действительный палиндром
- Удалить элемент
- Переместить нули
- Две суммы 2
- Контейнер с наибольшим количеством воды
Пример
Равнонаправленные (быстрые и медленные указатели)
Существует множество вариантов, в которых используются быстрые и медленные указатели, в том числе: Черепаха и заяц Флойда. Как правило, один указатель (быстрый указатель) перемещается на каждой итерации, а другой указатель (медленный указатель) перемещается с некоторыми ограничениями. Для более сложных сценариев быстрый бегун также перемещается с некоторыми ограничениями.
Этот шаблон актуален, когда:
- проблема связана с чем-то, связанным с циклическими структурами данных
- вам нужно знать положение определенного элемента или общую длину связанного списка
- проблема связана с циклом в связанном списке или отсортированном массиве
Примеры проблем
- Удалить дубликаты из отсортированного массива
- Найди повторяющееся число
- Счастливый номер
- Середина связанного списка
- Цикл связанного списка
- Связанный список палиндромов
- Самая длинная подстрока без повторяющихся символов
- Удалить N-й узел из конца списка
- Циклический массив
Пример
📚 Ресурсы 👀
14 шаблонов для ответа на любой вопрос на собеседовании по программированию
