Tijdens het oplossen van een geometrieprobleem kwam ik een benadering tegen die het Sliding Window Algorithm wordt genoemd.
Kon er niet echt studiemateriaal/details over vinden.
Waar gaat het algoritme over?
Antwoord 1, autoriteit 100%
Over het algemeen is een schuifvenster een sublijst die over een onderliggende verzameling loopt. D.w.z. als je een array hebt zoals
[a b c d e f g h]
er zou een schuifraam van maat 3 overheen lopen zoals
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
Dit is handig als u bijvoorbeeld een lopend gemiddelde wilt berekenen, of als u een set van alle aangrenzende paren wilt maken, enz.
Antwoord 2, autoriteit 49%
Ik zie het meer als een techniek dan als een algoritme. Het is een techniek die in verschillende algoritmen kan worden gebruikt.
Ik denk dat de techniek het beste wordt begrepen met het volgende voorbeeld. Stel je voor dat we deze array hebben:
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
Hoe vinden we de grootste som van vijf opeenvolgende elementen? We kijken eerst naar 5, 7, 1, 4, 3en zien dat de som 20is. Dan kijken we naar de volgende set van vijf opeenvolgende elementen, namelijk 7, 1, 4, 3, 6. De som hiervan is 21. Dit is meer dan onze vorige som, dus 7, 1, 4, 3, 6is momenteel de beste die we tot nu toe hebben.
Laten we kijken of we het kunnen verbeteren. 1, 4, 3, 6, 2? Nee, dat komt neer op 16. 4, 3, 6, 2, 9? Dat komt neer op 24, dus dat is de beste reeks die we hebben. Nu gaan we verder met de volgende reeks, 3, 6, 2, 9, 2. Dat komt neer op 22, wat niet beter is dan ons huidige beste van 24. En we hebben het einde bereikt, dus we zijn klaar.
De brute kracht om dit in code te implementeren is als volgt:
const getMaxSumOfFiveContiguousElements = (arr) => {
let maxSum = -Infinity;
let currSum;
for (let i = 0; i <= arr.length - 5; i++) {
currSum = 0;
for (let j = i; j < i + 5; j++) {
currSum += arr[j];
}
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
};
Wat is de tijdscomplexiteit hiervan? Het is O(n*k). De buitenste lus gaat door n - k + 1items, maar wanneer nveel groter is dan k, kunnen we de k + 1deel en noem het gewoon nitems. Dan gaat de innerlijke lus door kitems, dus we hebben O(n*k). Probeer het als volgt te visualiseren:
Kunnen we dit terugbrengen tot slechts O(n)? Laten we terugkeren naar deze array:
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
Eerst krijgen we de som van 5, 7, 1, 4, 3. Vervolgens hebben we de som van 7, 1, 4, 3, 6nodig. Visualiseer het zo, met een “venster” rond elke groep van vijf elementen.
Wat is het verschil tussen het eerste venster en het tweede venster? Welnu, het tweede venster verwijderde de 5aan de linkerkant, maar voegde een 6toe aan de rechterkant. Dus aangezien we weten dat de som van het eerste venster 20was, om de som van het tweede venster te krijgen, nemen we die 20, trekken de 5en voeg de 6toe om 21te krijgen. We hoeven niet elk element in het tweede venster te doorlopen en ze op te tellen (7 + 1 + 4 + 3 + 6). Dat zou herhaaldelijk en onnodig werk met zich meebrengen.
Hier wordt de benadering met het schuivende venster uiteindelijk twee bewerkingen in plaats van vijf, aangezien k5is. Dat is geen enorme verbetering, maar je kunt je voorstellen dat het voor grotere k(en grotere n) echt helpt.
Hier is hoe de code zou werken met behulp van de schuifvenstertechniek:
const getLargestSumOfFiveConsecutiveElements = (arr) => {
let currSum = getSum(arr, 0, 4);
let largestSum = currSum;
for (let i = 1; i <= arr.length - 5; i++) {
currSum -= arr[i - 1]; // subtract element to the left of curr window
currSum += arr[i + 4]; // add last element in curr window
largestSum = Math.max(largestSum, currSum);
}
return largestSum;
};
const getSum = (arr, start, end) => {
let sum = 0;
for (let i = start; i <= end; i++) {
sum += arr[i];
}
return sum;
};
En dat is de essentie van de schuifraamtechniek. Bij andere problemen doe je misschien iets ingewikkelders dan de som van de elementen in het venster krijgen. Of het raam zelf kan van verschillende grootte zijn in plaats van de vaste grootte van vijf die we hier zagen. Maar deze basistoepassing van de schuifraamtechniek zou u een basis moeten geven waarop u kunt bouwen.
Antwoord 3, autoriteit 24%
Het schuifvenster is een probleemoplossende techniek voor problemen waarbij arrays/lijsten betrokken zijn. Deze problemen zijn eenvoudig op te lossen met behulp van een brute force-benadering in O(n^2) of O(n^3). Met behulp van de ‘sliding window’-techniek kunnen we de tijdscomplexiteit terugbrengen tot O(n).
Geweldig artikel hierover vind je hier: https://medium .com/outco/how-to-solve-sliding-window-problems-28d67601a66
Dus het eerste dat u wilt kunnen doen, is een probleem identificeren
dat een schuifraamparadigma gebruikt. Gelukkig zijn er enkele veelvoorkomende
weggeefacties:
Het probleem is een datastructuur die geordend en itereerbaar is, zoals een array of een string
U zoekt naar een subbereik in die array/tekenreeks, zoals de langste, kortste of doelwaarde.
Er is een schijnbaar naïeve of brute force-oplossing die draait in O(N?), O(2^N) of een andere grote tijdscomplexiteit.
Maar de grootste weggeefactie is dat wat je zoekt is
vaak een soort optimaal, zoals de langste reeks of de kortste
opeenvolging van iets dat precies aan een bepaalde voorwaarde voldoet.
Antwoord 4, autoriteit 5%
Als aanvulling op de eerdere antwoorden zijn hier nog enkele bronnen die dit concept goed illustreren.
Deze YouTube-videois de beste die ik over dit onderwerp heb gevonden .
Hieris de lijst met vragen over leetcode die kunnen worden opgelost deze techniek gebruiken
Het glijdende venster is een van de meest voorkomende onderwerpen die in de coderingsrondes in de beste bedrijven worden gesteld, dus het is zeker de moeite waard om wat tijd te besteden om dit onder de knie te krijgen.