bisect ** Sequenzdichotomie-Algorithmus **
bisect_left(a, x, lo=0, hi=len(a))
Gibt die Position zurück, an der $ x $ für die sortierte Liste $ a $ in $ a $ eingefügt werden kann. Wenn $ a $ $ x $ enthält, befindet sich die Einfügemarke vor (links) einem vorhandenen $ x $ -Wert.
bisect_right(a, x, lo=0, hi=len(a)) Ähnlich wie bei bisect_left (), aber wenn $ a $ $ x $ enthält, befindet sich die Einfügemarke nach (rechts) einem vorhandenen $ x $ -Wert.
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
** Problembeispiel **
heapq ** Heap Queue-Algorithmus / Priority Queue-Algorithmus **
Schieben Sie den Gegenstand auf den Haufen.
Gibt das kleinste Element vom Heap zurück.
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 ** Container-Datentyp **
deque Ein listenartiger Container, der an beiden Enden mit hoher Geschwindigkeit Anhängen und Popup ausführen kann. appendleft () und poplift () können schneller als gleichwertige Operationen auf der Liste erreicht werden.
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'])
Eine Unterklasse des Wörterbuchs, die hashbare Objekte zählt. Sie können die count () -Methode von list oder tuple verwenden, um die Anzahl eines Elements zu zählen. Dies ist jedoch praktisch, wenn Sie die Anzahl aller Elemente zählen.
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})
#Gibt alle Elemente in absteigender Reihenfolge zurück
print(c.most_common()) # -> [('b', 3), ('d', 2), ('a', 1)]
itertools ** Iterator-Generierungsfunktion für eine effiziente Schleifenausführung **
Gibt das direkte Produkt mehrerer Iterables zurück.
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')]
Gibt eine Folge der Länge r aus dem Element iterable zurück.
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) Gibt die Kombination zurück, wenn r aus den Elementen von iterable ausgewählt wird.
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')]
** Problembeispiel ** ABC123 A Five Antennas Code
functools ** Manipulieren von Funktionen höherer Ordnung und aufrufbaren Objekten **
lru_cache(maxsize, typed) Ein Dekorateur, der eine Funktion in ein aufrufbares Objekt für ein Memorandum einschließt. Speichern Sie bis zur maximalen Größe der letzten Anrufe. Es kann bei der Wiederholung von Gedenkstätten verwendet werden.
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])
Iterierbare Elemente werden kumulativ von links auf eine Funktion angewendet, die zwei Argumente akzeptiert, und das Ergebnis wird zurückgegeben.
from functools import reduce
def f(a, b):
return a * b
l = [1, 2, 3, 4, 5]
# ((((1 * 2) * 3) * 4) * 5)Gleichwertig
print(reduce(f, l)) # -> 120
fractions ** Angemessene Anzahl **
gcd(a, b) Gibt die maximale Verpflichtung der Ganzzahlen $ a $ und $ b $ zurück.
Wenn Sie das minimale gemeinsame Vielfache ermitteln möchten, implementieren Sie lcm wie folgt.
from fractions import gcd
def lcm(a, b):
return a*b // gcd(a, b)
** Problembeispiel ** ABC070 C Multiple Clocks Code
Einführung integrierter Funktionen, die bei Wettkampfprofis eingesetzt werden können.
pow() ** Leistung **
$ pow (x, y [, z]) $ gibt den Rest von $ z $ für $ x \ ^ y $ oder $ x \ ^ y $ zurück. Auf diese Weise kann das inverse Element von $ a $ in $ mod $$ p $ durch $ pow (a, p-2, p) $ erhalten werden.
Es kann verwendet werden, um den Rest von $ p $ zu ermitteln. Dies ist die Anzahl der Kombinationen, mit denen $ k $ aus $ n $ ausgewählt werden kann.
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
** Problembeispiel ** ABC034 C-Route Code
Recommended Posts