Интервью по кодированию — это сложно. Никогда не знаешь, какой вопрос тебе зададут, а их так много! Что еще хуже, интервьюер ожидает, что вы в конце концов (если не сразу) придете к оптимальному решению.

Хорошая новость заключается в том, что есть несколько «шаблонов проектирования кода», которые могут вам помочь. Шаблон кодирования — это план, который можно настроить для оптимального решения многих связанных проблем.
Начнем учиться.

Два указателя:

Техника «двух указателей» — это популярный алгоритмический подход, используемый для решения множества задач, особенно в массивах и связанных списках. Это эффективный и интуитивно понятный способ решения задач, связанных с поиском, поиском пар или работой с элементами данных в отсортированной или частично отсортированной последовательности.

Основная идея метода двух указателей заключается в использовании двух указателей (или индексов), которые перемещаются по структуре данных одновременно, но часто с разной скоростью или в разных направлениях, для эффективного решения проблемы. Двойные указатели обычно используются для отслеживания позиций в массиве или связанном списке.

Чтобы реализовать метод двух указателей, вам обычно необходимо выполнить следующие шаги:

  1. Инициализировать два указателя (индекса), чтобы они начинались с определенных позиций в структуре данных.
  2. Используйте цикл while для итерации по структуре данных, пока указатели удовлетворяют определенным условиям (например, левый указатель находится перед правым указателем).
  3. В цикле обновите указатели в соответствии с требованиями задачи (например, переместите их ближе друг к другу или в разных направлениях).
  4. Продолжайте цикл, пока указатели не удовлетворят или не выполнят необходимые условия для решения проблемы.

Вот общие сценарии, в которых часто используется метод двух указателей:

  1. Поиск в отсортированном массиве или списке. Используя два указателя, один из которых начинается с начала (слева), а другой с конца (справа), вы можете эффективно искать определенный целевое значение или выполнить другие операции, например найти пару с определенной суммой.
  2. Удаление дубликатов из отсортированного массива или списка. Если у вас есть отсортированная структура данных, вы можете использовать два указателя для устранения дубликатов, сравнивая соседние элементы и сдвигая уникальные элементы вперед.
  3. Поиск подмассивов или подсписков с определенными свойствами. Метод двух указателей можно использовать для поиска подмассивов или подсписков с определенными характеристиками или условиями, такими как самый длинный подмассив с суммой, меньшей или равной заданное значение.
  4. Проверка палиндромов или шаблонов. Два указателя часто используются для проверки того, является ли строка или массив палиндромом или содержит определенный шаблон.

Ключевые преимущества метода двух указателей включают его временную сложность, которая часто является линейной (O(N)) или близкой к линейной, что делает его более эффективным по сравнению с другими подходами, такими как вложенные циклы.

👉 Пример кода, чтобы увидеть, как работают два указателя.

Быстрые и медленные указатели:

Метод «быстрых и медленных указателей», также известный как «алгоритм черепахи и зайца Флойда» или алгоритм «обнаружения циклов», является еще одним важным алгоритмическим подходом, обычно используемым в связанных списках и последовательностях. Он в основном используется для обнаружения циклов или циклов в связанном списке и может быть расширен для решения других проблем.

Основная идея метода быстрых и медленных указателей заключается в использовании двух указателей, которые перемещаются по связанному списку с разной скоростью. Один указатель перемещается быстрее другого, что позволяет нам обнаруживать циклы или эффективно выполнять другие операции.

Вот пошаговое объяснение техники:

  1. Инициализируйте два указателя, часто называемые "быстрым" и "медленным", на начало (начальную точку) связанного списка.
  2. Перемещайтесь по связанному списку с помощью указателей следующим образом:
    i. Медленный указатель перемещается на один шаг за раз.
    ii. Быстрый указатель перемещается на два шага за раз.
  3. Продолжайте перемещать указатели в соответствии с их скоростью, пока не будет выполнено одно из следующих условий:
    i. Быстрый указатель достигает конца связанного списка (т. е. становится нулевым), указывая на отсутствие цикла.
    ii. Быстрый указатель и медленный указатель встречаются в одном узле (т. е. указывают на одну и ту же ячейку памяти), что указывает на наличие цикла.
  4. Если обнаружен цикл, вы можете найти начальный узел цикла, сбросив быстрый или медленный указатель на начало списка, а затем перемещая их на один шаг, пока они снова не встретятся. Узел, в котором они встречаются, является начальным узлом цикла

