Когда кто-то слышит о скользящем окне, первое, что приходит на ум, — это скользящее окно, подобное тому, что на изображении выше, и если это то, что вы имеете в виду, то вы на правильном пути.
Техника скользящего окна решает некоторые вопросы динамического программирования, знание которых поможет вам решить большинство вопросов.
Итак, что такое техника скользящего окна:
Я имею в виду, если бы вы пытались объяснить этот термин ребенку, как бы вы это сделали? ! в основном давая всем слушателям обзор того, что будет происходить.
Изображение выше представляет технику скользящего окна. Как и обычное скользящее окно, мы должны сдвинуть его, чтобы отрегулировать его до нужного размера.
КАК ВЫ ИСПОЛЬЗУЕТЕ ТЕХНИКУ РАЗДВИЖНОГО ОКНА
Прежде всего, вы поймете, что окно содержит только подмассив. Подмассив является непрерывным по определению.
Вот пример, который поможет вам лучше понять:
Массив: [1,2,3,5,7,9,3]
Output : [2,3,5,7] //this is a sub-array its in a sequence.
[2,3] [9,3]// Sub-arrays that form subsets.
Надеюсь понятно 😁
Этот метод используется для поиска подмассива, удовлетворяющего заданным условиям, будь то максимальная сумма, минимальная сумма и т. д.
Признание этих проблем
- Проблема решается последовательно.
- Если вы пытаетесь получить максимальные, минимальные, самые длинные, самые короткие и содержащиеся значения, которые находятся во вспомогательном массиве.
ВОПРОСЫ РАЗНООБРАЗИЕ
- Поиск подмассива фиксированной длины.
- Поиск динамического варианта
- Поиск динамического варианта с помощью вспомогательной структуры данных (например, Карты, массивы и т. д. :)
Есть много других, которые я буду обновлять со временем.
Примеры вопросов: -
В технике большинство вещей лучше понимаются, когда их видят, я думаю, что увидеть действительно значит поверить!
Найдите подмассивы, которые составляют желаемое число.
Пример ввода: массив: [1,2,3,4,5,6,7,8,9] желаемое число: 9
Этот вопрос представляет собой решенный вопрос динамического скользящего окна, и он требует, чтобы вы добавили, скажем, значение индекса 0, равное 1, плюс значение индекса 1, равное 2, пока вы не дойдете до 9, но, например:
1+2+3+4= 10 // Это больше 9, так что же нам делать??
1+2+3+4= 10 // Its more than 9 so what do we do?? // We reduce the size of the window from the left by one,confirm if it now 9 which in our case it is. 1+2+3+4=10 - 1 =9
Что, если мы уменьшим самое левое число, но оно все равно не будет задано?
Ответ заключается в том, что мы будем продолжать изменять размер окна, пока не получим то, что хотим, сохраним то, что хотим, и вернем подмножества или количество подмножеств.
ВЕЖЛИВОЕ УВЕДОМЛЕНИЕ: ВНИМАТЕЛЬНО ОТНОСИТЕСЬ К ВАШЕМУ ДЕЛУ, ЧТО ПРОБЛЕМА ТРЕБУЕТ.
КОД ШАГ ЗА ШАГОМ:
Отказ от ответственности: для кодеров, не использующих JavaScript, я буду использовать JavaScript, но он не так сильно отличается от других языков.
- Определите переменную, которая будет содержать подмножества, когда подмассив удовлетворяет условию.
let solution = [];
2. Определите текущую сумму, чтобы иметь возможность отслеживать сумму по текущему индексу.
let currentsum = 0;
3. Определите начало и конец окна. Сначала он будет в той же точке, затем вы начнете двигать его вправо. Если текущая сумма меньше желаемой суммы, добавьте следующее значение индекса, затем увеличьте индекс конца: -
текущая сумма = текущая сумма + значение индекса:
let start = 0;
for(let end = 0; end < arr.length;){
if(currentsum < sum){
currentsum += arr[end];
end++;
}
4. В случае, если текущая сумма выходит за пределы условия, нам придется уменьшить окно, то есть вычитая первое число, которое находится в окне.
Пример: [2,3,4,5] Желаемое число равно 7:
конец равен 2, сначала это индекс 0. Текущая сумма меньше желаемой, которая равна 0, поэтому добавьте текущую сумму к индексу [0], равному 2, теперь текущая сумма равна 2, но она все еще меньше 7, поэтому добавьте 3, еще меньше, добавьте 4 и его 9, что больше.
Таким образом, мы должны уменьшить окно, и это на
текущаясумма = текущаясумма- обр [начало]
9–обр[0]= 9–2 = 7;
Затем increment start вызывает уменьшение размера окна.
else if (currentsum > sum){
currentsum -= arr[start]
start ++;
}
5. Наконец мы получаем подмассив, который добавляет к желаемому значению
e.g 3+4 = 7
поэтому нам нужно протолкнуть подмассив и продолжить итерацию по массиву, пока вы не дойдете до конца с помощью arr.length — 1, и мы указали это как условие в цикле for end‹array.length, потому что он должен добраться до на единицу меньше длины.
else{
solution.push(arr.slice(start,end));
currentsum -= arr[start];
currentsum += arr[end];
start ++;
end ++;
}
}
Таким образом, мы помещаем подмассив, вырезая его из массива с помощью метода slice(), а затем меняем текущую сумму и размер окна, чтобы продолжить итерацию.
6. Вернуть подмножества, помещенные в массив решений.
Полный код:
var DesiredSumSubArray = function(arr,sum){
let solution = [];
let currentsum = 0;
let start = 0;
for(let end = 0; end < arr.length;){
if(currentsum < sum){
currentsum += arr[end];
end++;
}
else if (currentsum > sum){
currentsum -= arr[start]
start ++;
}
else{
solution.push(arr.slice(start,end));
currentsum -= arr[start];
currentsum += arr[end];
start ++;
end ++;
}
}
return solution;
}
Временная сложность: O(n). Прохождение через него один раз
Пространственная сложность: O(n). Причина пустого массива решений
Подмассив максимальной суммы размера k.
ВОПРОС: Дан массив целых чисел, найти максимальную сумму подмассива требуемого размера.
Пример ввода: массив: [-1, 2, 3, 1, -3, 2] размер подмассива: 2
В этом вопросе такая же реализация скользящего окна, но разница в том, что окно должно иметь только 2 элемента.
Проведение вас через концептуальную логику этого вопроса:
Я знаю, что вы можете использовать грубую силу для этого вопроса, но грубая сила использует временную сложность O (n) и пространственную сложность O (n)
Если вы используете метод скользящего окна
временная сложность: O(n)
Пространственная сложность: O(1)
Отличие вносит наиболее оптимальное решение. Когда мы используем грубую силу, мы склонны повторять все возможные сохранения сумм в хэш-карте, максимальное значение, очевидно, является нашим результатом, но оно использует линейное пространство, но в скользящем окне мы подтверждаем, больше ли cursum, чем max, и если это так, то это max .
КОД ШАГ ЗА ШАГОМ:
Отказ от ответственности: для кодеров, не использующих JavaScript, я буду использовать JavaScript, но он не так сильно отличается от других языков.
1. Определение текущей суммы как cursum, инициализация ее 0.
let cursum = 0;
2. Определите максимальную сумму, чтобы отслеживать максимальную сумму.
let max = -infinity; //in case we have negative numbers.
3. Перебрать массив
for(let i = 0; i<nums.length; i++){
}
4. Обновление текущего примера суммы в начале цикла arr[0] = -1
поэтому cursum = cursum, который равен 0 + arr[0], что равно -1 = -1
cursum += nums[i];
5.Если размер окна достигнут, мы теперь проверяем максимальное
if(i >= size - 1){
maxsum = Math.max(cursum,maxsum);
cursum -= nums[i - (size - 1)];
}
Если i больше или равно size — 1; зачем так говорить;
Если я доберусь до индекса 1, размер будет заполнен, поэтому, если я равен 1, мы проверяем максимальное количество.
maxsum = Math.max либо cursum = 1, либо maxsum, равное -бесконечности; 1 больше, следовательно, становится новой максимальной суммой.
Затем курсор уменьшается путем удаления первого элемента, чтобы уменьшить окно и добавить еще один элемент.
cursum = cursum(1)-num[i(1) — (size(2)-1)]
курсум = 1 — число[0]
курс = 1 — -1 = 0
При этом первый индекс удаляется из суммы, и цикл продолжается до тех пор, пока мы не дойдем до конца массива.
Затем верните макс.
Полный код
var Maxsubarr = function(nums,size){
let cursum = 0;
let max = -infinity; //in case we have negative numbers.
for(let i = 0; i<nums.length; i++){
cursum += nums[i];
if(i >= size - 1){
maxsum = Math.max(cursum,maxsum);
cursum -= nums[i - (size - 1)];
}
}
return maxsum;
};
Динамический вариант со вспомогательной структурой данных
Самая длинная подстрока, содержащая не более k различных.
Под вспомогательным я подразумеваю использование массива, связанного списка или хэш-карты.
Этот вопрос является вопросом литкода, проверенным гигантскими технологическими компаниями, например Microsoft.
Вопрос: Имея строку s и целое число k, верните длину самой длинной подстроки s, содержащей не более k различных символов.
Пример ввода: s = ‘eceba’, k=2
выход : 3
Объяснение: подстрока «ece» имеет длину 3.
- Если длина строки равна или меньше определенного числа, верните длину строки.
if(k >= s.length ){
return s.length;
}
2. Определите пустую переменную хеш-карты.
let hmap = {}
let max = 0;
3. Итерация по строке.
for(let right=0,left=0; right<s.length; right++){
}
4. Добавление значений в хэш-карту во время или увеличение ее номера, если она уже есть.
hmap[s[right]] = (hmap[s[right]]||0)+1;
5. Удалите левый символ индекса, если уникальные символы превышают допустимые значения.
while(Object.keys(hmap).length>k){
}
6. Если значение символа равно 0, удалите его, а если не 0, просто уменьшите значение на 1.
if(--hmap[s[left]] === 0){
delete hmap[s[left]]
}
left ++;
7. Получая максимальное значение, вы сравниваете максимальное значение и вычитание справа, например, 6, и слева, например, 4 + 1. Если вычитание больше, то это максимальное значение.
max = Math.max(max,right-left+1);
Полный код
var lengthOfLongestSubstringKDistinct = function(s, k) {
if(k >= s.length ){
return s.length;
}
let hmap = {}
let max = 0;
for(let right=0,left=0; right<s.length; right++){
hmap[s[right]] = (hmap[s[right]]||0)+1;
while(Object.keys(hmap).length>k){
if(--hmap[s[left]] === 0){
delete hmap[s[left]]
}
left ++;
}
max = Math.max(max,right-left+1);
}
return max;
}
