Bittimaskit pieninä joukkoina
Esitä osajoukot kokonaislukuina
Bittimaskit pieninä joukkoina 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.
Kokonaisluku joukkona
Yksi kokonaisluku voi edustaa kokonaista joukkoa: bitin i arvo 1 tarkoittaa, että alkio i kuuluu joukkoon. Näin osajoukot voidaan pakata yhteen pieneen ja nopeaan arvoon. 🎒
Tyhjä ja täysi joukko
Luku 0 on tyhjä joukko, kun taas arvo, jonka n alinta bittiä ovat kaikki päällä, tarkoittaa, että kaikki alkiot ovat mukana.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAlkion lisääminen
Lisätkää alkio i joukkoon suorittamalla OR-operaatio sen bitillä. Tämä on täsmälleen sama kuin bitin asettaminen, mutta nyt sen voi tulkita yhden alkion kanssa tehdyksi yhdisteeksi.
s = 0
s |= (1 << 2) # add element 2Alkion poistaminen
Poistakaa alkio i suorittamalla AND-operaatio käänteisellä bitillä. Alkio poistuu joukosta ja kaikki muut alkiot säilyvät ennallaan. Tämä on yhden alkion muodostama joukon erotus.
s &= ~(1 << 2) # remove element 2Jäsenyyden testaaminen
Tarkistakaa, kuuluuko alkio i joukkoon, suorittamalla AND-operaatio sen bitillä. Nollasta poikkeava tulos tarkoittaa, että se on joukon jäsen.
if s & (1 << 2):
print('2 is in the set')Yhdiste ja leikkaus
Muodostakaa kahden maskin yhdiste OR-operaatiolla ja niiden leikkaus AND-operaatiolla. Kokonaiset joukkotoiminnot muuttuvat näin kukin yhdeksi konekäskyksi.
union = a | b
inter = a & bJoukon koko on popcount
Bittimaskin alkioiden määrä on yksinkertaisesti sen asetettujen bittien määrä. Käyttäkää bit_count-metodia saadaksenne koon heti.
size = mask.bit_count()Käykää läpi kaikki osajoukot
Kun alkioita on n, kokonaisluvut 0:sta lukuun 2:n potenssiin n miinus 1 luettelevat kaikki osajoukot. Yksi yksinkertainen range-silmukka kattaa ne kaikki.
for mask in range(1 << n):
pass # mask is one subsetKäykää alibittimaskit nopeasti läpi
Jos haluatte käydä läpi vain tietyn maskin osajoukot, käyttäkää klassista submask-silmukkaa. Se käy jokaisen osajoukon läpi laskevassa järjestyksessä.
sub = mask
while sub:
sub = (sub - 1) & maskBittimaski-DP:tä käytetään tässä
Bittimaskit toimivat monien DP-tehtävien tilana, esimerkiksi kauppamatkustajan ongelmassa, jossa maski kertoo, missä solmuissa olette jo käyneet.
Pitäkää n pienenä
Koska osajoukkoja on 2:n potenssiin n, tämä tekniikka toimii käytännössä vain pienillä n:n arvoilla, yleensä noin 20:een asti. Sen jälkeen määrä kasvaa räjähdysmäisesti. ⚠️
Pikatarkistus
Vielä yksi joukkoa bittimaskina koskeva kysymys.
Kertaus: bittimaskijoukot
Voitte tallentaa joukon yhteen kokonaislukuun, lisätä ja poistaa alkioita maskien avulla sekä käydä läpi jokaisen osajoukon. Tämä mahdollistaa nopean bittimaski-DP:n. 🎉
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 ”Bittimaskit pieninä joukkoina” ilmainen?
Kyllä – oppitunnin ”Bittimaskit pieninä joukkoina” 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 ”Bittimaskit pieninä joukkoina”?
Esitä osajoukot kokonaislukuina 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 ”Bittimaskit pieninä joukkoina”-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
- AND, OR, XOR ja siirrot
- Bitin asettaminen, tyhjentäminen ja vaihtaminen
- Bittien ja alimman asetetun bitin laskeminen
- Bittimaskit pieninä joukkoina