Reconnaître le bon pattern
IntermédiaireFace à un énoncé, repérez les signaux : ils désignent le pattern qui débloque le problème.
| Signal dans l'énoncé | Pattern | Idée clé |
|---|---|---|
| « Trouve deux éléments dont la somme vaut… », doublons, fréquences, « as-tu déjà vu… » | Hashmap | Stocker ce qu'on a vu pour répondre en O(1) au lieu de rescanner |
| Tableau ou chaîne triés, palindrome, paire à trouver, partition sur place | Two pointers | Deux indices qui convergent (ou avancent à des vitesses différentes) en O(n) |
| Sous-tableau ou sous-chaîne contigu, « plus long / plus court / maximum de taille k » | Sliding window | Fenêtre [gauche, droite] qu'on étend et rétrécit avec un état incrémental |
| Données triées, « premier index tel que… », minimiser un maximum | Recherche binaire | Diviser l'espace de recherche par deux, sur un tableau ou sur la réponse |
| Cycle dans une liste, milieu, inversion, fusion de listes | Listes chaînées | Pointeurs lent/rapide, nœud sentinelle, réécriture soigneuse des liens |
| Parenthèses bien formées, « prochain plus grand », annuler/refaire | Pile | Le dernier ouvert est le premier fermé ; pile monotone |
| Parcours par niveaux, plus court chemin sans poids | File (BFS) | Traiter dans l'ordre d'arrivée |
| Arbre, hiérarchie, profondeur, chemin, plus proche ancêtre commun | Arbres / BST | DFS récursif (diviser pour régner) ou BFS par niveaux |
| « Génère toutes les combinaisons / permutations / sous-ensembles » | Backtracking | Choisir, explorer, annuler ; élaguer les branches impossibles |
| « Les k plus grands / fréquents / proches », médiane en flux, fusion de k listes | Heap | Heap de taille k pour garder les meilleurs candidats en O(n log k) |
| Réseau, grille, dépendances, composantes connexes, ordre des cours | Graphes | BFS pour le plus court chemin, DFS pour explorer, tri topologique pour les dépendances |
| Plus court chemin avec poids positifs | Dijkstra | Heap qui extrait toujours le sommet le plus proche |
| « Nombre de façons », minimum/maximum avec sous-problèmes répétés | Programmation dynamique | Définir l'état et la transition, mémoïser ou remplir un tableau |
| Intervalles à fusionner, planification, « le choix local suffit » | Glouton / intervalles | Trier d'abord, décider localement, prouver que le glouton est correct |
Astuce : bloqué entre deux patterns ? Donnez d'abord la brute force et sa complexité, puis demandez-vous ce qu'elle recalcule inutilement : la réponse désigne généralement le bon pattern.