Привет, мир!

Недавно я столкнулся с техникой скользящего окна, пытаясь решить несколько алгоритмических проблем, связанных с массивами или строками. Являясь подмножеством динамического программирования, это действительно мощный метод, который обычно используется вместе со структурами данных, такими как Hash Map, Hash Set или Array. Я не мастер в этом, но после попытки решить несколько проблем с этим методом, я подумал, что могу поделиться тем, что я узнал до сих пор.

Почему такое название «Скользящее окно»?

Сам этот метод включает в себя 2 указателя (обычно индексы строки / массива), представляющие 2 края на стороне окна - начальный индекс находится на левом краю, а конечный индекс находится на правом краю. Элементы массива, захваченные в диапазоне начального и конечного индексов, будут использоваться для вычисления результата.

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

Зачем использовать скользящее окно?

Решение, использующее этот метод, обычно выполняется с временной сложностью O (n).

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

Когда мне следует использовать скользящее окно?

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

Я столкнулся с двумя типами окон: один имеет фиксированный размер, а другой - динамический. Окно фиксированного размера можно использовать для решения проблемы, когда вы хотите определить, содержит ли данная строка конкретную подстроку, поскольку мы можем легко найти фиксированную длину подстроки. С другой стороны, динамический можно использовать для поиска самой длинной или самой короткой подстроки данной строки.

Примеры

Во всех этих примерах вы можете увидеть общую схему настройки алгоритма:

  • Создайте таблицу поиска, чтобы запомнить количество вхождений символа или его последний просмотренный индекс. Это может быть HashMap или массив. Размер массива должен быть 256 (если в формулировке задачи указано Unicode), 128 (если ASCII) или даже 26 (количество английских букв).
  • Переменная счетчика для отслеживания требований проблемы. Это может быть максимальная / минимальная длина подстроки при любых условиях.
  • Указатели начального и конечного окон, инициализированные 0
  • Цикл for или while, расширяющий окно за счет увеличения индекса конца окна. По мере того, как окно увеличивается вправо, оно обновляет приведенную выше таблицу поиска.
  • Внутри основного цикла существует оператор if или иногда цикл while, чтобы определить, когда следует увеличивать начальный индекс. Обычно это происходит, когда указанная выше переменная счетчика удовлетворяет заданным ограничениям.

1. Найдите все анаграммы в строке

Проверьте вопрос Leetcode

Код Github с комментариями

Это пример применения скользящего окна фиксированного размера. Как видите, проблема запрашивает только начальный индекс, поскольку они уже знают размер анаграммы (p.length()). Временная сложность решения составляет O (n), где n - длина строки s. Сложность пространства равна O (1), поскольку используемый массив имеет фиксированную длину независимо от размера входных данных.

Идея в том, что мы храним символы из p и их частоты; затем, расширяя окно, мы уменьшаем частоту символа в конце указателя. Если этого символа нет в p, он не будет заполнен раньше, поэтому при уменьшении он может достигать -1 частоты. Если символ все еще появляется >= 1 раз в таблице поиска, уменьшите remainingCharToBeAnagram.

Когда размер окна совпадает с p.length(), мы добавляем частоту символа в начальный индекс назад, когда мы перемещаем начальный указатель вперед, исключая его из рамки окна. Если количество символов равно >= 0 (а не -1), то есть изначально он был в строке p, поэтому мы добавляем счетчик remainingCharToBeAnagram обратно.

2. Замена самого длинного повторяющегося символа

Оформить заказ на вопрос Leetcode

Код Github с комментариями

Это пример скользящего окна динамического размера. В вопросе запрашивается максимальный размер подстроки, а не только начальный индекс, как в предыдущем вопросе.

Идея этого вопроса заключается в том, что вы находите самую длинную подстроку с символом доминирующим (например, «AABABBA» - кажется, что A здесь является доминирующим) и k символ (и), который не является доминирующим. Если k = 1, то вы можете заменить только 1 символ, скажем, B в индексе 2 на A даст вам AAAA, что является самой длинной подстрокой с повторяющимся символом. Следовательно, вы хотите найти подстроку с AAxA, где x - любой символ, кроме A, и в этом случае должно быть только 1 x.

Это очень похоже на другие проблемы, единственное отличие состоит в условии уменьшения окна и в том, как обновить счетчик отслеживания. В этом примере мы сжимаемся, когда внутри нашего окна имеется более k символов, отличных от основного.

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

3. Самая длинная подстрока без повторяющихся символов

Оформить заказ на вопрос Leetcode

Код Github с комментариями

Таблица поиска в этом решении используется для хранения индекса последнего посещения персонажа. Например, «ABBB», индекс последнего посещения A будет равен 0, а индекс B - 3.

Идея здесь в том, чтобы «супер» сжать окно до символа, который повторяется, когда мы расширяем конечный указатель. Он отличается от предыдущего вопроса, где он сжимает начальный указатель, постепенно увеличивая его, тогда как в этом он переходит прямо к конечному указателю, где находится последний встреченный повторяющийся символ (поскольку требование - without repeating characters). Например, снова «ABBB», изначально начало окна находится в точке A, поскольку мы скользим по конечному указателю, находящемуся в индексе 2 (второй B) и обнаруживаем дубликат B в окне, начальный указатель обновляется до индекса 2. Нет смысла увеличивать его по одному.

Мы достигаем этого, устанавливая начальный указатель в зависимости от того, что больше, его текущего значения или последнего увиденного индекса текущего символа (на который указывает конечный указатель). Если символ, которого достиг конечный указатель, раньше не был виден в окне, его значение по умолчанию будет 0, тогда начальный указатель останется на 0.

Максимальная длина подстроки обновляется путем сравнения ее текущего значения с длиной нового окна, вычисленной с помощью индекса конечного указателя, вычитающего индекс начального указателя.

Ресурсы

Я надеюсь, что эти 3 примера дали вам, друзьям по решению проблем, лучшее понимание техники скользящего окна.

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

Приятного чтения!