The part about the data structure of tips you should know when programming competitive programming with Python2 has been divided.
The Python version is ** 2.7.5 ** (Python3 has very different specifications such as input / output, so it is recommended to refer to other articles).
int
Integer type.
Strictly speaking, Python integers include integer type int and long integer type long.
For that reason, you don't have to worry too much.
print int('10') # 10
I like this area because it's very concise.
Radix conversion of integers frequently occurs in process computers.
@ n_knuu6 taught me.
By using format (), it is possible to convert from a decimal number to a character string expressed in 2/8/16.
#Binary number
b = format(10, 'b') # '1010'
#8 base
o = format(10, 'o') # '12'
#Hexadecimal(Lowercase)
x = format(10, 'x') # 'a'
#Hexadecimal(uppercase letter)
X = format(10, 'X') # 'A'
On the contrary, if you want to convert a character string expressed in 2/8/16 decimal number to a decimal number, specify the radix of the original character string in the second argument of ʻint () `.
d1 = int('1010', 2) # 10
d2 = int('12', 8) # 10
d3 = int('a', 16) # 10
d4 = int('A', 16) # 10
I will write it someday.
float
Floating point type.
print float('10.00') # 10.0
The following points are often addicted to floating point relationships.
#The remainder of the division is truncated
a = 5 / 2 # 2
If the result of division between integers is a non-integer value, the result is truncated (Python 3 seems to solve this problem).
If you want to correctly represent the division between integers,
a1 = 5 * 1.0 / 2 # 2.5
a2 = 5. / 2 # 2.5
a3 = float(5) / 2 # 2.5
As shown in, either the numerator or denominator should be a float type.
Infinity, often used in competitive programming.
Of course, it is possible to set a very large integer value such as 10000000000 as infinity, but depending on the input value, it may exceed the set value, which causes an unexpected bug.
In Python, float ('inf') can represent infinity.
p_inf = float('inf') #Positive infinity
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 infinity
print n_inf < -10000000000 # True
print float('inf') - float('inf') # nan
print float('inf') / float('inf') # nan
print float('inf') * 0 # nan
Note that the value becomes nan (indefinite) when subtracting or dividing between infinities or multiplying infinity by 0 as described above.
str
Character string type. Note that you cannot change the character string (reassign it to the elements that make up the character string) as in Java.
I use it very often (but forget it soon).
s = 'abc'
reverse = s[::-1] # 'cba'
This is also often used.
s = 'abc'
l = list(s) # ['a', 'b', 'c']
ns = ''.join(l) # 'abc'
ns2 = ','.join(l) # 'a,b,c'
#By the way, str(l)Is not an inverse operation
bad = str(l) # "['a', 'b', 'c']"
In competitive programming, ASCII codes are often obtained from characters (the famous one is Caesar cipher).
c = 'a'
print ord('a') # 97
#Error if you add a character string of 2 or more characters or a character that cannot be represented by ASCII code to the argument
print ord('ab') # TypeError
list
So-called arrays (strictly speaking, Python also has an array module, so it's a mistake, but unless you need a lot of speedup, use a list). There are various functions.
5. Data Structures — Python 2.7ja1 documentation
List-Create, Extract, Replace, Add, Search, Delete, Number of Elements-Memo
The basics are written on the above page, so they are omitted.
If the number of elements is small, you can substitute it as it is, but for example, in C ++
int a[100][100];
What to do with something like that.
There are initialization by list comprehension notation and initialization by \ *.
#Both are lists with 100 consecutive 0s([0, 0, ..., 0])To the variable l
l = [0 for i in range(100)] #Initialization using list comprehension notation
l = [0] * 100 # *Initialization using
By the way, when comparing the execution time using% 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
Therefore, it was found that the initialization using * is faster.
Here, in order to generate a two-dimensional list of 10 \ * 10,
l = [[0] * 10] * 10
Is wrong. If you use \ * for a list, the list reference will be copied, so
l = [[0] * 10] * 10
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [1, 0, 0, ..., 0],
# ...
# [1, 0, 0, ..., 0]]
As shown, the change spreads to other parts. This is a rather addictive place.
Correctly,
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]]
Or
l = [[0 for j in range(10)] for i in range(10)]
Let. The same applies to 3D and above.
When I benchmarked the execution time for this as well,
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
It turned out that it seems better to use \ * where it can be used.
5. Data Structures — Python 2.7ja1 documentation
A unique Python notation for operating on lists.
It seems that the learning cost is a little high for the Python language specification, but I think it's worth remembering because it allows simple and powerful expressions.
As mentioned in the above example, it should be used instead of map () and filter ().
l = range(5) # [0, 1, 2, 3, 4]
x = [2 * e for e in l if e >= 3] #Extract only 3 or more elements of l(filter)， Returns a set of doubles it as a list(map)
print x # [6, 8]
Also applicable to multidimensional lists.
l = [[0] * 10 for i in range(10)]
x = [[e + 1 for e in l[i]] for i in range(len(l))] #Add 1 to all elements of the list
print l
# [[1, 1, ..., 1],
# [1, 1, ..., 1],
# ...
# [1, 1, ..., 1]]
You can also write a short for loop. List comprehensions are generally faster.
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)]
#The above code can be written in one line
print [(i, j) for i in range(10) for j in range(10)]
Nesting is possible as shown below, but it is not recommended because it is often complicated.
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] #Of the elements of l, only 3 or more are taken out, and only those larger than 7 are returned as a list for the set of doubled elements.
print x # [8]
There is a non-destructive sorted () function and a destructive sort () method.
Both sorted () and sort () are sorted in ascending order by default, but can be changed to descending order by passing reverse = True as an argument.
If the element to be sorted is a character string, it will be sorted in lexicographic order.
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]
If each element of the list is a tuple, by default, the 0th element of each element is sorted, and then the 1st element is sorted for the same value, and so on.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
Sorting by specifying a key is also possible by giving key =" lambda expression " as an argument.
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
#For l2, the following two are equivalent
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)]
#The second element is sorted in descending order, and those with the same value are sorted in ascending order for the first element.
print sorted(l2, key=lambda x: (-x[1], x[0]) # [('fuga', 3), ('piyo', 2), ('fuga', 1), ('hoge', 1)]
I will write it someday.
In Python, the list object acts as a stack and queue.
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]
** Addendum: ** Thank you to @wonderful_panda.
8.3. collections — High Performance Container Data Types — Python 2.7ja1 documentation
ʻAppend ()andpop ()are $ O (1) $, butpop (0)` is an operation of $ O (n) $, so if the number of elements in the list increases, it will take time to deque. It will be like this.
When using (stack,) queues, it is safe to use collections.deque.
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])
Implemented Dijkstra's algorithm in Python-Don't call it futu!
Priority queue (priority queue) that is taken care of in competitive programming.
I wrote an article on my blog before, so please refer to that.
Recommended Posts