Manipulations courantes

Chaînes de caractères

# Conversion ASCII
ord('A')   # 65
chr(65)    # 'A'

# Nettoyage
s = "  hello\t\n"
s.strip()          # "hello"
s.lstrip()         # "hello\t\n"
s.rstrip()         # "  hello"

# Tests et transformations
"abc".isalpha()    # True
"123".isnumeric()  # True
"HELLO".lower()    # "hello"

# Jointure
seq = ("a", "b", "c")
"-".join(seq)      # "a-b-c"

# Comptage
from collections import Counter
c = Counter("bcabc")
# Counter({'b': 2, 'c': 2, 'a': 1})

# Split
"pomme,banane,orange".split(",")      # ['pomme', 'banane', 'orange']
"pomme,banane,orange".split(",", 2)   # ['pomme', 'banane,orange']

# Inversion
texte = "ABCDEFG"
texte[::-1]                          # "GFEDCBA"
''.join(reversed(texte))             # "GFEDCBA"

Listes (tableaux)

donnees = [1, 2, 3, 4, 5]

# all / any
all(x <= 5 for x in donnees)   # True
any(x == 5 for x in donnees)   # True

# Tri
liste = [2, 1, 3]
sorted(liste)                   # [1, 2, 3]

# Ensemble (set)
elements = set([1, 2, 3, 3])
elements.add(100)
liste_unique = list(elements)   # [1, 2, 3, 100]

# Index
valeurs = [1, 2, 3, 4, 5]
valeurs.index(max(valeurs))     # 4

# Enumerate
saisons = ['Print', 'Été', 'Automne', 'Hiver']
for i, nom in enumerate(saisons, start=1):
    print(i, nom)

# Copie et tranches
original = [1, 2, 3, 4, 5]
copie = original.copy()          # copie profonde
tranche1 = original[1:3]         # [2, 3]
tranche2 = original[:3]          # [1, 2, 3]
tranche3 = original[3:]          # [4, 5]
tranche4 = original[-3:]         # [3, 4, 5]

# Inversion sur place
liste_inv = [1, 2, 3, 4]
liste_inv.reverse()

Dictionnaires

note = {'Maths': 95}
note['Français'] = 89          # ajout
note['Français'] = 100         # modification
del note['Maths']              # suppression

# Récupération des clés/valeurs
d = {"Alice": "20", "Bob": "18"}
list(d)                       # ['Alice', 'Bob']
list(d.values())              # ['20', '18']

Maths, ASCII, Regex

import math
math.sqrt(9)   # 3.0

# Codes ASCII : 48-57 chiffres, 65-90 majuscules, 97-122 minuscules

import re
re.sub(r'\d+', 'X', 'abc123def')   # 'abcXdef'

Fonctions lambda, map, filter, reduce

carre = lambda x: x ** 2
list(map(carre, [1, 2, 3]))               # [1, 4, 9]
list(map(lambda x: x ** 2, [1, 2, 3]))    # [1, 4, 9]
list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4]))  # [2, 4]

from functools import reduce
reduce(lambda x, y: x * y, [1, 2, 3, 4, 5])  # 120

Divers

# Conversion liste de str -> int
strs = ["1", "2", "3"]
ints = [int(x) for x in strs]

# Opérateur morse (walrus)
if (n := len("hello")) > 3:
    print(n)   # affiche 5

# Range
list(range(10))        # [0..9]
list(range(1, 11))     # [1..10]
list(range(0, 30, 5))  # [0, 5, 10, 15, 20, 25]

# global / nonlocal
def externe():
    x = 0
    def interne():
        nonlocal x
        x += 1
    interne()
    return x

# Cache decorator
from functools import cache
@cache
def factorielle(n):
    return 1 if n <= 1 else n * factorielle(n-1)

Algorithmes classiques

Algorithme glouton (greedy)

Choisir localement la meilleure option en espérant obtenir un optimum global.

Pile (stack) et file (queue)

pile = []                        # création
pile.append('a')                 # push
dernier = pile.pop()             # pop
sommet = pile[-1]                # lecture sans retrait

