Regrouper et classer avec une table de correspondance
Regrouper les anagrammes et les éléments similaires
Regrouper et classer avec une table de correspondance est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Le regroupement est un motif
De nombreux problèmes vous demandent de regrouper les éléments qui ont une caractéristique commune. Une association entre une clé et un compartiment transforme cela en un seul parcours clair. 🗂️
Choisir la clé de regroupement
Toute l'astuce consiste à choisir une clé identique pour les éléments d'un même groupe. Si vous faites le bon choix, le reste est facile.
Créer un compartiment avec un dictionnaire à valeur par défaut
Utilisez defaultdict(list) afin que chaque nouvelle clé commence avec un compartiment vide. Vous ajoutez les éléments sans jamais vérifier si la clé existe.
from collections import defaultdict
buckets = defaultdict(list)La boucle principale
Pour chaque élément, calculez sa clé et append l'élément au compartiment correspondant. Une ligne par élément suffit pour tout regrouper.
for word in words:
buckets[key_of(word)].append(word)Regrouper les anagrammes
Les anagrammes possèdent les mêmes lettres sorted, la chaîne triée constitue donc la clé de regroupement idéale. Effectuez le tri une fois, puis rangez les éléments dans les compartiments correspondants.
k = ''.join(sorted(word))
buckets[k].append(word)Clés tuples pour les comptages
Lorsque le tri est lent, un tuple contenant les comptages de lettres peut également servir de clé. Les tuples sont hachables et s'intègrent donc parfaitement à un dictionnaire.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Créer des compartiments selon une propriété
Regroupez les nombres selon leur reste, leur parité ou leur longueur en modifiant simplement la clé. Le motif reste identique d'un problème à l'autre.
for n in nums:
buckets[n % 3].append(n)L'idée du tri par compartiments
Lorsque les valeurs appartiennent à un petit intervalle, placez chacune dans un compartiment indexé, puis lisez-les dans l'ordre. Vous obtenez un tri presque linéaire.
for x in nums:
bucket[x].append(x)Rassembler les résultats
Après le classement par compartiments, la réponse se trouve généralement dans les values du dictionnaire. Convertissez-les en liste lorsque le correcteur attend les groupes eux-mêmes.
result = list(buckets.values())Compter par groupe
Si vous avez seulement besoin de la taille des groupes, utilisez un compteur pour les compartiments ou additionnez les longueurs à la fin. Choisissez ce qui correspond réellement à la question.
sizes = {k: len(v) for k, v in buckets.items()}Pourquoi l'association est avantageuse
Regrouper avec une association s'effectue en O(n) au lieu de comparer chaque paire. La clé hachée réalise les correspondances à votre place.
Vérification rapide
Vous souhaitez regrouper les mots afin que les anagrammes se retrouvent dans le même compartiment.
Récapitulatif
Regroupez les éléments en associant la clé de chacun à un compartiment de dictionnaire à valeur par défaut, en un seul parcours O(n). Choisissez bien la clé et les problèmes de regroupement deviennent simples. 🚀
Questions Fréquemment Posées
La leçon « Regrouper et classer avec une table de correspondance » est-elle gratuite ?
Oui — le texte complet de « Regrouper et classer avec une table de correspondance » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Regrouper et classer avec une table de correspondance » ?
Regrouper les anagrammes et les éléments similaires Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Regrouper et classer avec une table de correspondance » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Ensembles pour l’appartenance et la déduplication
- Dictionnaires comme tables de consultation
- Counter et defaultdict en action
- Regrouper et classer avec une table de correspondance