Скользящее окно алгоритм программирование

Метод скользящего окна

Пожалуй, самая нелюбимая часть собеседования у любого программиста — алгоритмическая секция, где приходится решать какие-то загогулистые задачи, которые зачастую в настоящей работе не пригождаются. Но есть две причины, почему это всё-таки важно:

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

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

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

Задача

Для массива, состоящего из n целых чисел, найдите непрерывный подмассив заданной длины k, который имеет максимальное среднее значение. Нужно вывести максимальное среднее значение.

Аргументы: [1, 12, -5, -6, 50, 3], k = 4 Ответ: 12.75 Объяснение: Максимальное среднее — это (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75 

Брутфорсим

Не будет лишним на собеседовании начать с наивной реализации, брутфорса. Решить задачу неоптимально лучше, чем не решить совсем. К тому же это позволит больше пообщаться с собеседующим, показать поток мышления. Набросаем:

function findMaxAverage(nums: number[], k: number): number  let maxAverage = Number.MIN_VALUE for (let i = 0; i  nums.length - k + 1; i++)  let sum = 0 // сумма следующих k элементов for (let j = i; j  i + k; j++)  sum += nums[j] > const average = sum / k maxAverage = Math.max(maxAverage, average) > return maxAverage > console.assert(findMaxAverage([1, 12, -5, -6, 50, 3], 4) === 12.75) 

Сложность этого решения O(n*k), где n — длина переданного массива. Но это наивное решение редко удовлетворит собеседующего, литкод тоже на это намекает, он пожалуется, что превышен лимит по времени. Так что давайте подумаем, как найти решение получше.

Если внимательно взглянуть на текущее решение, то легко заметить, что при каждом сдвиге мы заново высчитываем сумму элементов. Можно ли как-нибудь переиспользовать сумму для пересекающихся подмассивов?

Скользим

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

function findMaxAverage(nums: number[], k: number): number  // считаем сумму первого окна let sum = 0 for (let i = 0; i  k; i++)  sum += nums[i] > let res = sum // храним максимальную сумму for (let i = k; i  nums.length; i++)  sum += nums[i] - nums[i - k] // добавляем вошедший/убираем ушедший res = Math.max(res, sum) > return res / k > console.assert(findMaxAverage([1, 12, -5, -6, 50, 3], 4) === 12.75) 

Временная сложность — O(n), сложность по памяти — O(1). Идеально.

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

• в задаче передаётся упорядоченная и итерируемая структура данных, вроде массива или строки
• просят найти подпоследовательность в массиве/строке, самое длинное/короткое, среднее/большое/маленькое и т. д.
• первым в голову приходит наивное решение со сложностью O ( n 2 ) O(n^2) O ( n 2 ) или даже O ( 2 n ) O(2^n) O ( 2 n )

Метод скользящего окна позволяет улучшить вычислительную сложность до линейной, а по памяти — до константной. И это классно.

Тренируемся

Ссылки

🚀 Если узнал из статьи что-то полезное, ставь лайк и подписывайся на наш канал в Телеграм или группу ВК. Обсудить статью можно в нашем уютном чатике 😏

Источник

Алгоритм скользящего окна — практические задачи

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

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

1. Найдите самую длинную подстроку строки, содержащей k отдельные персонажи

Дана строка и положительное число k , найти самую длинную подстроку строки, содержащей k отчетливые персонажи. Если k больше, чем общее количество различных символов в строке, вернуть всю строку.

2. Найти все подстроки строки, являющиеся перестановкой другой строки

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

3. Найдите самую длинную подстроку строки, содержащей различные символы

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

4. Найдите последовательность непрерывных элементов максимальной длины (используя скользящее окно)

Для заданного двоичного массива найдите индекс 0, который нужно заменить на 1, чтобы получить последовательность непрерывных единиц максимальной длины.

5. Найдите максимальную последовательность непрерывных единиц, образованную заменой не более k нули на единицы

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

6. Найдите подмассив минимальной суммы размера k

Учитывая целочисленный массив, найдите минимальный подмассив суммы размера k , куда k является положительным целым числом.

7. Найти подмассив с заданной суммой в целочисленном массиве

Дан целочисленный массив, найти подмассив, содержащий заданную сумму.

8. Найдите наименьшую длину подмассива, сумма элементов которого больше k

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

9. Найдите количество различных элементов в каждом подмассиве размера k

Дан массив и целое число k , найти количество различных элементов в каждом подмассиве размера k .

10. Вывести все подмассивы массива, имеющие различные элементы

Для массива целых чисел выведите все подмассивы максимального размера, содержащие все отдельные элементы.

11. Подсчет различных абсолютных значений в отсортированном массиве

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

12. Найти дубликаты в пределах диапазона k в массиве

Дан массив и положительное число k , проверьте, содержит ли массив какие-либо повторяющиеся элементы в диапазоне k . Если k превышает размер массива, решение должно проверять наличие дубликатов во всем массиве.

Средний рейтинг 4.74 /5. Подсчет голосов: 129

Голосов пока нет! Будьте первым, кто оценит этот пост.

Сожалеем, что этот пост не оказался для вас полезным!

Расскажите, как мы можем улучшить этот пост?

Источник