Kiinteän kokoisen ikkunan summat
Liikuta k:n pituista ikkunaa ajassa O(n)
Kiinteän kokoisen ikkunan summat on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Toistuvien summien ongelma
Monissa tehtävissä pyydetään laskemaan jokaisen k peräkkäisen alkion muodostaman lohkon summa. Jokaisen lohkon laskeminen uudelleen alusta asti on tehotonta, ja voitte tehdä sen tehokkaammin. 🪟
Hidas tapa ensin
Naiivi ratkaisu laskee jokaisen k:n pituisen ikkunan erikseen. Tämä toistaa samaa työtä ja vie aikaa O(n × k), mikä on liian hidasta suurilla syötteillä.
for i in range(n - k + 1):
s = sum(a[i:i + k])Keskeinen oivallus
Vierekkäiset ikkunat menevät lähes kokonaan päällekkäin. Kun ikkunaa siirretään yhden askeleen oikealle, siitä poistetaan vain vasemman reunan alkio ja oikealle lisätään yksi uusi alkio.
Alustakaa ensimmäinen ikkuna
Aloittakaa laskemalla ensimmäisten k alkion summa kerran. Tätä summaa päivitetään pohjana aina, kun ikkunaa siirretään eteenpäin.
window = sum(a[:k])
best = windowSiirtäkää ikkunaa yksi askel
Siirtäkää ikkunaa lisäämällä siihen tuleva alkio ja vähentämällä siitä poistuva alkio. Näin jokainen askel vaatii vakioajan O(1).
for i in range(k, n):
window += a[i] - a[i - k]Seuratkaa vastausta
Päivittäkää jokaisen siirron jälkeen tarvittavat tiedot, kuten tähän asti nähdyn ikkunan summan maksimi. Ikkunan arvo on aina heti käytettävissä.
best = max(best, window)Kokonaiskustannus on lineaarinen
Kosketatte jokaista alkiota kerran sen lisäämiseksi ja vielä kerran sen poistamiseksi, joten koko läpikäynnin aikavaativuus on O(n). Tämä riittää helposti suuriin rajoihin.
Huomioikaa indeksit
Ikkunasta poistuva alkio on a[i - k], ei a[i - 1]. Tämän siirtymän käsitteleminen oikein on yleisin kiinteän ikkunan virhe.
Keskiarvo saadaan samalla
Tarvitsetteko summan sijaan ikkunan suurimman keskiarvon? Jakakaa seurattu ikkunan summa vain k:lla. Liukuikkunan logiikka ei muutu lainkaan.
avg = window / kKäsitelkää pienet taulukot
Jos taulukko on lyhyempi kuin k, täyttä ikkunaa ei ole olemassa. Tarkistakaa len(a) suhteessa arvoon k heti alussa ja palauttakaa tulos ennenaikaisesti indeksivirheen välttämiseksi.
if n < k:
return NoneMilloin kiinteät ikkunat sopivat
Käyttäkää tätä mallia aina, kun ikkunan pituus on kiinteä ja arvot voidaan yhdistää tehokkaasti esimerkiksi summaksi, lukumääräksi tai yksinkertaisiksi juokseviksi tilastoiksi.
Pikatarkistus
Siirrätte k:n kokoista ikkunaa yhden askeleen oikealle taulukon yli.
Kertaus
Alustakaa ensimmäinen ikkuna kerran ja lisätkää ja vähentäkää arvoja jokaisella askeleella, jolloin siirto vie ajan O(1). Koko kiinteän koon läpikäynti toimii lineaarisessa ajassa. ✅
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Kiinteän kokoisen ikkunan summat” ilmainen?
Kyllä – oppitunnin ”Kiinteän kokoisen ikkunan summat” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Kiinteän kokoisen ikkunan summat”?
Liikuta k:n pituista ikkunaa ajassa O(n) Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Kiinteän kokoisen ikkunan summat”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Kiinteän kokoisen ikkunan summat
- Muuttuvan kokoinen ikkuna kahdella osoittimella
- Pisin toistoton alimerkkijono
- Säännön täyttävien ikkunoiden laskeminen