最近公共祖先 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class LCA: def __init__(self, edges: List[List[int]]): n = len(edges) + 1 m = n.bit_length() g = [[] for _ in range(n)] for

并查集 1 2 3 4 5 6 7 8 9 10 11 12 def find(x): if f[x]!=x: f[x] = find(f[x]) return f[x] def union(x,y): fx, fy = find(x),find(y) if fx != fy: if sz[fx]>sz[fy]: fx, fy = fy, fx f[fx] = fy sz[fy] += sz[fx]

1 质因数分解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ma = def get_primes(M): f = [1]*M for i in range(2,isqrt(M)+1): if f[i]: f[i*i:M:i] = [0] * ((M-1-i*i)//i+1) return [i for i in range(2,M) if f[i]] primes = get_primes(isqrt(ma)+1) @cache def factor(x): ct = Counter() for p in primes: while x%p==0: x//=p ct[p]

下一个排列 1 2 3 4 5 6 7 8 9 10 11 12 13 def nxt(A): n = len(A) i = n-2 while i >= 0 and A[i] >= A[i+1]: i -= 1 if i < 0: return [] j = n-1 while A[j] <= A[i]: j -= 1 A[i], A[j] = A[j], A[i] A[i+1:] = A[i+1:][::-1] return A

计算器 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def cal(s: str) -> int: func = {'+':int.__add__,'-':int.__sub__,'*':int.__mul__,'/':lambda x,y:x//y} pro = dict(zip('+-*/(','11223')) sk,ops = [],[] for x,op in re.findall('(\d+)|([-+*/()])',s+'+'): if x: sk.append(int(x)) elif op=='(': ops.append(op) elif op==')': while ops[-1] != '(': b,a = sk.pop(),sk.pop() sk.append(func[ops.pop()](a,b)) ops.pop() else: while ops and pro[ops[-1]]<=pro[op]: b,a = sk.pop(),sk.pop() sk.append(func[ops.pop()](a,b)) ops.append(op) return

反转链表 1 2 3 4 5 6 7 8 def reverse(head): tail = head while tail and tail.next: tmp = tail.next tail.next = tmp.next tmp.next = head head = tmp return head

遍历子集 1 2 3 4 y = st # 生成 st 的所有子集 while y: # 处理子集 y y = (y-1)&st Gosper’s Hack 算法学习笔记(75): Gosper’s Hack 1 2 3 4 5 6 7 8 st,ma = (1<<k)-1, 1<<n # 生成 n 元集合所有 k 元子

后缀数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 def SA(A): def SA_IS(A): def equal(pos1,

一般字典树 哈希表 1 2 3 4 T = lambda: defaultdict(T) trie = T() for w in words: reduce(dict.__getitem__, w, trie)['#'] = w 数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Trie: def __init__(self,n,L,k): # 插入 n 个长为 L 的字符串，