Mit einer Map gruppieren und einteilen
Gruppieren Sie Anagramme und ähnliche Elemente
Mit einer Map gruppieren und einteilen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Gruppieren als Muster
Viele Aufgaben verlangen, Elemente mit einer gemeinsamen Eigenschaft zu gruppieren. Eine Zuordnung von einem Schlüssel zu einem Behälter macht daraus einen einzigen übersichtlichen Durchlauf. 🗂️
Den Gruppierungsschlüssel wählen
Der entscheidende Trick besteht darin, einen Schlüssel zu wählen, der für Elemente derselben Gruppe identisch ist. Wenn das gelingt, ist der Rest einfach.
Mit defaultdict in Behälter einteilen
Verwenden Sie defaultdict(list), damit für jeden neuen Schlüssel ein leerer Behälter beginnt. Sie können Elemente anhängen, ohne jemals zu prüfen, ob der Schlüssel existiert.
from collections import defaultdict
buckets = defaultdict(list)Die zentrale Schleife
Berechnen Sie für jedes Element seinen Schlüssel und hängen Sie das Element an den Behälter dieses Schlüssels an. Eine Zeile pro Element gruppiert alles.
for word in words:
buckets[key_of(word)].append(word)Anagramme gruppieren
Anagramme haben dieselben sortierten Buchstaben. Daher ist die sortierte Zeichenkette der perfekte Gruppierungsschlüssel. Sortieren Sie einmal und teilen Sie anschließend danach in Behälter ein.
k = ''.join(sorted(word))
buckets[k].append(word)Tupel als Zählschlüssel
Wenn Sortieren zu langsam ist, eignet sich auch ein Tupel mit den Buchstabenanzahlen als Schlüssel. Tupel sind hashbar und lassen sich daher problemlos in einem Dictionary verwenden.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Nach einer Eigenschaft einteilen
Gruppieren Sie Zahlen nach Rest, Parität oder Länge, indem Sie einfach den Schlüssel ändern. Das Muster bleibt bei verschiedenen Aufgaben gleich.
for n in nums:
buckets[n % 3].append(n)Die Idee von Bucket Sort
Wenn die Werte in einen kleinen Bereich fallen, legen Sie jeden Wert in einen indizierten Behälter und lesen die Behälter der Reihe nach aus. So entsteht eine nahezu lineare Sortierung.
for x in nums:
bucket[x].append(x)Die Ergebnisse sammeln
Nach dem Einteilen in Behälter besteht die Antwort meist aus den values des Dictionaries. Wandeln Sie sie in eine Liste um, wenn der Judge die Gruppen selbst erwartet.
result = list(buckets.values())Pro Gruppe zählen
Wenn Sie nur die Größen der Gruppen benötigen, können Sie die Elemente in einem Counter sammeln oder am Ende die Längen addieren. Entscheiden Sie sich für die Variante, nach der die Aufgabe tatsächlich fragt.
sizes = {k: len(v) for k, v in buckets.items()}Warum eine Zuordnung besser ist
Das Gruppieren mit einer Zuordnung benötigt O(n) statt jedes Paar miteinander zu vergleichen. Der gehashte Schlüssel übernimmt die Zuordnung für Sie.
Kurzer Check
Sie möchten Wörter so gruppieren, dass Anagramme im selben Behälter landen.
Zusammenfassung
Gruppieren Sie, indem Sie den Schlüssel jedes Elements in einem defaultdict-Behälter ablegen und alles in einem Durchlauf von O(n) verarbeiten. Wählen Sie den Schlüssel sorgfältig, und Gruppierungsaufgaben werden zum Kinderspiel. 🚀
Häufig gestellte Fragen
Ist die Lektion „Mit einer Map gruppieren und einteilen“ kostenlos?
Ja — der vollständige Text von „Mit einer Map gruppieren und einteilen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Mit einer Map gruppieren und einteilen“?
Gruppieren Sie Anagramme und ähnliche Elemente Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Mit einer Map gruppieren und einteilen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Mengen für Mitgliedschaft und Deduplizierung
- Dictionaries als Nachschlagetabellen
- Counter und defaultdict in der Praxis
- Mit einer Map gruppieren und einteilen