Ryhmittely ja ämpäröinti mapilla
Ryhmittele anagrammit ja samankaltaiset alkiot
Ryhmittely ja ämpäröinti mapilla on ilmainen Competitive Programming Academy-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 Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Ryhmittely on toimintamalli
Monissa tehtävissä pyydetään ryhmittelemään alkiot jonkin yhteisen ominaisuuden perusteella. Avaimen ja lokeron yhdistävä kartoitus tekee tästä yhden selkeän läpikäynnin. 🗂️
Valitse ryhmittelyavain
Koko tempun ydin on valita avain, joka on saman ryhmän alkioille sama. Kun tämä on oikein, loppu on helppoa.
Ryhmittele defaultdictilla
Käytä defaultdict(list)-rakennetta, jotta jokainen uusi avain aloittaa tyhjästä lokerosta. Voit lisätä alkioita tarkistamatta koskaan, onko avain olemassa.
from collections import defaultdict
buckets = defaultdict(list)Silmukan ydin
Laske jokaiselle alkiolle sen avain ja lisää alkio append-metodilla kyseisen avaimen lokeroon. Yksi rivi alkiota kohti ryhmittelee kaiken.
for word in words:
buckets[key_of(word)].append(word)Ryhmittele anagrammit
Anagrammeissa on samat lajitellut kirjaimet, joten lajiteltu merkkijono on täydellinen ryhmittelyavain. Lajittele kerran ja sijoita sitten alkiot sen perusteella lokeroihin.
k = ''.join(sorted(word))
buckets[k].append(word)Tuple-avaimet lukumäärille
Kun lajittelu on hidasta, myös kirjainten lukumääristä koostuva tuple toimii avaimena. Tuplet ovat hashattavia, joten ne sopivat suoraan dictiin.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Ryhmittele ominaisuuden perusteella
Ryhmittele luvut jäännöksen, parillisuuden tai pituuden perusteella vaihtamalla vain avainta. Toimintamalli pysyy samana eri tehtävissä.
for n in nums:
buckets[n % 3].append(n)Lokerolajittelun idea
Kun arvot kuuluvat pieneen vaihteluväliin, sijoita jokainen indeksoituun lokeroon ja lue ne järjestyksessä. Näin lajittelu on lähes lineaarista.
for x in nums:
bucket[x].append(x)Kerää tulokset
Lokeroinnin jälkeen vastaus löytyy yleensä sanakirjan values-arvoista. Muunna ne listaksi, jos tuomari odottaa ryhmiä sellaisinaan.
result = list(buckets.values())Laske ryhmittäin
Jos tarvitset vain ryhmien koot, kokoa alkiot Counteriin tai summaa pituudet lopuksi. Valitse tapa sen mukaan, mitä tehtävässä todella kysytään.
sizes = {k: len(v) for k, v in buckets.items()}Miksi kartoitus kannattaa
Kartoitukseen perustuva ryhmittely on O(n) eikä vaadi jokaisen parin vertailemista. Hajautettu avain hoitaa vastaavuuksien etsimisen puolestasi.
Pikatarkistus
Haluat ryhmitellä sanat niin, että anagrammit päätyvät samaan lokeroon.
Kertaus
Ryhmittele sijoittamalla jokaisen alkion avain defaultdictin lokeroon yhdellä O(n)-läpikäynnillä. Valitse avain huolellisesti, niin ryhmittelytehtävät helpottuvat huomattavasti. 🚀
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 ”Ryhmittely ja ämpäröinti mapilla” ilmainen?
Kyllä – oppitunnin ”Ryhmittely ja ämpäröinti mapilla” 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 ”Ryhmittely ja ämpäröinti mapilla”?
Ryhmittele anagrammit ja samankaltaiset alkiot 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 4/4.
Kuinka kauan ”Ryhmittely ja ämpäröinti mapilla”-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
- Setit jäsenyyden tarkistamiseen ja duplikaattien poistoon
- Dictionariet hakutauluina
- Counter ja defaultdict käytännössä
- Ryhmittely ja ämpäröinti mapilla