from collections import deque
file = deque()
file.append('a')                 # queue droite
file.appendleft('b')             # queue gauche
premier = file.popleft()         # pop gauche
dernier = file.pop()             # pop droite
file.extend([1,2])               # ajout multiples à droite
file.clear()

Tas (heap)

import heapq
tas = []
for x in [18, 1, 20, 10, 5, 200]:
    heapq.heappush(tas, x)
# tas = [1, 5, 20, 18, 10, 200]

# Max‑heap : stocker les opposés
tas_max = []
for x in [18, 1, 20, 10, 5, 200]:
    heapq.heappush(tas_max, -x)
max_val = -heapq.heappop(tas_max)

# Transformation en place
liste = [18, 1, 20, 10, 5, 200]
heapq.heapify(liste)

heapq.heappushpop(tas, 1)   # push puis pop min

Double pointeur

Utiliser deux indices (gauche/droite ou lent/rapide) pour parcourir une structure linéaire.

Fenêtre glissante (sliding window)

1. Initialiser gauche = droit = 0.
2. Augmenter droit jusqu'à satisfaire la condition.
3. Réduire gauche jusqu'à ne plus satisfaire la condition.
4. Répéter jusqu'à la fin de la séquence.

Table de hachage (hash map / set)

# Ensemble (hash set)
ens = set()
ens.add(3)
ens.remove(2)
if 2 not in ens: print("absent")
ens.clear()

# Dictionnaire (hash map)
d = {}
d['a'] = 1
valeur = d.get('a', 0)
del d['b']
for cle in d: ...
cles = d.keys()
d.clear()

Liste chaînée

class Noeud:
    def __init__(self, val=0, suivant=None):
        self.val = val
        self.suivant = suivant

# Nœud factice (dummy)
tete = Noeud(0, premier_noeud)

Arbre

Parcours en profondeur (DFS) – récursif

def dfs(racine):
    if racine is None: return
    resultat.append(racine.val)
    dfs(racine.gauche)
    dfs(racine.droite)

# Avec profondeur
def dfs_prof(noeud, prof):
    if noeud is None: return prof-1
    chemin.append((noeud.val, prof))
    dfs_prof(noeud.gauche, prof+1)
    dfs_prof(noeud.droite, prof+1)

Parcours en largeur (BFS) – file

def bfs(racine):
    if racine is None: return []
    q = deque([racine])
    parcours = []
    while q:
        n = q.popleft()
        parcours.append(n.val)
        if n.gauche: q.append(n.gauche)
        if n.droite: q.append(n.droite)
    return parcours

Union‑Find (disjoint sets)

Structure permettent de gérer des ensembles disjoints et d'effectuer des opérations d'union et de recherche.

Graphe

Stockage

• Matrice d'adjacence : con[i][j] = True si arête i→j.
• Liste d'adjacence : graphe[nœud] = [voisins].

DFS – itératif avec pile

def dfs_graphe(graphe, depart):
    pile = [depart]
    visite = {depart}
    while pile:
        n = pile.pop()
        # traiter n
        for voisin in reversed(graphe[n]):
            if voisin not in visite:
                pile.append(voisin)
                visite.add(voisin)

BFS – avec file

def bfs_graphe(graphe, depart):
    file = deque([depart])
    visite = {depart}
    while file:
        n = file.popleft()
        # traiter n
        for voisin in graphe[n]:
            if voisin not in visite:
                file.append(voisin)
                visite.add(voisin)

Tri toploogique

• BFS (Kahn) : calculer degré entrant, mettre les nœuds de degré 0 dans une file, puis réduire les degrés.
• DFS : visiter les nœuds non visités, marquer « en cours », détecter les cycles, puis empiler pour obtenir l'ordre inverse.

Programmasion dynamique

# Tableau 1D
dp = [0] * taille

# Exemple classique : Fibonacci
@cache
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Concepts utiles

Ordre lexicographique

Comparaison caractère par caractère. Si une chaîne est préfixe d'une autre, la plus longue est considérée plus grande. Exemple : "abc" < "acb" < "acbd".