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

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

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

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

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

Others

Primes

PRIMES = []
for i in range(2, 1001):
  for j in range(2, i):
    if not i % j:
      break
  else:
      PRIMES.append(i)
;