Taiyi dev

Notes

Python

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

Bit

(5).bit_length() # 3
(8).bit_length() # 4

(5).bit_count() # 2
(8).bit_count() # 1

x & -x

#  x = 101110
# -x = 010010 (2's complement)
# -----------
       000010

x & (x + 1)

# 1011
# 1100
# ----
# 1111

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))

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)

埃式篩(Sieve of Eratosthenes)

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
;