Kaksi osoitinta järjestetyssä taulukossa
Siirrä päitä sisäänpäin tavoitteen saavuttamiseksi
Kaksi osoitinta järjestetyssä taulukossa 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.
Miksi kaksi osoitinta
Kahden osoittimen tekniikka käy taulukon läpi kahdella indeksillä sisäkkäisten silmukoiden sijaan. Näin monet O(n^2)-ratkaisut muuttuvat yhdeksi selkeäksi O(n)-läpikäynniksi. 🎯
Järjestys ratkaisee
Klassinen versio tarvitsee järjestetyn taulukon. Järjestys auttaa päättelyssä: oikealle siirtyminen kasvattaa arvoa ja vasemmalle siirtyminen pienentää sitä, joten jokainen askel on todellinen päätös.
Kaksi osoitinta päissä
Aseta toinen osoitin vasempaan päähän ja toinen oikeaan päähän. Ne ovat vastakkain ja pienentävät niiden välistä etäisyyttä vähitellen.
left = 0
right = len(a) - 1Siirrä päitä sisäänpäin
Jokaisella askeleella siirrät täsmälleen yhtä osoitinta sisäänpäin. Taulukon järjestys kertoo, kumpaa puolta on siirrettävä tavoitteen saavuttamiseksi.
Silmukan ehto
Jatka silmukointia niin kauan kuin left < right. Kun osoittimet kohtaavat tai ohittavat toisensa, kaikki hyödylliset parit on tarkistettu ja voit lopettaa.
while left < right:
# inspect a[left] and a[right]
passNykyisen summan tarkistaminen
Tarkastele lauseketta a[left] + a[right] nykyisenä ehdokkaana. Sen vertaaminen tavoitearvoon kertoo, tarvitsetko seuraavaksi suuremman vai pienemmän arvon.
total = a[left] + a[right]Liian pieni: siirrä vasemmalle
Jos summa alittaa tavoitteen, tarvitset enemmän. Siirrä vasenta osoitinta oikealle kohti suurempia arvoja, koska taulukko on järjestetty nousevasti.
if total < target:
left += 1Liian suuri: siirrä oikealle
Jos summa ylittää tavoitteen, tarvitset vähemmän. Siirrä oikeaa osoitinta vasemmalle kohti pienempiä arvoja pienentääksesi kokonaissummaa.
elif total > target:
right -= 1Jokainen askel poistaa työtä
Jokainen siirto poistaa kokonaisen joukon pareja, joita sinun ei enää tarvitse testata. Siksi läpikäynti on lineaarinen eikä kvadraattinen.
Miksi ratkaisu pysyy oikeana
Hylkäät vain parit, jotka eivät voi täsmätä, joten oikea vastaus ei koskaan jää väliin. Tämän ansiosta kahden osoittimen tekniikkaan voi luottaa kilpailuissa.
Päätepisteitä pidemmälle
Sama idea toimii myös monissa muunnelmissa: paikallaan kääntämisessä, osioinnissa ja yhdistämisessä. Kun opit kohtaavat osoittimet, kaikki nämä tuntuvat tutuilta.
Pikatarkistus
Käyt läpi järjestettyä taulukkoa molemmista päistä etsiessäsi tietyn suuruista summaa.
Kertaus
Kaksi osoitinta käy järjestetyn taulukon läpi molemmista päistä ja siirtää yhtä osoitinta sisäänpäin jokaisella askeleella ehdon left < right vallitessa. Menetelmä on lineaarinen ja oikea, ja se toimii monien tekniikoiden perustana. 🚀
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 ”Kaksi osoitinta järjestetyssä taulukossa” ilmainen?
Kyllä – oppitunnin ”Kaksi osoitinta järjestetyssä taulukossa” 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 ”Kaksi osoitinta järjestetyssä taulukossa”?
Siirrä päitä sisäänpäin tavoitteen saavuttamiseksi 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 ”Kaksi osoitinta järjestetyssä taulukossa”-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
- Kaksi osoitinta järjestetyssä taulukossa
- Tietyn summan muodostavan parin etsiminen
- Kaksoiskappaleiden poistaminen paikallaan
- Kahden järjestetyn sekvenssin yhdistäminen