Gruppér og kategorisér med et map
Gruppér anagrammer og lignende elementer
Gruppér og kategorisér med et map er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Gruppering er et mønster
Mange opgaver beder dig om at gruppere elementer, der har noget til fælles. En afbildning fra nøgle til beholder gør det til ét enkelt, overskueligt gennemløb. 🗂️
Vælg grupperingsnøglen
Hele tricket er at vælge en nøgle, der er identisk for elementer i samme gruppe. Når det er på plads, er resten nemt.
Brug defaultdict som beholder
Brug en defaultdict(list), så hver ny nøgle starter med en tom beholder. Du tilføjer elementer uden nogensinde at tjekke, om nøglen findes.
from collections import defaultdict
buckets = defaultdict(list)Den centrale løkke
For hvert element beregner du dets nøgle og tilføjer elementet til den pågældende nøgles beholder. Én linje pr. element grupperer alt.
for word in words:
buckets[key_of(word)].append(word)Gruppér anagrammer
Anagrammer har de samme sorted-bogstaver, så den sorterede streng er den perfekte gruppenøgle. Sortér én gang, og læg derefter elementerne i beholdere efter den.
k = ''.join(sorted(word))
buckets[k].append(word)Tupelnøgler til optællinger
Når sortering er langsom, fungerer en tuple med bogstavoptællinger også som nøgle. Tupler er hashbare, så de passer problemfrit ind i en dict.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Gruppér efter en egenskab
Gruppér tal efter rest, paritet eller længde blot ved at ændre nøglen. Mønstret er det samme på tværs af opgaver.
for n in nums:
buckets[n % 3].append(n)Idéen bag bucket-sortering
Når værdierne ligger i et lille interval, lægger du hver af dem i en indekseret beholder og læser dem i rækkefølge. Det giver sortering tæt på lineær tid.
for x in nums:
bucket[x].append(x)Saml resultaterne
Efter gruppering er svaret normalt dictens values. Konvertér dem til en liste, når dommeren forventer selve grupperne.
result = list(buckets.values())Optælling pr. gruppe
Hvis du kun har brug for gruppers størrelser, kan du lægge dem i en Counter eller summere længderne til sidst. Vælg det, som spørgsmålet faktisk beder om.
sizes = {k: len(v) for k, v in buckets.items()}Hvorfor afbildning vinder
Gruppering med en afbildning tager O(n) i stedet for at sammenligne hvert par. Den hashberegnede nøgle udfører matchningen for dig.
Hurtigt tjek
Du vil gruppere ord, så anagrammer ender i den samme beholder.
Opsummering
Gruppér ved at lægge hvert elements nøgle i en defaultdict-beholder i ét gennemløb på O(n). Vælg nøglen med omhu, så bliver grupperingsopgaver meget lettere. 🚀
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Gruppér og kategorisér med et map” gratis?
Ja — hele teksten til “Gruppér og kategorisér med et map” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Gruppér og kategorisér med et map”?
Gruppér anagrammer og lignende elementer Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Gruppér og kategorisér med et map”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Sets til medlemskab og deduplikering
- Dictionaries som opslagstabeller
- Counter og defaultdict i praksis
- Gruppér og kategorisér med et map