Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Polynominen merkkijonohajautus

Vertaa alimerkkijonoja vakioajassa

Oppitunti 2/413 vaihetta

Polynominen merkkijonohajautus on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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.

Alimerkkijonojen nopea vertailu

Usein on selvitettävä, ovatko kaksi alimerkkijonoa samoja. Merkkien vertaaminen yksitellen on hidasta, joten muunnamme jokaisen merkkijonon luvuksi. 🔢

Hajautuksen idea

Hash kuvaa merkkijonon yhdeksi kokonaisluvuksi. Jos kaksi merkkijonoa eroaa toisistaan, myös niiden hash-arvot eroavat lähes aina.

Käsittele merkkijonoja polynomeina

Käsittelemme jokaista merkkiä luvun p kantaluvun numeroina. Tämä polynomin näkökulma muuntaa merkkijonon yhdeksi suureksi painotetuksi summaksi.

h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * p

Valitse kanta ja modulo

Valitse kannaksi alkuluku, kuten 31, ja käytä suurta alkulukua modulona. Modulo pitää luvut pieninä ja estää ylivuodon.

BASE = 31
MOD = 10**9 + 9

Yhden hash-arvon laskeminen

Käy merkkijono läpi ja yhdistä jokainen merkki mukaan Hornerin säännöllä ottaen modulon jokaisessa vaiheessa.

h = 0
for c in s:
    h = (h * BASE + ord(c)) % MOD

Prefiksihashit

Tallenna jokaiselle kohdalle prefiksihash. Sen jälkeen minkä tahansa alimerkkijonon hash saadaan nopeasti vähentämällä.

pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MOD

Kannan potenssit

Esilaske myös kannan potenssit. Niiden avulla kaksi prefiksiä kohdistetaan toisiinsa vähennettäessä.

pw[i] = (pw[i - 1] * BASE) % MOD

Alimerkkijonon hash ajassa O(1)

Merkkijonon s[l..r] hash saadaan kahden prefiksihashin vähennyslaskuna, joka skaalataan potenssilla. Yhden kyselyn aika on vakio.

def sub(l, r):
    return (pre[r] - pre[l] * pw[r - l]) % MOD

Varokaa törmäyksiä

Kahdella eri merkkijonolla voi olla sama hajautusarvo; tätä kutsutaan törmäykseksi. Se on harvinaista, mutta kilpailuissa syötteet saatetaan joskus suunnitella aiheuttamaan sellainen.

Kaksoishajautus varmistuksena

Käyttäkää kahta toisistaan riippumatonta moduloa ja verratkaa molempia hajautusarvoja. Törmäys molemmissa samanaikaisesti on käytännössä mahdoton.

Hajautuksen vahvuudet

Hajautus mahdollistaa osamerkkijonojen vertailun, toistojen etsimisen ja hahmonten haun. Se on monipuolinen yleisväline.

Pikatarkistus

Valitkaa oikea työkalu, kun haluatte vertailla turvallisesti monia osamerkkijonoja.

Vastaa interaktiivisessa oppitunnissa

Kertaus: hajautus toimii

Osaatte nyt muuntaa merkkijonot polynomihajautusarvoiksi, hakea minkä tahansa osamerkkijonon ajassa O(1) ja suojautua törmäyksiltä. 🚀

Aloita maksutta

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

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Polynominen merkkijonohajautus” ilmainen?

Kyllä – oppitunnin ”Polynominen merkkijonohajautus” 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 ”Polynominen merkkijonohajautus”?

Vertaa alimerkkijonoja vakioajassa 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 2/4.

Kuinka kauan ”Polynominen merkkijonohajautus”-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

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin