Bīdāmo logu algoritma ceļvedis un tā ieviešana Go

Operāciju veikšana ar ciparu un rakstzīmju secībām ir būtisks programmēšanas aspekts. Bīdāmo logu algoritms ir viens no standarta algoritmiem, lai to izdarītu.

Tas ir elegants un daudzpusīgs risinājums, kas ir atradis ceļu vairākās jomās. No manipulācijām ar virknēm līdz masīvu pārvietošanai un veiktspējas optimizēšanai, šim algoritmam var būt nozīme.

Tātad, kā darbojas bīdāmo logu algoritms un kā to var ieviest programmā Go?

Izpratne par bīdāmo logu algoritmu

Tur ir daudzi populārākie algoritmi kas ir noderīgi zināt programmētājam, un bīdāmais logs ir viens no tiem. Šis algoritms griežas ap vienkāršu koncepciju, kā uzturēt dinamisku logu pār datu secību, lai efektīvi apstrādātu un analizētu šo datu apakškopas.

Algoritmu var lietot, risinot skaitļošanas problēmas, kas ietver masīvus, virknes vai datu secības.

Bīdāmo logu algoritma pamatideja ir definēt fiksēta vai mainīga izmēra logu un pārvietot to caur ievades datiem. Tas ļauj izpētīt dažādas ievades apakškopas bez liekiem aprēķiniem, kas var kavēt veiktspēju.

Šeit ir vizuāls attēlojums, kā tas darbojas:

Logu robežas var pielāgot atbilstoši konkrētās problēmas prasībām.

Bīdāmo logu algoritma ieviešana programmā Go

Varat izmantot populāru kodēšanas problēmu, lai uzzinātu, kā darbojas bīdāmā loga algoritms: atrast lielāko apakšmasīva summu ar noteiktu garumu.

Šīs izlases problēmas mērķis ir atrast lieluma apakšmasīvu k kuru elementu summa ir vislielākā. Risinājuma funkcijai ir divi parametri: ievades masīvs un pozitīvs vesels skaitlis k.

Ļaujiet izlases masīvam būt numuri, kā redzams tālāk redzamajā kodā:

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

Un ļaujiet apakšmasīva garumam būt k, ar vērtību 3:

k := 3

Pēc tam varat deklarēt funkciju, lai atrastu maksimālo apakšmasīvu summu ar garumu k:

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

Iespējams, jūs domājat, ka logam ir jābūt masīvam, kurā tiek glabātas mērķa elementu kopijas. Lai gan tā ir iespēja, tā darbojas slikti.

Tā vietā jums vienkārši jādefinē loga robežas, lai to izsekotu. Piemēram, šajā gadījumā pirmajā logā būs sākuma indekss 0 un beigu indekss k-1. Loga bīdīšanas procesā jūs atjaunināsit šīs robežas.

Pirmais solis, lai atrisinātu šo problēmu, ir iegūt pirmā k izmēra apakšmasīva summu. Pievienojiet savai funkcijai šādu kodu:

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

Iepriekš minētais kods deklarē algoritmam nepieciešamos mainīgos un atrod masīva pirmā loga summu. Pēc tam tas tiek inicializēts maxSum ar pirmā loga summu.

Nākamais solis ir pabīdiet logu atkārtojot caur numuri masīvs no indeksa k līdz beigām. Katrā loga bīdīšanas solī:

1. Atjaunināt logsSum pievienojot pašreizējo elementu un atņemot elementu pie logsStart.
2. Atjaunināt maxSum ja jaunā vērtība logsSum ir lielāks par to.

Šis kods ievieš bīdāmo logu. Pievienojiet to maximumSubarraySum funkciju.

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

Kad cilpa būs pabeigta, jums būs vislielākā summa maxSum, ko varat atgriezt funkcijas rezultātā:

return maxSum

Pilnai funkcijai vajadzētu izskatīties šādi:

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
}

Varat definēt galveno funkciju, lai pārbaudītu algoritmu, izmantojot vērtības numuri un k no iepriekšējiem:

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

Izvade šajā gadījumā būs 19, kas ir apakšmasīva [4, 8, 7] summa, kas ir lielākā.

Tagad varat izmantot to pašu paņēmienu līdzīgām problēmām, pat citās valodās, piemēram, apstrādāt atkārtotus elementus logā, izmantojot a Java hash karte, piemēram.

Optimāli algoritmi nodrošina efektīvus lietojumus

Šis algoritms ir apliecinājums efektīvu risinājumu jaudai, kad runa ir par problēmu risināšanu. Bīdāmais logs palielina veiktspēju un novērš nevajadzīgus aprēķinus.

Stingra izpratne par bīdāmo logu algoritmu un tā ieviešanu Go, veidojot lietojumprogrammas, jūs varat risināt reālās pasaules scenārijus.