Säännön täyttävien ikkunoiden laskeminen
At-most-K miinus at-most-(K-1) -niksi
Säännön täyttävien ikkunoiden laskeminen 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.
Laskeminen, ei mittaaminen
Joskus on löydettävä pisimmän ikkunan sijaan niiden osataulukoiden lukumäärä, jotka täyttävät tietyn säännön. Pieni temppu muuttaa tämän helposti ratkaistavaksi liukuikkunatehtäväksi. 🔢
Täsmälleen K:n haaste
Tasan K jotakin sisältävien osataulukoiden laskeminen suoraan on hankalaa. Raja vaihtuu jatkuvasti, minkä vuoksi yhden selkeän ikkunan muodostaminen on vaikeaa.
Enintään K -näkökulma
Enintään K jotakin sisältävien osataulukoiden laskeminen on paljon helpompaa yhdellä ikkunalla. Kun laajennatte ikkunaa oikealle, jokainen kelvollinen alku tuottaa yhden laskettavan osataulukon.
Vähennystemppu
Täsmälleen K on atMost(K) miinus atMost(K - 1). Kaksi helppoa laskua yhdistetään näin vaikeammaksi laskuksi, jota todella tarvitaan.
answer = at_most(k) - at_most(k - 1)Rakentakaa apufunktio
Kirjoittakaa yksi funktio, joka laskee enintään k jotakin sisältävät osataulukot. Se siirtää ikkunaa ja kutistaa sitä aina, kun lukumäärä ylittää k:n.
def at_most(k):
left = 0
total = 0Kutistakaa ehdon rikkoutuessa
Laajentakaa ikkunaa oikealle ja päivittäkää sen tila. Kun ikkunassa on enemmän kuin k alkiota, siirtäkää left-osoitinta eteenpäin, jotta ikkuna palaa sallitulle alueelle.
while count > k:
# remove a[left]
left += 1Lisätkää ikkunan lukumäärä
Kun ikkuna on korjattu, jokainen right-kohtaan päättyvä osataulukko, jonka alku on kohdassa left tai sen jälkeen, on kelvollinen. Lisätkää tulokseen right - left + 1.
total += right - left + 1Miksi tämä lukumäärä toimii
Kun right on kiinteä, kelvolliset aloituskohdat ovat left, left+1 ja niin edelleen kohtaan right asti. Näin saadaan täsmälleen right - left + 1 osataulukkoa, jotka kaikki sisältävät enintään k alkiota.
Yhdistäkää kaksi kutsua
Kutsukaa apufunktiota kahdesti ja vähentäkää tulokset. Kumpikin kutsu vie ajan O(n), joten koko täsmälleen K:n laskenta on edelleen lineaarinen.
return at_most(k) - at_most(k - 1)Huomioikaa reunatapaus
Kun k on nolla, atMost(k - 1) käyttäisi arvoa miinus yksi. Käsitelkää tämä tapaus erikseen, jotta apufunktio palauttaa järkevän nollatuloksen.
Missä tätä käytetään
Tämä at-most miinus at-most -ajatus sopii osataulukoiden laskemiseen, kun niissä on täsmälleen K eri arvoa, K paritonta lukua tai jokin muu monotoninen ikkunakohtainen ominaisuus.
Pikatarkistus
Haluatte laskea niiden osataulukoiden lukumäärän, joissa on täsmälleen K eri alkiota.
Kertaus
Täsmälleen K on yksinkertaisesti atMost(K) miinus atMost(K - 1). Kumpikin apufunktio siirtää ikkunaa ajassa O(n), joten koko laskenta pysyy lineaarisena. ✅
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 ”Säännön täyttävien ikkunoiden laskeminen” ilmainen?
Kyllä – oppitunnin ”Säännön täyttävien ikkunoiden laskeminen” 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 ”Säännön täyttävien ikkunoiden laskeminen”?
At-most-K miinus at-most-(K-1) -niksi 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 ”Säännön täyttävien ikkunoiden laskeminen”-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
- Kiinteän kokoisen ikkunan summat
- Muuttuvan kokoinen ikkuna kahdella osoittimella
- Pisin toistoton alimerkkijono
- Säännön täyttävien ikkunoiden laskeminen