Der Teil über die Datenstruktur von Tipps, die Sie beim Programmieren von Wettbewerben mit Python2 kennen sollten wurde geteilt.
Die Python-Version ist ** 2.7.5 ** (In Python3 unterscheiden sich Spezifikationen wie Eingabe und Ausgabe erheblich, daher wird empfohlen, auf andere Artikel zu verweisen).
int
Ganzzahliger Typ.
Genau genommen umfassen Python-Ganzzahlen den Integer-Typ int und den Long-Integer-Typ long.
Aus diesem Grund müssen Sie sich nicht zu viele Sorgen machen.
print int('10') # 10
Ich mag diesen Bereich, weil er sehr prägnant ist.
In Prozesscomputern tritt häufig eine Radix-Konvertierung von Ganzzahlen auf.
@ n_knuu6 hat mich unterrichtet.
Mit format () ist es möglich, von einer Dezimalzahl in eine Zeichenfolge zu konvertieren, die am 08.02.16 ausgedrückt wird.
#Binärzahl
b = format(10, 'b') # '1010'
#8 Basis
o = format(10, 'o') # '12'
#Hexadezimal(Kleinbuchstaben)
x = format(10, 'x') # 'a'
#Hexadezimal(Großbuchstabe)
X = format(10, 'X') # 'A'
Wenn Sie dagegen eine Basiszeichenfolge vom 08.02.16 in eine Dezimalzahl konvertieren möchten, geben Sie die Basis der ursprünglichen Zeichenfolge im zweiten Argument von "int ()" an.
d1 = int('1010', 2) # 10
d2 = int('12', 8) # 10
d3 = int('a', 16) # 10
d4 = int('A', 16) # 10
Ich werde es eines Tages schreiben.
float
Gleitkomma-Typ.
print float('10.00') # 10.0
Die folgenden Punkte sind häufig abhängig von Gleitkomma-Beziehungen.
#Der Rest der Teilung wird abgeschnitten
a = 5 / 2 # 2
Wenn das Ergebnis der Division zwischen Ganzzahlen ein nicht ganzzahliger Wert ist, wird das Ergebnis abgeschnitten (Python 3 scheint dieses Problem zu lösen).
Wenn Sie die Division zwischen ganzen Zahlen korrekt darstellen möchten,
a1 = 5 * 1.0 / 2 # 2.5
a2 = 5. / 2 # 2.5
a3 = float(5) / 2 # 2.5
Wie in gezeigt, sollte entweder das Molekül oder der Nenner ein Float-Typ sein.
Unendlichkeit, oft in der Wettbewerbsprogrammierung verwendet.
Natürlich ist es möglich, einen sehr großen ganzzahligen Wert wie 10000000000 als unendlich festzulegen, aber es kann unerwartete Fehler verursachen, z. B. die Möglichkeit, den eingestellten Wert abhängig vom Eingabewert zu überschreiten.
In Python kann float (inf) unendlich darstellen.
p_inf = float('inf') #Positive Unendlichkeit
print p_inf > 10000000000 # True
print p_inf + 10000000000 # inf
print p_inf - 10000000000 # inf
print min(10000000000, float('inf')) # 10000000000
n_inf = -float('inf') #Negative Unendlichkeit
print n_inf < -10000000000 # True
print float('inf') - float('inf') # nan
print float('inf') / float('inf') # nan
print float('inf') * 0 # nan
Es ist zu beachten, dass der Wert nan (unbestimmt) wird, wenn eine Subtraktion oder Division zwischen Unendlichkeiten durchgeführt wird oder wenn die Unendlichkeit wie oben beschrieben mit 0 multipliziert wird.
str
Zeichenkettentyp. Beachten Sie wie bei Java, dass Sie die Zeichenfolge nicht ändern können (weisen Sie sie den Elementen zu, aus denen die Zeichenfolge besteht).
Ich benutze es sehr oft (aber vergiss es bald).
s = 'abc'
reverse = s[::-1] # 'cba'
Dies wird auch oft verwendet.
s = 'abc'
l = list(s) # ['a', 'b', 'c']
ns = ''.join(l) # 'abc'
ns2 = ','.join(l) # 'a,b,c'
#Übrigens str(l)Ist keine inverse Operation
bad = str(l) # "['a', 'b', 'c']"
In der Wettbewerbsprogrammierung werden ASCII-Codes häufig aus Zeichen erhalten (der berühmte ist der Caesar-Code).
c = 'a'
print ord('a') # 97
#Fehler, wenn Sie dem Argument eine Zeichenfolge mit 2 oder mehr Zeichen oder ein Zeichen hinzufügen, das nicht durch ASCII-Code dargestellt werden kann
print ord('ab') # TypeError
list
Sogenannte Arrays (genau genommen hat Python auch ein Array-Modul, es ist also ein Fehler, aber wenn Sie nicht viel Geschwindigkeit benötigen, verwenden Sie eine Liste). Es gibt verschiedene Funktionen.
5. Datenstruktur - Python 2.7ja1-Dokumentation
Liste erstellen, extrahieren, ersetzen, hinzufügen, suchen, löschen, Anzahl der Elemente-Hikimemo
Die Grundlagen sind auf der obigen Seite beschrieben und werden daher weggelassen.
Wenn die Anzahl der Elemente gering ist, können Sie sie unverändert ersetzen, beispielsweise in C ++
int a[100][100];
Was tun mit so etwas?
Es gibt eine Initialisierung durch Listeneinschlussnotation und eine Initialisierung durch \ *.
#Beide sind Listen mit 100 aufeinanderfolgenden Nullen([0, 0, ..., 0])Zur Variablen l
l = [0 for i in range(100)] #Initialisierung mit Listeneinschlussnotation
l = [0] * 100 # *Initialisierung mit
Übrigens, wenn Sie die Ausführungszeit mit% timeit von ipython vergleichen,
In [45]: %timeit [0] * 1000000
100 loops, best of 3: 6.66 ms per loop
In [46]: %timeit [0 for i in range(1000000)]
10 loops, best of 3: 65.1 ms per loop
Daher wurde festgestellt, dass die Initialisierung mit * schneller ist.
Um hier eine zweidimensionale Liste von 10 \ * 10 zu erzeugen,
l = [[0] * 10] * 10
Ist falsch. Wenn Sie \ * für eine Liste verwenden, wird die Listenreferenz kopiert
l = [[0] * 10] * 10
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [1, 0, 0, ..., 0],
# ...
# [1, 0, 0, ..., 0]]
Wie gezeigt, erstreckt sich die Änderung auf andere Teile. Dies ist ein ziemlich süchtig machender Ort.
Korrekt,
l = [[0] * 10 for i in range(10)]
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [0, 0, 0, ..., 0],
# ...
# [0, 0, 0, ..., 0]]
Oder
l = [[0 for j in range(10)] for i in range(10)]
Lassen. Gleiches gilt für 3 Dimensionen und höher.
Als ich auch dafür einen Benchmark der Ausführungszeit nahm,
In [40]: %timeit [[0] * 1000 for i in range(1000)]
100 loops, best of 3: 7.04 ms per loop
In [42]: %timeit [[0 for j in range(1000)] for i in range(1000)]
10 loops, best of 3: 48 ms per loop
Es stellte sich heraus, dass es besser scheint, \ * dort zu verwenden, wo es verwendet werden kann.
5. Datenstruktur - Python 2.7ja1-Dokumentation
Python-spezifische Notation für die Berechnung auf Listen.
Es scheint, dass die Lernkosten für die Python-Sprachspezifikation etwas hoch sind, aber ich denke, es lohnt sich, sich daran zu erinnern, weil es einfache und leistungsstarke Ausdrücke ermöglicht.
Wie im obigen Beispiel erwähnt, sollte es anstelle von "map ()" und "filter ()" verwendet werden.
l = range(5) # [0, 1, 2, 3, 4]
x = [2 * e for e in l if e >= 3] #Extrahieren Sie nur 3 oder mehr Elemente von l(filter)， Gibt eine Reihe von doppelten als Liste zurück(map)
print x # [6, 8]
Gilt auch für mehrdimensionale Listen.
l = [[0] * 10 for i in range(10)]
x = [[e + 1 for e in l[i]] for i in range(len(l))] #Fügen Sie allen Elementen der Liste 1 hinzu
print l
# [[1, 1, ..., 1],
# [1, 1, ..., 1],
# ...
# [1, 1, ..., 1]]
Sie können auch eine kurze for-Schleife schreiben. Im Allgemeinen ist die Listeneinschlussnotation schneller.
l = []
for i in range(10):
for j in range(10):
l.append((i, j))
print l
# [(0, 0),
# (0, 1),
# (0, 2),
# ...
# (9, 8),
# (9, 9)]
#Der obige Code kann in einer Zeile geschrieben werden
print [(i, j) for i in range(10) for j in range(10)]
Das Verschachteln ist wie unten gezeigt möglich, wird jedoch nicht empfohlen, da es häufig kompliziert ist.
l = range(5) # [0, 1, 2, 3, 4]
x = [e for e in [2 * e for e in l if e >= 3] if e > 7] #Von den Elementen von l werden nur 3 oder mehr herausgenommen, und nur diejenigen, die größer als 7 sind, werden als Liste für die Menge der doppelten Elemente zurückgegeben.
print x # [8]
Es gibt eine zerstörungsfreie sorted () Funktion und eine destruktivesort ()Methode.
Sowohl "sortiert ()" als auch "sort ()" werden standardmäßig in aufsteigender Reihenfolge sortiert, können jedoch in absteigende Reihenfolge geändert werden, indem "reverse = True" als Argument übergeben wird.
Wenn das zu sortierende Element eine Zeichenfolge ist, wird es in lexikalischer Reihenfolge sortiert.
l = [5, 1, 3, 4, 2]
print sorted(l) # [1, 2, 3, 4, 5]
print l # [5, 1, 3, 4, 2]
print l.sort() # None
print l # [1, 2, 3, 4, 5]
l.sort(reverse=True)
print l # [5, 4, 3, 2, 1]
Wenn jedes Element der Liste ein Tapple ist, wird standardmäßig das 0. Element jedes Elements sortiert, und dann wird das 1. Element nach demselben Wert sortiert, und so weiter.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
Indem Sie dem Argument "key =" Lambda-Ausdruck "" geben, ist auch eine Sortierung durch Angabe des Schlüssels möglich.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
#Für l2 sind die folgenden zwei äquivalent
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
print sorted(l2, key=lambda x: (x[0], x[1])) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
#Sortieren Sie für das zweite Element in absteigender Reihenfolge und für das erste Element in aufsteigender Reihenfolge, wenn sie denselben Wert haben.
print sorted(l2, key=lambda x: (-x[1], x[0]) # [('fuga', 3), ('piyo', 2), ('fuga', 1), ('hoge', 1)]
Ich werde es eines Tages schreiben.
In Python fungiert das Listenobjekt als Stapel und Warteschlange.
l = [0, 1, 2, 3]
# push/enque
l.append(4)
print l # [0, 1, 2, 3, 4]
# pop
x = l.pop() # 4
print l # [0, 1, 2, 3]
# deque
y = l.pop(0) # 0
print l # [1, 2, 3]
** Nachtrag: ** Vielen Dank an @wonderful_panda.
8.3. Sammlungen - Hochleistungscontainer-Datentyp - Python 2.7ja1-Dokumentation
append () und pop () sind $ O (1) $, aber pop (0) ist eine Operation von $ O (n) $. Wenn also die Anzahl der Elemente in der Liste zunimmt, dauert es einige Zeit, bis sie entfernt werden. Es wird so sein.
Bei Verwendung von (Stapel-) Warteschlangen ist die Verwendung von collection.deque sicher.
from collections import deque
l = [0, 1, 2, 3]
q = deque(l)
# push/enque
q.append(4)
print q # deque([0, 1, 2, 3, 4])
# pop
x = q.pop() # 4
print q # deque([0, 1, 2, 3])
# deque
y = q.popleft() # 0
print q # deque([1, 2, 3])
Implementierte den Dyxtra-Algorithmus in Python - Sag es nicht!
Priority Cue (Priority Cue), der in der Wettbewerbsprogrammierung berücksichtigt wird.
Ich habe bereits einen Artikel in meinem Blog geschrieben.
Recommended Posts