0%

huahua的模板

发表于 更新于 分类于 阅读次数：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

2020年2月12日 下午12:49

注：来源于公众号：huahualeetcode

二分模板：

1
2
3
4
5
6
7
8
9
10
11
12
# Author: Huahua
# Returns the smallest m in [l, r),
# s.t. cond(m) == True
# If not found returns r.
def binary_search(l, r, cond)
  while l < r:
    m = l + (r - l) // 2
    if cond(m):
      r = m
    else
      l = m + 1
  return l

排列模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Author: Huahua
def P(n, m, cur, used):
  if len(cur) == m:
    print(cur)
    return
  for i in range(n):
    if used[i]: continue
    used[i] = True
    cur.append(i + 1)
    P(n, m, cur, used)
    cur.pop()
    used[i] = False

n = 5
m = 3
P(n, m, [], [False] * n)

组合模板

1
2
3
4
5
6
7
8
9
10
11
12
13
# Author: Huahua
def C(n, m, s, cur):
  if len(cur) == m:
    print(cur)
    return
  for i in range(s, n):
    cur.append(i + 1)
    C(n, m, i + 1, cur)
    cur.pop()    

n = 5
m = 3
C(n, m, 0, [])

BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Author: Huahua
# Find the shortest path from |start| to |target| in a unweighted graph G.
# neighbor(x) returns the neighbors of x in G.

q = deque([start])
seen = set([start])
steps = 0

while q:
  size = len(q)
  for _ in range(size):
    n = q.popleft()
    if n == target: return steps
    for t in neighbor(n):
      if t in seen: continue
      q.append(t)
      seen.add(t)
  steps += 1
return -1 # not found

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Author: Huahua
# Check whether there is a path from |start| to |target| in graph G.
# neighbor(x) returns the neighbors of x in G.

seen = set([start])
def dfs(n):
  if n == target:
    return True  
  for t in neighbor(n):
    if t in seen: continue
    seen.add(t)
    if dfs(t): return True
    seen.remove(t) # back-tracking  
  return False
return dfs(start)

前缀树模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Author: Huahua
class Trie(object):
  def __init__(self): self.root = {}

  def insert(self, word):
    p = self.root
    for c in word:
      if c not in p: p[c] = {}
      p = p[c]
    p['#'] = True    

  def search(self, word):
    node = self._find(word)
    return node and '#' in node
    
  def startsWith(self, prefix):
    return self._find(prefix)

  def _find(self, prefix):
    p = self.root
    for c in prefix:
      if c not in p: return None
      p = p[c]
    return p

并查集模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Author: Huahua
class UnionFindSet:
  def __init__(self, n):
    self.p = [i for i in range(n + 1)]
    self.r = [1 for i in range(n + 1)]

  def find(self, u):
    while u != self.p[u]:
      self.p[u] = self.p[self.p[u]]
      u = self.p[u]
    return u

  def union(self, u, v):
    pu, pv = self.find(u), self.find(v)
    if pu == pv: return False    
    if self.r[pu] < self.r[pv]:
      self.p[pu] = pv
    elif self.r[pu] > self.r[pv]:
      self.p[pv] = pu
    else:        
      self.p[pv] = pu
      self.r[pu] += 1
    return True

记忆化递归模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Author: Huahua
# dp(state) returns the minimal cost to solve the subproblem |s|.
def dp(s):
  # No solution
  if unsolvable(s): return float('inf')
  # Base case, easy to solve.
  if base_case(s): return cost(s)
  # Already solved
  if s in memo: return memo[s]
  best = float('inf')
  for t in subproblems(s):   
    best = min(best, cost(s, t) + dp(t))
  memo[s] = best
  return best
return dp(start)