Erotustaulukot välin päivityksiin
Suorita useita koko välin lisäysoperaatioita nopeasti
Erotustaulukot välin päivityksiin on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/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 Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Kääntäkää ongelma toisinpäin
Prefix-summat vastasivat välikyselyihin nopeasti. Erotustaulukon avulla voitte puolestaan tehdä useita välin päivityksiä nopeasti. 🔁
Hidas tapa
Arvon lisääminen välin jokaiseen alkioon monta kertaa maksaa O(n) päivitystä kohden. Q päivityksen yhteydessä tämä kustannus kasvaa valtavaksi.
Tallentakaa muutokset
Sen sijaan että muuttaisitte jokaista solua, tallentakaa vain kohdat, joissa muutos alkaa ja päättyy. Merkitkää reunat, älkää keskiosaa.
Mitä erotustaulukko sisältää
Erotustaulukko tallentaa kunkin alkion ja sitä edeltävän alkion välisen eron. Yhden eron muokkaaminen siirtää vaikutusta koko myöhempään osuuteen.
Kahden merkinnän niksi
Lisätessänne arvon v välille l–r lisätkää v indeksissä l ja vähentäkää v indeksissä r + 1. Vain kaksi muokkausta kattaa koko välin.
diff[l] += v
diff[r + 1] -= vMiksi vähennys
Indeksissä l oleva plusmerkki kytkee muutoksen päälle, ja indeksissä r + 1 oleva miinusmerkki kytkee sen jälleen pois päältä. Yhdessä ne rajaavat päivityksen yhteen väliin.
Tehkää kaikki päivitykset edullisesti
Jokainen päivitys vaatii vain kaksi taulukkoon kirjoittamista, joten q päivityksen tekeminen maksaa yhteensä O(q). Raskas työ siirtyy loppuun.
Palauttakaa lopullinen taulukko
Kun kaikki merkinnät on tehty, laskekaa erotustaulukosta prefix-summa. Yksi läpikäynti palauttaa jokaisen lopullisen arvon.
for i in range(1, n):
diff[i] += diff[i - 1]Varaa suojapaikka
Tehkää taulukosta yhden solun verran pidempi, jotta r + 1 ei koskaan ylitä sen loppua. Ylimääräinen suojapaikka estää indeksivirheet.
Kokonaiskustannus
Käytätte päivitysten merkitsemiseen O(q) aikaa ja yhden O(n):n läpikäynnin taulukon palauttamiseen. Yhdistetty kustannus on paljon pienempi kuin naiivi O(n kertaa q).
Missä se on parhaimmillaan
Erotustaulukot ovat parhaimmillaan varausmäärien, tietullien ja muiden sellaisten tehtävien yhteydessä, joissa on paljon välin lisäys -operaatioita ja yksi lopullinen lukukerta.
Pikatarkistus
Lisäätte arvon v jokaiseen alkioon indeksistä l indeksiin r.
Kertaus
Voitte koota välin päivitykset erotustaulukolla: merkitkää l ja r + 1 ja laskekaa sitten prefix-summa kerran taulukon palauttamiseksi. Nopeat päivitykset, yksi lukukerta. ✅
Opi Valmistautuminen ohjelmointihaastatteluihin 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
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Erotustaulukot välin päivityksiin” ilmainen?
Kyllä – oppitunnin ”Erotustaulukot välin päivityksiin” 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 Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Erotustaulukot välin päivityksiin”?
Suorita useita koko välin lisäysoperaatioita nopeasti Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Erotustaulukot välin päivityksiin”-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ä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-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
- Prefix-summataulukon rakentaminen
- Minkä tahansa välin summa vähentämällä
- Tavoitesumman sisältävien alitaulukoiden laskeminen
- Erotustaulukot välin päivityksiin