Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen
Laske samanaikaiset välit tapahtumien avulla
Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Suurimman päällekkäisyyden kysymys
Kuinka monta väliä kattaa saman ajanhetken yhtä aikaa? Huippumäärä on suurin päällekkäisyys eli aikajanan vilkkain kohta. 📈
Ajatelkaa tapahtumina
Lakatkaa ajattelemasta kokonaisia välejä. Jakakaa jokainen väli kahdeksi tapahtumaksi: alkuun sijoittuvaksi +1-tapahtumaksi ja loppuun sijoittuvaksi -1-tapahtumaksi.
Muodostakaa tapahtumalista
Lisätkää jokaisesta välistä alku- ja lopputapahtuma yhteiseen listaan. Jokainen tapahtuma sisältää sijainnin ja plus- tai miinus-yhden suuruisen deltan.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Lajitelkaa tapahtumat
Lajitelkaa jokainen tapahtuma sijainnin mukaan, jotta voitte pyyhkäistä aikajanan vasemmalta oikealle ja käsitellä muutokset oikeassa järjestyksessä.
events.sort()Pyyhkäiskää ja laskekaa
Käykää lajitellut tapahtumat läpi ja ylläpitäkää juoksevaa laskuria. Lisätkää jokainen delta sen kohdalla, ja laskuri kertoo, kuinka monta väliä on parhaillaan aktiivisena.
active = 0
for pos, delta in events:
active += deltaSeuratkaa huippua
Verratkaa jokaisen päivityksen jälkeen laskuria siihen asti parhaana pitämäänne arvoon. Suurin laskurin saavuttama arvo on suurin päällekkäisyys.
best = max(best, active)Tasatilanteen ratkaisu
Saman sijainnin kohdalla järjestyksellä on merkitystä. Jos kohdassa x päättyvän välin tulee vapauttaa paikka ennen kohdassa x alkavaa väliä, lajitelkaa loput ennen alkuja samassa kohdassa.
Koodatkaa deltat oikeaa lajittelua varten
Kätevä tapa ratkaista tasatilanteet on valita deltat niin, että tuple-lajittelu hoitaa asian puolestanne. Sijoittakaa -1 delta ennen +1-deltaa, kun sijainnit ovat samat.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieMiksi tämä on nopea
Luotte 2n tapahtumaa, lajittelette ne kerran ja pyyhkäisette ne kerran. Koko menetelmän aikavaativuus on O(n log n), koska yksi lajittelu määrää sen kustannuksen.
Missä tätä käytetään
Suurin päällekkäisyys ratkaisee klassisia tehtäviä, kuten kokouksiin tarvittavan vähimmäismäärän huoneita tai palvelimen samanaikaisten käyttäjien huippumäärän selvittämisen.
Enemmän kuin pelkkä laskeminen
Sama pyyhkäisy laajenee helposti: voitte seurata katetun alueen kokonaispituutta tai etsiä kaikki sijainnit, joissa määrä muuttuu, ja tehdä kaiken yhdellä lineaarisella läpikäynnillä.
Pikatarkistus
Pyyhkäisette tapahtumat suurimman päällekkäisyyden löytämiseksi.
Kertaus
Muutatte välit +1-alku- ja -1-lopputapahtumiksi, lajittelette ne ja pyyhkäisette laskurilla löytääksenne huippuarvon. Ratkaiskaa tasatilanteet käsittelemällä loppuvat välit ennen alkavia. 🚀
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 ”Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen” ilmainen?
Kyllä – oppitunnin ”Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen” 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 ”Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen”?
Laske samanaikaiset välit tapahtumien avulla 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 3/4.
Kuinka kauan ”Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen”-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
- Lajittele välit alun perusteella
- Päällekkäisten välien yhdistäminen
- Pyyhkäisylinja suurimman päällekkäisyyden löytämiseen
- Päällekkäisyyden poistamiseen tarvittavat vähimmäispoistot