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

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

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

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

К сожалению, всё задачи в мире не прорешаешь, и не факт что на собесе попадётся одна из сотен порешённых задач, а стоит завалить одну и всё, отказ. Но есть лайфхак по решению алгоритмических задач. Им является не просто прорешивание всего подряд, а знание определённых подходов к решению семейства задач. А уж эти подходы можно пересчитать на пальцах и они закроют процентов 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 )

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

Тренируемся

Ссылки

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

Источник

Грокаем алгоритмы: Гайд по алгоритмам для тех, кому сложно решать задачи

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

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

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

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

Коротко расскажу о себе, чтобы вы убедились в моей экспертности. Я программирую уже 20 лет, за это время я много раз менял место работы. Всего я прошел около 30 воронок найма — больше 120 собеседований. Плюс к этому у меня есть опыт с той стороны баррикад: я провел около 300 технических собеседований и больше 200 собеседований по системному дизайну.

Где мы грокаем алгоритмы

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

Самая большая проблема LeetCode в том, что сайту не хватает продуманной системы обучения. У него много разных задач, в которых легко потеряться. Сколько нужно таких задач, чтобы подготовиться к собеседованию? Я бы предпочел двигаться по продуманной программе, в конце которой я смогу ощутить уверенность в собственных знаниях. Но системы нет, а я ленивый, и вообще — не хочу решать 500+ задач.

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

Какую систему обучения придумал я

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

Я обнаружил 25 паттернов, которые лежат в основе решения большинства задач. Думаю, эти паттерны помогут кому угодно показывать на собеседованиях красивые и элегантные решения. Вся фишка этих паттернов в том, что понимая один из них, вы научитесь решать сразу несколько задач, десятки задач.

Самые распространенные паттерны для решения задач

1. Метод скользящего окна
2. Метод двух указателей
3. Нахождение цикла
4. Интервальное слияние
5. Цикличная сортировка
6. In-place Reversal для LinkedList
7. Поиск в ширину
8. Поиск в глубину
9. Двоичная куча
10. Подмножества
11. Усовершенствованный бинарный поиск
12. Побитовое исключающее ИЛИ
13. Top K Elements
14. K-образное слияние
15. Задача о рюкзаке 0-1
16. Задача о неограниченном рюкзаке
17. Числа Фибоначчи
18. Наибольшая последовательность-палиндром
19. Наибольшая общая подстрока
20. Топологическая сортировка
21. Чтение префиксного дерева
22. Задача: количество островов в матрице
23. Метод проб и ошибок
24. Система непересекающихся множеств
25. Задача: найти уникальные маршруты

Читайте также: Это снова я, резиновая уточка: что такое метод Фейнмана и почему с его помощью так просто изучать программирование

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

Контекст: Мы используем этот метод, когда у нас есть входные данные с заданным размером окна.

Задачи для этого паттерна:

Метод двух указателей

Контекст: Мы используем два указателя, чтобы перебрать все входные данные. Обычно два указателя движутся в противоположных направлениях с фиксированным интервалом.

Задачи для этого паттерна:

Нахождение цикла

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

Задачи для этого паттерна:

Интервальное слияние

Контекст: Этот метод применяют, если есть пересекающиеся интервалы. Например, на этом изображении мы видим, что интервалы a и b могут пересекаться шестью разными способами:

Задачи для этого паттерна:

Цикличная сортировка

Контекст: Если входные данные лежат в заданном интервале, используйте цикличную сортировку.

Задачи для этого паттерна:

In-place Reversal для LinkedList

Техника: Эта техника описывает эффективный способ перевернуть связи между узлами в LinkedList (класс Java). Часто мы ограничены in-place, то есть мы должны использовать исходные узлы.

Задачи для этого паттерна:

Поиск в ширину

Контекст: Это метод для решения задач с деревьями.

Задачи для этого паттерна:

Поиск в глубину

Контекст: Тот же, что для предыдущего метода.

Задачи для этого паттерна:

Двоичная куча

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

Задачи для этого паттерна:

Подмножества

Контекст: Если задача требует перестановки или комбинаций элементов, используйте подмножества.

Задачи для этого паттерна:

Усовершенствованный бинарный поиск

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

Задачи для этого паттерна:

Наибольшее K элементов

Контекст: Эта техника используется, чтобы найти наибольший/наименьший или наиболее часто встречающийся набор k-элементов в коллекции.

Задачи для этого паттерна:

Читайте также: Как решить задачу, если непонятно, с чего вообще начать: советы от Хекслета

K-образное слияние

Контекст: Используйте эту технику, если у вас есть список отсортированных массивов.

Задачи для этого паттерна:

Рюкзак 0-1

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

Задачи для этого паттерна:

Неограниченный рюкзак

Контекст: То же самое, что в предыдущем паттерне, но только каждый элемент может быть выбран повторно сколько угодно раз.

Задачи для этого паттерна:

Числа Фибоначчи

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

Задачи для этого паттерна:

Наибольшая последовательность — палиндром

Контекст: Имеется в виду задача, которая может быть использована как для последовательности, так и для строк. По сути это задача на оптимизацию.

Задачи для этого паттерна:

Наибольшая общая подстрока

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

Задачи для этого паттерна:

Чтение префиксного дерева

Контекст: Это специфичная для структуры данных техника, с помощью которой читают или создают префиксное дерево.

Задачи для этого паттерна:

Острова в матрице

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

Задачи для этого паттерна:

Путь проб и ошибок

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

Задачи для этого паттерна:

Система непересекающихся множеств

Контекст: Если данные раскиданы по непересекающимся множествам, то они решаются одним и тем же способом.

Задачи для этого паттерна:

Поиск уникального маршрута

Контекст: Этот паттерн подойдет для прохождения по любому многомерному массиву.

Задачи для этого паттерна:

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

Источник