La partie sur la structure de données de conseils à connaître lors de la programmation de la compétition avec Python2 a été divisée.
La version Python est ** 2.7.5 ** (En Python3, les spécifications telles que l'entrée et la sortie sont très différentes, il est donc recommandé de se référer à d'autres articles).
int
Type entier.
À proprement parler, les entiers Python incluent le type entier int et le type entier long long.
Pour cette raison, vous ne devez pas trop vous inquiéter.
print int('10') # 10
J'aime ce domaine car il est très concis.
La conversion Radix d'entiers se produit fréquemment dans les ordinateurs de processus.
@ n_knuu6 m'a appris.
En utilisant format (), il est possible de convertir un nombre décimal en une chaîne de caractères exprimée en 2/8/16.
#Nombre binaire
b = format(10, 'b') # '1010'
#8 base
o = format(10, 'o') # '12'
#Hexadécimal(Minuscule)
x = format(10, 'x') # 'a'
#Hexadécimal(lettre majuscule)
X = format(10, 'X') # 'A'
Inversement, si vous voulez convertir une chaîne de caractères de base 2/8/16 en un nombre décimal, spécifiez la base de la chaîne de caractères d'origine dans le deuxième argument de ʻint () `.
d1 = int('1010', 2) # 10
d2 = int('12', 8) # 10
d3 = int('a', 16) # 10
d4 = int('A', 16) # 10
Je l'écrirai un jour.
float
Type à virgule flottante.
print float('10.00') # 10.0
Les points suivants sont souvent dépendants des relations en virgule flottante.
#Le reste de la division est tronqué
a = 5 / 2 # 2
Si le résultat de la division entre entiers est une valeur non entière, le résultat est tronqué (Python 3 semble résoudre ce problème).
Si vous voulez représenter correctement la division entre les entiers,
a1 = 5 * 1.0 / 2 # 2.5
a2 = 5. / 2 # 2.5
a3 = float(5) / 2 # 2.5
Comme indiqué dans, la molécule ou le dénominateur doit être de type flottant.
Infinity, souvent utilisé dans la programmation compétitive.
Bien sûr, il est possible de définir une valeur entière très grande telle que 10000000000 comme infini, mais cela peut provoquer des bogues inattendus tels que la possibilité de dépasser la valeur définie en fonction de la valeur d'entrée.
En Python, float ('inf') peut représenter l'infini.
p_inf = float('inf') #Infini positif
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') #Infini négatif
print n_inf < -10000000000 # True
print float('inf') - float('inf') # nan
print float('inf') / float('inf') # nan
print float('inf') * 0 # nan
Notez que la valeur devient nan (indéfinie) lorsque la soustraction ou la division est effectuée entre les infinis ou lorsque l'infini est multiplié par 0 comme décrit ci-dessus.
str
Type de chaîne de caractères. Comme avec Java, sachez que vous ne pouvez pas modifier la chaîne de caractères (réaffectez-la aux éléments qui composent la chaîne de caractères).
Je l'utilise très souvent (mais oublie vite).
s = 'abc'
reverse = s[::-1] # 'cba'
Ceci est également souvent utilisé.
s = 'abc'
l = list(s) # ['a', 'b', 'c']
ns = ''.join(l) # 'abc'
ns2 = ','.join(l) # 'a,b,c'
#Au fait, str(l)N'est pas une opération inverse
bad = str(l) # "['a', 'b', 'c']"
Dans la programmation de compétition, les codes ASCII sont souvent obtenus à partir de caractères (le célèbre est le code César).
c = 'a'
print ord('a') # 97
#Erreur si vous ajoutez une chaîne de caractères de 2 caractères ou plus ou un caractère qui ne peut pas être représenté par un code ASCII à l'argument
print ord('ab') # TypeError
list
Les soi-disant tableaux (à proprement parler, Python a également un module de tableau, donc c'est une erreur, mais à moins que vous n'ayez besoin de beaucoup d'accélération, utilisez une liste). Il existe différentes fonctions.
5. Structure des données - Documentation Python 2.7ja1
Liste-Créer, Extraire, Remplacer, Ajouter, Rechercher, Supprimer, Nombre d'éléments-Hikimemo
Les bases sont écrites sur la page ci-dessus, elles sont donc omises.
Si le nombre d'éléments est petit, vous pouvez le remplacer tel quel, mais par exemple en C ++
int a[100][100];
Que faire avec quelque chose comme ça.
Il existe une initialisation par notation d'inclusion de liste et une initialisation par \ *.
#Les deux sont des listes avec 100 0 consécutifs([0, 0, ..., 0])Vers la variable l
l = [0 for i in range(100)] #Initialisation à l'aide de la notation d'inclusion de liste
l = [0] * 100 # *Initialisation avec
Au fait, en comparant le temps d'exécution en utilisant% timeit of ipython,
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
Par conséquent, il a été constaté que l'initialisation à l'aide de * est plus rapide.
Ici, pour générer une liste bidimensionnelle de 10 \ * 10,
l = [[0] * 10] * 10
Est faux. Si vous utilisez \ * pour une liste, la référence de la liste sera copiée, donc
l = [[0] * 10] * 10
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [1, 0, 0, ..., 0],
# ...
# [1, 0, 0, ..., 0]]
Comme indiqué, le changement se propage à d'autres parties. C'est un endroit plutôt addictif.
Correctement,
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]]
Ou
l = [[0 for j in range(10)] for i in range(10)]
Laisser. La même chose s'applique à 3 dimensions et plus.
Quand j'ai pris une référence de temps d'exécution pour cela aussi,
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
Il s'est avéré qu'il semble préférable d'utiliser \ * là où il peut être utilisé.
5. Structure des données - Documentation Python 2.7ja1
Notation spécifique à Python pour le calcul sur des listes.
Il semble que le coût d'apprentissage soit un peu élevé pour la spécification du langage Python, mais je pense que cela vaut la peine de s'en souvenir car il permet des expressions simples et puissantes.
Comme mentionné dans l'exemple ci-dessus, il doit être utilisé à la place de map () et filter ().
l = range(5) # [0, 1, 2, 3, 4]
x = [2 * e for e in l if e >= 3] #Extraire seulement 3 éléments ou plus de l(filter)， Renvoie un ensemble de doublés sous forme de liste(map)
print x # [6, 8]
Applicable également aux listes multidimensionnelles.
l = [[0] * 10 for i in range(10)]
x = [[e + 1 for e in l[i]] for i in range(len(l))] #Ajouter 1 à tous les éléments de la liste
print l
# [[1, 1, ..., 1],
# [1, 1, ..., 1],
# ...
# [1, 1, ..., 1]]
Vous pouvez également écrire une courte boucle for. En général, la notation d'inclusion de liste est plus rapide.
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)]
#Le code ci-dessus peut être écrit sur une seule ligne
print [(i, j) for i in range(10) for j in range(10)]
L'imbrication est possible comme indiqué ci-dessous, mais elle n'est pas recommandée car elle est souvent compliquée.
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] #Parmi les éléments de l, seuls 3 ou plus sont retirés, et seuls ceux supérieurs à 7 sont renvoyés sous forme de liste pour l'ensemble des éléments doublés.
print x # [8]
Il existe une fonction non destructive sorted () et une méthode destructive sort ().
«Sorted ()» et «sort ()» sont triés par défaut par ordre croissant, mais peuvent être modifiés en ordre décroissant en passant «reverse = True» comme argument.
Si l'élément à trier est une chaîne de caractères, il est trié par ordre lexical.
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]
Si chaque élément de la liste est un tapple, par défaut, le 0ème élément de chaque élément est trié, puis le 1er élément est trié pour la même valeur, et ainsi de suite.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
En donnant key =" expression lambda " à l'argument, le tri en spécifiant la clé est également possible.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
#Pour l2, les deux suivants sont équivalents
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)]
#Triez par ordre décroissant pour le deuxième élément et triez par ordre croissant pour le premier élément s'ils ont la même valeur.
print sorted(l2, key=lambda x: (-x[1], x[0]) # [('fuga', 3), ('piyo', 2), ('fuga', 1), ('hoge', 1)]
Je l'écrirai un jour.
En Python, l'objet liste agit comme une pile et une file d'attente.
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]
** Addenda: ** Merci à @wonderful_panda.
8.3. Collections - Types de données de conteneurs hautes performances - Documentation Python 2.7ja1
ʻAppend () et pop () sont $ O (1) $, mais pop (0) `est une opération de $ O (n) $, donc si le nombre d'éléments dans la liste augmente, il faudra du temps pour diminuer. Ce sera comme ça.
Lorsque vous utilisez des files d'attente (stack,), vous pouvez utiliser collections.deque en toute sécurité.
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])
Implémentation de l'algorithme Dyxtra en Python - Ne le dis pas!
Indication prioritaire (repère prioritaire) qui est prise en charge dans la programmation de la compétition.
J'ai déjà écrit un article sur mon blog, alors veuillez vous y référer.