Lors de cette rencontre, nous poursuivrons notre exploration des problèmes liés aux arrays en introduisant deux concepts fondamentaux en programmation compétitive : le hachage et les piles. Ces outils puissants vous permettront de résoudre une variété de problèmes plus efficacement, en manipulant et en organisant les données d’une manière qui simplifie les calculs et améliore les performances. Nous explorerons les bases de ces structures, leur utilité, et comment les utiliser dans des contextes pratiques à l’aide de Python.
Le hachage est une technique utilisée pour stocker et rechercher des données de manière très efficace. En utilisant une fonction de hachage, nous pouvons convertir une entrée (comme une chaîne de caractères ou un nombre) en un index dans une table de hachage, ce qui permet un accès rapide aux données.
Classes et méthodes Python utiles pour le hachage :
Dictionnaires (dict) : En Python, un dictionnaire est une implémentation directe de la table de hachage. Vous pouvez l’utiliser pour stocker des paires clé-valeur.
d = {} # Créer un dictionnaire vide
d["apple"] = 3 # Ajouter une clé "apple" avec la valeur 3
print(d.get("apple", 0)) # Accéder à la valeur associée à "apple"
Ensembles (set) : Utilisez les ensembles pour stocker des éléments uniques et effectuer des opérations comme l’union, l’intersection, et la différence.
s = set() # Créer un ensemble vide
s.add(1) # Ajouter l’élément 1 à l’ensemble
print(1 in s) # Vérifier si 1 est dans l’ensemble
Une pile (stack) est une structure de données qui suit le principe "Last In, First Out" (LIFO), c’est-à-dire que le dernier élément ajouté est le premier à être retiré. Imaginez une pile d’assiettes où vous ne pouvez retirer que celle du dessus.
Classes et méthodes Python utiles pour les piles :
Listes (list) : En Python, vous pouvez utiliser une liste comme pile en utilisant les méthodes append() pour ajouter un élément et pop() pour retirer le dernier élément.
stack = [] # Créer une pile vide
stack.append(1) # Ajouter 1 à la pile
stack.append(2) # Ajouter 2 à la pile
print(stack.pop()) # Retirer le dernier élément (2) et l’afficher
Module collections.deque : Pour une pile plus performante, utilisez deque du module collections, qui est optimisé pour les ajouts et retraits aux extrémités.
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
print(stack.pop()) # Retirer et afficher le dernier élément (2)
Le nombre à côté de chaque problème indique son niveau de difficulté selon Kattis.
“Odd Gnome” 1.6 — Trouvez le roi dans chaque groupe de gnomes en identifiant l’unique gnome qui ne respecte pas l’ordre strictement croissant de leurs identifiants.
“Conformity” 1.7 — Calculez le nombre d’étudiants ayant choisi la combinaison de cours la plus populaire parmi toutes les combinaisons sélectionnées par les étudiants.
“Deduplicating Files” 3.8 — Identifiez les fichiers en double en utilisant une fonction de hachage pour détecter les doublons potentiels et réduire le nombre de comparaisons directes entre fichiers.
“Teque” 4.3 — Gérez une nouvelle structure de données appelée "teque" qui permet d’insérer des éléments à l’avant, à l’arrière ou au milieu, et d’accéder rapidement aux éléments par index.
“Baby Names” 5.6 — Gérez une liste de prénoms avec insertion, suppression et recherche efficaces..