bisect ** Algorithme de dichotomie de séquence **
bisect_left(a, x, lo=0, hi=len(a))
Renvoie la position où $ x $ peut être inséré dans $ a $ pour la liste triée $ a $. Si $ a $ contient $ x $, le point d'insertion sera avant (à gauche) toute valeur $ x $ existante.
bisect_right(a, x, lo=0, hi=len(a)) Similaire à bisect_left (), mais si $ a $ contient $ x $, le point d'insertion sera après (à droite) toute valeur $ x $ existante.
from bisect import bisect_left, bisect_right
a = [1, 2, 2, 2, 3, 5]
print(bisect_left(a, 2)) # -> 1
print(bisect_right(a, 2)) # -> 4
** Exemple de problème **
heapq ** Algorithme de file d'attente de tas / Algorithme de file d'attente prioritaire **
Poussez l'élément vers le tas.
Renvoie le plus petit élément du tas.
from heapq import heappop, heappush
a = []
heappush(a, (10, 'x'))
heappush(a, (5, 'y'))
heappush(a, (1, 'z'))
print(a) # -> [(1, 'z'), (10, 'x'), (5, 'y')]
print(heappop(a)) # -> (1, 'z')
print(heappop(a)) # -> (5, 'y')
print(heappop(a)) # -> (10, 'x')
collections ** Type de données du conteneur **
deque Un conteneur de type liste qui peut effectuer des ajouts et des pop à grande vitesse aux deux extrémités. appendleft () et poplift () peuvent être réalisés plus rapidement que les opérations équivalentes sur list.
from collections import deque
q = deque(['a', 'b', 'b', 'b', 'd', 'd'])
print(q.popleft()) # -> a
print(q) # -> deque(['b', 'b', 'b', 'd', 'd'])
q.appendleft('z')
print(q) # -> deque(['z', 'b', 'b', 'b', 'd', 'd'])
Une sous-classe du dictionnaire qui compte les objets hachables. Pour compter le nombre d'un élément, vous pouvez utiliser la méthode count () de la liste ou du tuple, mais c'est pratique pour compter le nombre de tous les éléments.
from collections import Counter
l = ['a', 'b', 'b', 'b', 'd', 'd']
t = ('a', 'b', 'b', 'b', 'd', 'd',)
print(l.count('b')) # -> 3
print(t.count('b')) # -> 3
c = Counter(l)
print(c) # -> Counter({'b': 3, 'd': 2, 'a': 1})
#Renvoie tous les éléments dans l'ordre décroissant du nombre
print(c.most_common()) # -> [('b', 3), ('d', 2), ('a', 1)]
itertools ** Fonction de génération d'itérateur pour une exécution de boucle efficace **
Renvoie le produit direct de plusieurs itérables.
from itertools import product
l = ['a', 'b', 'c']
m = ['x', 'y']
print(list(product(l, m)))
# -> [('a', 'x'), ('a', 'y'), ('b', 'x'), ('b', 'y'), ('c', 'x'), ('c', 'y')]
Renvoie une séquence de longueur r à partir de l'élément de iterable.
from itertools import permutations
l = ['a', 'b', 'c']
print(list(permutations(l, 3)))
# -> [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
print(list(permutations(l, 2)))
# -> [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
combinations(iterable, r) Renvoie la combinaison lors de la sélection de r parmi les éléments de iterable.
from itertools import combinations
l = ['a', 'b', 'c', 'd', 'e']
print(list(combinations(l, 2)))
# -> [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('b', 'c'), ('b', 'd'), ('b', 'e'), ('c', 'd'), ('c', 'e'), ('d', 'e')]
** Exemple de problème ** ABC123 A Five Antennas Code
functools ** Manipulation des fonctions d'ordre supérieur et des objets appelables **
lru_cache(maxsize, typed) Un décorateur qui enveloppe une fonction dans un objet appelable pour mémorandum. Économisez jusqu'à la taille maximale des appels récents. Il peut être utilisé dans la conversion de mémo.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2);
print(fib(100)) # -> 354224848179261915075
print(fib.cache_info()) # -> CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)
reduce(function, iterable[, initializer])
Les éléments itérables sont appliqués de manière cumulative de la gauche à une fonction qui prend deux arguments, et le résultat est renvoyé.
from functools import reduce
def f(a, b):
return a * b
l = [1, 2, 3, 4, 5]
# ((((1 * 2) * 3) * 4) * 5)Équivalent à
print(reduce(f, l)) # -> 120
fractions ** Nombre raisonnable **
gcd(a, b) Renvoie l'engagement maximum des entiers $ a $ et $ b $.
Si vous voulez trouver le multiple commun minimum, implémentez lcm comme suit.
from fractions import gcd
def lcm(a, b):
return a*b // gcd(a, b)
** Exemple de problème ** ABC070 C Multiple Clocks Code
Présentation de fonctions intégrées pouvant être utilisées par les professionnels de la compétition.
pow() ** Puissance **
$ pow (x, y [, z]) $ renvoie le reste de $ z $ pour $ x \ ^ y $ ou $ x \ ^ y $. En utilisant ceci, l'élément inverse de $ a $ dans $ mod $$ p $ peut être obtenu par $ pow (a, p-2, p) $.
Il peut être utilisé pour trouver le reste de $ p $, qui est le nombre de combinaisons pour sélectionner $ k $ à partir de $ n $.
def nCk(n, k, p):
ret = 1
for i in range(k):
ret = ret * (n - i) * pow(i + 1, p - 2, p) % p
return ret
** Exemple de problème ** Itinéraire ABC034 C Code