Grupper og legg i bøtter med et map
Grupper anagrammer og lignende elementer
Grupper og legg i bøtter med et map er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Gruppering er et mønster
Mange oppgaver ber deg gruppere elementer som har noe til felles. En kobling fra nøkkel til beholder gjør dette til én ryddig gjennomgang. 🗂️
Velg grupperingsnøkkelen
Hele trikset er å velge en nøkkel som er identisk for elementer i samme gruppe. Når dette er riktig, blir resten enkelt.
Legg i bøtte med defaultdict
Bruk en defaultdict(list) slik at hver ny nøkkel starter med en tom bøtte. Du kan legge til elementer uten å sjekke om nøkkelen finnes.
from collections import defaultdict
buckets = defaultdict(list)Hovedløkken
For hvert element beregner du nøkkelen og legger elementet til i bøtten for denne nøkkelen. Én linje per element grupperer alt.
for word in words:
buckets[key_of(word)].append(word)Gruppér anagrammer
Anagrammer har de samme sorterte bokstavene, så den sorterte strengen er den perfekte gruppenøkkelen. Sorter én gang, og legg deretter elementene i bøtter etter den.
k = ''.join(sorted(word))
buckets[k].append(word)Tupler som nøkler for opptelling
Når sortering er langsomt, kan en tuppel med bokstavtall også brukes som nøkkel. Tupler er hashbare, så de passer fint inn i en dict.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Gruppér etter en egenskap
Gruppér tall etter rest, paritet eller lengde ved ganske enkelt å endre nøkkelen. Mønsteret er identisk på tvers av oppgaver.
for n in nums:
buckets[n % 3].append(n)Tanken bak bøttesortering
Når verdiene ligger innenfor et lite område, legger du hver av dem i en indeksert bøtte og leser dem i rekkefølge. Det gir sortering som er nesten lineær.
for x in nums:
bucket[x].append(x)Samle resultatene
Etter bøtteinndelingen er svaret vanligvis ordbokens values. Konverter dem til en liste når dommeren forventer selve gruppene.
result = list(buckets.values())Tell per gruppe
Hvis du bare trenger gruppenes størrelser, kan du legge dem i en Counter eller summere lengdene til slutt. Velg det som faktisk etterspørres i oppgaven.
sizes = {k: len(v) for k, v in buckets.items()}Hvorfor mapping vinner
Gruppering med en mapping tar O(n) i stedet for å sammenligne hvert par. Den hashede nøkkelen gjør samsvaringen for deg.
Hurtigsjekk
Du vil gruppere ord slik at anagrammer havner i samme bøtte.
Oppsummering
Gruppér ved å legge hvert elements nøkkel i en defaultdict-bøtte i én gjennomgang på O(n). Velg nøkkelen med omhu, så blir grupperingsoppgaver mye enklere. 🚀
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Grupper og legg i bøtter med et map» gratis?
Ja – hele teksten i «Grupper og legg i bøtter med et map» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Grupper og legg i bøtter med et map»?
Grupper anagrammer og lignende elementer Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Grupper og legg i bøtter med et map»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Mengder for medlemskap og deduplisering
- Ordbøker som oppslagstabeller
- Counter og defaultdict i praksis
- Grupper og legg i bøtter med et map