a-z
ascii_lowercase #"abcdefghijklmnopqrstuvwxyz"
ord('a') # 97
ord('b') # 98
chr(97) # a
chr(98) # b
"str123".isalnum() # check a-z, 0-9
"123".isdigit() # check 0-9
String
"hello".index("hel") # 0
"hello".index("world") # exception substring not found
"hello".find("hel") # 0
"hello".find("world") # -1
"123".zfill(5) # 00123
Bit
(5).bit_length() # 3
(8).bit_length() # 4
(5).bit_count() # 2
(8).bit_count() # 1
- lowbit 找到最右邊的1
x & -x
# x = 101110
# -x = 010010 (2's complement)
# -----------
000010
- 將最右邊的0改為1
x & (x + 1)
# 1011
# 1100
# ----
# 1111
- 消掉最右邊的1
x & (x - 1)
# 111 110
# & 110 & 101
# ----- -----
# 110 100
Iterator
pairwise
for x, y in pairwise("abbcccc"):
print(x, y)
"""
a b
b b
b c
c c
c c
c c
"""
zip
la = ['a1', 'a2', 'a3']
lb = ['b1', 'b2', 'b3']
lc = ['c1', 'c2', 'c3']
for a, b, c in zip(la, lb, lc):
print(a, b, c)
"""
a1 b1 c1
a2 b2 c2
a3 b3 c3
"""
permutations
nums = [3,4,1]
permutations(nums)
"""
(3, 4, 1)
(3, 1, 4)
(4, 3, 1)
(4, 1, 3)
(1, 3, 4)
(1, 4, 3)
"""
Search
bisect
arr = [1, 2, 3, 3, 3, 5, 6]
print(bisect_left(arr, 3)) # 2
print(bisect_right(arr, 3)) # 5
arr = [1, 2, 3, 5, 6]
print(bisect_left(arr, 4)) # 3
print(bisect_right(arr, 4)) # 3
Sort
list.sort()
list.sort(reverse=True)
sorted([3, 2]) # [2, 3]
t = [('a', 5), ('e', 1),('c', 3), ('b', 2)]
t.sort(key=lambda c: c[1])
for i in t:
print(i)
# ('e', 1)
# ('b', 2)
# ('c', 3)
# ('a', 5)
def cmp(a, b):
return a.bit_length() - b.bit_length()
nums.sort(key=cmp_to_key(cmp))
排序字串
s = "54321"
sorted(s) # ['1', '2', '3', '4', '5']
''.join(sorted(s)) # '12345'
Data Structure
List
a = [1, 2, 3, 4, 5]
a[::-1] # [5, 4, 3, 2, 1]
b = [1, 2, 3]
b.extend([4, 5, 6])
b # [1, 2, 3, 4, 5, 6]
2d Array
# M * N
matrix = [[0] * N for _ in range(M)]
Queue
q = deque([1,2,3])
q.append(4) # deque([1, 2, 3, 4])
v = q.popleft() # v = 1, q = deque([2, 3, 4])
q.clear()
Dict
graph = defaultdict(list) # key不存在時用空list作為預設值
edges = [[1, 2], [0, 2], [0, 1], [3, 4]]
for [n1, n2] in edges:
graph[n1].append(n2)
# defaultdict(<class 'list'>, {1: [2], 0: [2, 1], 3: [4]})
cnt = defaultdict(SortedSet) # defaultdict(SortedList)
cnt['1'].add(3)
cnt['1'].add(2)
cnt['1'].add(1)
# {'1': SortedSet([1, 2, 3])}
Counter
cnt = Counter()
s = "aaabbcc"
for c in s:
cnt[c] += 1
# Counter({'a': 3, 'b': 2, 'c': 2})
for k, v in cnt.items():
print(k, v)
# a 3
# b 2
# c 2
s = "aaaabbb"
s.count('a') # 4
nums = [1,1,2,2,3,4,2,3]
cnt = Counter(nums)
cnt.most_common() # [(2, 3), (1, 2), (3, 2), (4, 1)]
Heap
arr = []
heapq.heapify(arr)
heapq.heappush(arr, 7) # push
heapq.heappop(arr) # pop
# Max Heap
class MaxHeap:
def __init__(self):
self.data = []
def top(self):
return -self.data[0]
def push(self, val):
heapq.heappush(self.data, -val)
def pop(self):
return -heapq.heappop(self.data)
Math
a = [1, 2, 3, 4, 5]
list(accumulate(a)) # [1, 3, 6, 10, 15]
nums = [3,2,1,5]
numsOr = reduce(ior, nums) # 7
Templates
Primes質數
PRIMES = []
for i in range(2, 1001):
for j in range(2, i):
if not i % j:
break
else:
PRIMES.append(i)
def sieve(self, upper_limit):
isPrime = [True] * (upper_limit + 1)
isPrime[0] = isPrime[1] = False
for n in range(2, int(upper_limit ** 0.5) + 1):
if isPrime[n]:
for mul in range(n * n, upper_limit + 1, n):
isPrime[mul] = False
return isPrime
Combination組合數
MOD = 10**9 + 7
MX = 10**5
# fac[i] = i!
fac = [0] * MX
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i - 1] * i % MOD
# inv_f[i] = 1/i!
inv_f = [0] * MX
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
inv_f[i - 1] = inv_f[i] * i % MOD
# n取m
def comb(n: int, m: int) -> int:
return fac[n] * inv_f[m] * inv_f[n - m] % MOD if 0 <= m <= n else 0
預先計算階層
fac = [factorial(i) for i in range(n + 1)]
Union Find
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x != y:
if self.size[x] < self.size[y]:
self.parent[x] = y
self.size[y] += self.size[x]
else:
self.parent[y] = x
self.size[x] += self.size[y]