Liugakna algoritmi juhend ja kuidas seda Go-s rakendada

Numbrite ja tähemärkide jadadega toimingute sooritamine on programmeerimise oluline aspekt. Liugakna algoritm on üks standardseid algoritme selle tegemiseks.

See on elegantne ja mitmekülgne lahendus, mis on leidnud tee mitmesse domeeni. See algoritm võib mängida rolli stringidega manipuleerimisest massiivi läbimise ja jõudluse optimeerimiseni.

Niisiis, kuidas libiseva akna algoritm töötab ja kuidas saate seda Go-s rakendada?

Lükandakna algoritmi mõistmine

Seal on palju tippalgoritme mida on programmeerijana kasulik teada ja libistatav aken on üks neist. See algoritm keerleb lihtsa kontseptsiooni ümber, mille kohaselt säilitatakse andmejada dünaamiline aken, et tõhusalt töödelda ja analüüsida nende andmete alamhulka.

Algoritmi saate rakendada arvutusprobleemide lahendamisel, mis hõlmavad massiive, stringe või andmejadasid.

Liugakna algoritmi põhiidee on määratleda fikseeritud või muutuva suurusega aken ja liigutada seda läbi sisendandmete. See võimaldab teil uurida sisendi erinevaid alamhulki ilma üleliigsete arvutusteta, mis võivad jõudlust takistada.

Siin on visuaalne kujutis selle toimimisest:

Akna piire võib kohandada vastavalt konkreetse probleemi nõuetele.

Lükandakna algoritmi rakendamine Go-s

Saate kasutada populaarset kodeerimisülesannet, et õppida, kuidas libiseva akna algoritm töötab: leida antud pikkusega alammassiivi suurim summa.

Selle näidisülesande eesmärk on leida suuruse alammassiivi k mille elementide summa on suurim väärtus. Lahendusfunktsioon sisaldab kahte parameetrit: sisendmassiivi ja positiivset täisarvu k.

Olgu näidismassiivil numbrid, nagu allolev kood näitab:

nums := []int{1, 5, 4, 8, 7, 1, 9}

Ja alammassiivi pikkus olgu k, väärtusega 3:

k := 3

Seejärel saate deklareerida funktsiooni, et leida k pikkusega alammassiivide maksimaalne summa:

funcmaximumSubarraySum(nums []int, k int)int {
// body
}

Võib-olla arvate, et aken peab olema massiiv, mis salvestab sihtelementide koopiad. Kuigi see on valik, töötab see halvasti.

Selle asemel peate lihtsalt määratlema akna piirid, et seda jälgida. Näiteks sel juhul on esimese akna algusindeks 0 ja lõppindeks k-1. Akna libistamise käigus värskendate neid piire.

Selle ülesande lahendamise esimene samm on saada esimese suuruse k alammassiivi summa. Lisage oma funktsioonile järgmine kood:

var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
}
maxSum = windowSum

Ülaltoodud kood deklareerib algoritmi jaoks vajalikud muutujad ja leiab massiivi esimese akna summa. Seejärel initsialiseeritakse maxSum esimese akna summaga.

Järgmine samm on libistage akent itereerides läbi numbrid massiiv indeksist k lõpuni. Akna libistamise igal etapil:

1. Värskenda akenSum lisades praeguse elemendi ja lahutades elemendi at akenStart.
2. Värskenda maxSum kui uus väärtus akenSum on sellest suurem.

Järgmine kood rakendab libisevat akent. Lisage see maksimaalneSubarraySum funktsiooni.

for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++
}

Kui tsükkel on lõppenud, on teil suurim summa maxSum, mille saate tagastada funktsiooni tulemusel:

return maxSum

Teie täielik funktsioon peaks välja nägema järgmine:

funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
 windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
 }
 maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++ 
 }
return maxSum
}

Algoritmi testimiseks saate määratleda põhifunktsiooni, kasutades väärtusi numbrid ja k varasemast:

funcmain() {
 nums := []int{1, 5, 4, 8, 7, 1, 9}
 k := 3
 fmt.Println(maximumSubarraySum(nums, k))
}

Väljund on sel juhul 19, mis on alammassiivi [4, 8, 7] summa, mis on suurim.

Nüüd saate sama tehnikat rakendada sarnastele probleemidele isegi teistes keeltes, näiteks korduvate elementide käsitlemine aknas, kasutades a Java räsikaart, näiteks.

Optimaalsed algoritmid toovad kaasa tõhusad rakendused

See algoritm annab tunnistust tõhusate lahenduste võimsusest probleemide lahendamisel. Lükandaken maksimeerib jõudlust ja välistab tarbetud arvutused.

Hea arusaamine libiseva akna algoritmist ja selle rakendamisest Go-s võimaldab teil rakenduste loomisel toime tulla reaalsete stsenaariumidega.