Syntaxe Python :
- Python ne supporte pas nativement les piles, on utilise généralement une liste pour simuler une pile. Les opérations courantes sont : append(), pop().
Cliquez pour voir le code``` pile = []
Empiler (push)
pile.append(1)
Décacher (pop)
element_superieur = pile.pop()
Accéder à l'élément supérieur (peek)
element_superieur = pile[-1]
Vérifier si la pile est vide
est_vide = len(pile) == 0 non pile
2. Structures de données courantes en Python (listes, dictionnaires, ensembles, tuples) et modules utiles
- Listes [] : append(v), insert(idx,v), extend([]) | remove(v), pop(/idx), del list[idx], clear()
Cliquez pour voir le code```
# append() ajoute un élément à la fin de la liste.
ma_liste = [1, 2, 3]
ma_liste.append(4)
print(ma_liste) # Affiche : [1, 2, 3, 4]
# insert() insère un élément à une position spécifique.
ma_liste = [1, 2, 3]
ma_liste.insert(1, 4) # Insère 4 à l'index 1
print(ma_liste) # Affiche : [1, 4, 2, 3]
# extend() ajoute tous les éléments d'une autre liste à la fin de la liste courante.
ma_liste = [1, 2, 3]
ma_liste.extend([4, 5])
print(ma_liste) # Affiche : [1, 2, 3, 4, 5]
# remove() supprime le premier élément correspondant. Si l'élément n'existe pas, lève une erreur ValueError.
ma_liste = [1, 2, 3, 2, 4]
ma_liste.remove(2)
print(ma_liste) # Affiche : [1, 3, 2, 4]
# pop() supprime et renvoie l'élément à une position spécifique. Sans indice, supprime le dernier élément.
ma_liste = [1, 2, 3]
element_pop = ma_liste.pop()
print(element_pop) # Affiche : 3
print(ma_liste) # Affiche : [1, 2]
element_pop = ma_liste.pop(0)
print(element_pop) # Affiche : 1
print(ma_liste) # Affiche : [2]
# del supprime un élément à une position spécifique ou supprime toute la liste.
ma_liste = [1, 2, 3]
del ma_liste[1]
print(ma_liste) # Affiche : [1, 3]
del ma_liste # Supprime toute la liste
# print(ma_liste) # Cette ligne provoquera une erreur car ma_liste a été supprimée
# clear() vide la liste.
ma_liste = [1, 2, 3]
ma_liste.clear()
print(ma_liste) # Affiche : []
- Dictionnaires {} : dict['xx']=4
- Ensembles {} : add(), remove()
- Tuples () : immuables ?
- Structure de données高级'deque' (double file), pop(), popleft() (tous les éléments vides)
Cliquez pour voir le code``` from collections import deque
ma_deque = deque([1, 2, 3, 4, 5]) ma_deque.append(6) # Affiche : deque([1, 2, 3, 4, 5, 6]) ma_deque.appendleft(0) # Affiche : deque([0, 1, 2, 3, 4, 5, 6]) ma_deque.pop() # Affiche : deque([0, 1, 2, 3, 4, 5]) ma_deque.popleft() # Affiche : deque([1, 2, 3, 4, 5])
- Dictionnaire utilisé pour compter les éléments 'Counter'
Cliquez pour voir le code```
from collections import Counter
mon_compteur = Counter(['a', 'b', 'c', 'a', 'b', 'a'])
print(mon_compteur) # Affiche : Counter({'a': 3, 'b': 2, 'c': 1})
print(mon_compteur.most_common(2)) # Affiche : [('a', 3), ('b', 2)]
232. File à l'aide de piles
Problème : Veuillez utiliser uniquement deux piles pour implémenter une file FIFO. La file doit prendre en charge toutes les opérations que supporte une file classique (push, pop, peek, empty) : Implémenter la classe MyQueue : void push(int x) Met un élément x à la fin de la file int pop() Supprime et renvoie l'élément au début de la file int peek() Renvoie l'élément au début de la file boolean empty() Si la file est vide, renvoie true ; sinon, renvoie false
Solution :
Clés :
- Python ne supporte pas les piles, utilisez deux listes pour simuler les piles et utilisez uniquement les opérations pop et append
- Lors du push des données, placez simplement les données dans la pile d'entrée. Lors du pop, le processus est plus complexe : si la pile de sortie est vide, transférez tous les éléments de la pile d'entrée dans la pile de sortie (remarquez que c'est tous les éléments), puis pop() depuis la pile de sortie. Si la pile de sortie n'est pas vide, pop() depuis la pile de sortie directement
- peek utilise la méthode pop pour obtenir le premier élément de la file et le remet dans la pile de sortie pour conserver l'état de la file, puis renvoie l'élément
Cliquez pour voir le code``` class MyQueue:
def __init__(self):
self.pile_in = []
self.pile_out = []
def push(self, x: int) -> None:
self.pile_in.append(x)
def pop(self) -> int:
if self.pile_out:
return self.pile_out.pop()
else:
for i in range(len(self.pile_in)):
self.pile_out.append(self.pile_in.pop())
return self.pile_out.pop()
def peek(self) -> int:
ans = self.pop()
self.pile_out.append(ans)
return ans
def empty(self) -> bool:
return not (self.pile_in or self.pile_out)
**225. Pile à l'aide de files**
Problème : Veuillez utiliser uniquement deux files pour implémenter une pile LIFO (Last In, First Out) et prendre en charge toutes les opérations standard d'une pile (push, top, pop et empty).
Implémenter la classe MyStack :
void push(int x) Met un élément x en haut de la pile.
int pop() Supprime et renvoie l'élément au sommet de la pile.
int top() Renvoie l'élément au sommet de la pile.
boolean empty() Si la pile est vide, renvoie true ; sinon, renvoie false.
**Solution :**
Clés :
1. Utilisez un deque (double file) pour simuler une pile, un seul deque est suffisant
2. Lors du pop(), il faut transférer tous les éléments, sauf le dernier, de la file en tête à la fin de la file, puis supprimer le premier élément pour obtenir l'élément de pile à supprimer
Cliquez pour voir le code```
class MyStack:
def __init__(self):
self.fichier = deque()
def push(self, x: int) -> None:
self.fichier.append(x)
def pop(self) -> int:
for i in range(len(self.fichier) - 1):
self.fichier.append(self.fichier.popleft())
return self.fichier.popleft()
def top(self) -> int:
ans = self.pop()
self.fichier.append(ans)
return ans
def empty(self) -> bool:
return not self.fichier
20. Parenthèses valides
Problème : Donnez une chaîne de caractères composée uniquement de '(', ')', '{', '}', '[' et ']', déterminez si la chaîne est valide. Une chaîne est considérée comme valide si : Les parenthèses ouvrantes doivent être fermées par des parenthèses fermantes de même type. Les parenthèses ouvrantes doivent être fermées dans l'ordre inverse de leur apparition. Chaque parenthèse fermante doit avoir un correspondant de même type.
Solution :
Idée : La structure de pile est idéale pour ce type de problème de correspondance symétrique. Clés :
- Si la longueur de la chaîne est impaire, la chaîne est automatiquement invalide
- Si les types de parenthèses ne correspondent pas, la chaîne est invalide
- Si les parenthèses fermantes apparaissent trop tôt (pas de correspondant ouvert), la chaîne est invalide
Cliquez pour voir le code``` class Sloution: def isValid(self, s: str) -> bool: if len(s) % 2 != 0: # Taille impaire return False pile = [] for char in s: if char == '(': pile.append(')') elif char == '[': pile.append(']') elif char == '{': pile.append('}') elif not pile or pile[-1] != char: return False else: pile.pop() if pile: return False else: return True
**1047. Suppression des paires adjacentes**
Problème : Étant donné une chaîne de caractères composée de lettres minuscules, une opération de suppression consiste à choisir deux lettres identiques adjacentes et à les supprimer.
Effectuez cette opération de suppression de manière répétée jusqu'à ce qu'il soit impossible d'en effectuer une de plus. Renvoie la chaîne finale après toutes les suppressions. Le résultat est garanti d'être unique.
**Solution :**
Idée : Les paires adjacentes identiques correspondent à un problème de correspondance symétrique, qui peut être résolu efficacement avec une pile
Cliquez pour voir le code```
class Solution:
def removeDuplicates(self, s: str) -> str:
pile = []
for char in s:
if pile and pile[-1] == char:
pile.pop()
else:
pile.append(char)
return ''.join(pile)
Conclusion :
En Python, les piles sont essentiellement des listes. Les opérations courantes sont append(), pop() et pile[-1]. Pour l'itération sur les chaînes de caractères, utilisez : for char in s: