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
Digit
digit_sum = sum(map(int, str(x)))
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)
"""
Binary 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))
tasks.sort(
key=lambda num: (
-(num[1] - num[0]), # 差值大的排前面
-num[1] # 差值相同時，第二個數大的排前面
)
)
排序字串
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]
copy list
copy_row = matrix[r][::]
stacks = [[0, 1], [2], [], []]
sorted(chain.from_iterable(stacks)) # [0, 1, 2]
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
st = {1,2,3}
st.clear()
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
模板
Primes質數
PRIMES = []
for i in range(2, 1001):
for j in range(2, i):
if not i % j:
break
else:
PRIMES.append(i)
def isPrime(n: int) -> bool:
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return n >= 2
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
質因數分解
MX = 10**6 + 1
PRIME_FACTORS = [[] for _ in range(MX)]
for i in range(2, MX):
if not PRIME_FACTORS[i]:
for j in range(i, MX, i):
PRIME_FACTORS[j].append(i)
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
- math.comb(n, k)
預先計算階層
fac = [factorial(i) for i in range(n + 1)]
矩陣運算
MOD = 10**9 + 7
# 矩陣乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)]
for row in a]
# a^n @ f0 (@: 矩陣乘法)
def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
res = f0
while n:
if n & 1:
res = mul(a, res)
a = mul(a, a)
n >>= 1
return res
Rotate matrix 90 degree clockwise
mat = [list(x) for x in zip(*mat[::-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]
最常公共子序列 (Longest Increasing Subsequence, LIS)
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
g = []
for x in nums:
j = bisect_left(g, x)
if j == len(g):
g.append(x)
else:
g[j] = x
return len(g)
t在s中的不同子序列的個數
def numDistinct(self, s: str, t: str) -> int:
@cache
def dfs(i, j):
if i < j: # 不合法
return 0
if j < 0: # 找到一種方案
return 1
res = dfs(i-1, j)
if s[i] == t[j]:
res += dfs(i-1, j-1)
return res
return dfs(len(s)-1, len(t)-1)