Juhend libiseva akna algoritmi ja selle rakendamiseks Go-s

Juhend libiseva akna algoritmi ja selle rakendamiseks Go-s
Teiesugused lugejad aitavad MUO-d toetada. Kui teete ostu meie saidil olevate linkide abil, võime teenida sidusettevõtte komisjonitasu. Loe rohkem.

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





MUO päeva video SISUGA JÄTKAMISEKS KERIMISE

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.

kuidas ehitada nutikat peeglit

Siin on visuaalne kujutis selle toimimisest:



Kaks vaadet, mis näitavad numbrite komplekti. Igaühel on esile tõstetud 3 numbrit sisaldav liugaken, teisel juhul üks samm edasi.

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

Lükandakna algoritmi rakendamine Go-s

Võite 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:

 func maximumSubarraySum(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 maxAmount 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 maxAmount 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 maxAmount , mille saate tagastada funktsiooni tulemusel:

 return maxSum

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

 func maximumSubarraySum(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:

 func main() { 
    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.

parim fototöötlustarkvara algajatele