Rencontre #33: Arrays, Hachage et Piles

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.

Introduction au Hachage (Hashing)

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.

• Pourquoi utiliser le hachage ? Le hachage est utile lorsqu’on a besoin d’accéder fréquemment à des données en temps constant (O(1)), par exemple pour vérifier si un élément est présent dans un ensemble, compter les occurrences d’éléments, ou créer des associations rapides entre clés et valeurs.

• 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

Introduction aux Piles (Stacks)

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.

• Pourquoi utiliser les piles ? Les piles sont utiles pour des opérations qui nécessitent une gestion de l’ordre, comme l’évaluation d’expressions (utilisation des parenthèses), le backtracking (revenir en arrière dans des algorithmes de recherche), et la gestion des appels récursifs.

• 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)

Problèmes

Le nombre à côté de chaque problème indique son niveau de difficulté selon Kattis.

1. “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.

   • “Missing Number” Easy — Problème similaire sur Leetcode.

2. “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.

   • “Top K Frequent Elements” Medium — Problème similaire sur Leetcode.

3. “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.

   • “Contains Duplicate” Easy — Problème plus facile sur LeetCode.

4. “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.

   • “ Design Front Middle Back Queue” Medium — Problème similaire on LeetCode.

5. “Baby Names” 5.6 — Gérez une liste de prénoms avec insertion, suppression et recherche efficaces..

   • “Find Median From Data Stream” Hard — Problème Similaire du LeetCode