Причина, по которой этот метод работает для обнаружения циклов, заключается в том, что если в связанном списке есть цикл, быстрый указатель в конечном итоге «догонит» медленный указатель по мере его перемещения по циклу. Если цикла нет, быстрый указатель достигнет конца списка, не встречаясь с медленным указателем.

Быстрые и медленные указатели можно использовать и для других сценариев, а не только для обнаружения циклов. Некоторые распространенные приложения включают в себя:

  • Поиск середины связанного списка. Используя тот же подход, вы можете найти средний узел связанного списка, перемещая быстрый указатель на два шага, а медленный указатель на один шаг, пока не появится быстрый указатель. доходит до конца.
  • Обнаружение палиндрома в связанном списке. Вы можете поменять местами вторую половину связанного списка, используя подход с быстрыми и медленными указателями, а затем сравнить его с первой половиной, чтобы найти палиндром.
  • Обнаружение точки пересечения двух связанных списков. Используя технику быстрых и медленных указателей, вы можете определить, пересекаются ли два связанных списка, и найти точку пересечения.

Техника быстрых и медленных указателей, как правило, очень эффективна и имеет временную сложность O(N), где N — количество узлов в связанном списке. Это универсальный и полезный метод для эффективного решения различных проблем связанных списков.

👉 Пример кода, чтобы увидеть, как работает быстрый и медленный указатель.

Раздвижное окно:

Техника скользящего окна — еще один популярный алгоритмический подход, используемый для эффективного решения задач, связанных с массивами или строками. Это особенно полезно при работе с подмассивами или проблемами, связанными с подстроками. Этот метод включает в себя поддержание «окна» элементов в массиве или строке и эффективное скольжение этого окна, чтобы найти желаемый результат.

Вот общий обзор техники скользящего окна:

  1. Инициализация. Инициализация двух указателей, обычно left и right, для определения окна. Эти указатели представляют начальную и конечную позиции окна.
  2. Настроить окно. Изначально окно имеет определенный размер или содержит определенное количество элементов (например, окно фиксированного размера или окно, содержащее первые k элемента). Идея состоит в том, чтобы обработать это начальное окно, чтобы получить первоначальный результат.
  3. Переместить указатель вправо. Увеличьте значение указателя right, чтобы развернуть окно вправо и добавить новые элементы в текущее окно. Этот шаг также известен как "расширение окна".
  4. Проверить условие. На каждом шаге проверяйте, удовлетворяет ли окно условию или требованию задачи. Это может быть проверка определенного свойства, поиск подмассива с заданной суммой или что-то еще, в зависимости от задачи.
  5. Переместить указатель влево. Если условие нарушено, увеличьте значение указателя left, чтобы свернуть окно слева, удаляя элементы из текущего окна. Этот шаг также известен как "сжатие окна".
  6. Повторите шаги 4 и 5. Продолжайте перемещать указатель right и проверять условие, пока оно не перестанет выполняться. Затем снова повторите шаги 4 и 5, продолжая этот процесс до тех пор, пока указатель right не достигнет конца массива или строки.
  7. Завершение. Алгоритм завершается, когда указатель right достигает конца массива или строки, и окно больше не может быть развернуто.

Метод скользящего окна может быть эффективным решением многих проблем с массивами и строками, часто достигая временной сложности O (n) или лучше, в зависимости от конкретной реализации.

👉 Пример кода, чтобы увидеть, как работает быстрый и медленный указатель.

Заключение

Теперь пришло время отправиться в ваше приключение по кодированию! Наслаждайтесь решением сложных задач и всегда помните, что у вас есть возможность преуспеть и создать замечательные решения. Итак, вперед, учитесь, экспериментируйте и станьте мастером решения проблем в мире программирования.

Удачного кодирования!