差分

例如給一個陣列 nums = [[3,6],[1,5],[4,7]], 包含多組[start, end]需要累加在範圍內的值。 可以使用到差分的特性，可以從原本brute force需要$O(n^2)$時間降為$O(n)$。

nums = [1, 2, 3, 4, 5]
diff = [1, 1, 1, 1, 1]
# 如果要針對[nums[1], nums[3]]範圍內加1
# 可以對diff做操作，最後再用累加方式還原
# 對diff的start(nums[1])做+1, 對end+1(nums[3+1])做-1
diff = [1, 2, 1, 1, 0]
# 再做累加還原成原本想要的操作
acc = [1, 3, 4, 5, 5]

# brute force: O(n^2)
for i in range(len(nums)):
  for k in range(start, end + 1):
    if start <= i <= end:
      nums[i] += 1

相關題目: 3355. Zero Array Transformation I

Graph

Dijkstra

• 解決問題: 從0到n-1的最短路徑
• 步驟
  1. 將原點加到minheap中
  2. 每次從minheap中拿出cost最小的節點A
  3. 將節點A可接觸到的節點B, C, D...分別計算新的cost後(cost + new edge weight)，放回minheap中
  4. 當到達n-1節點後返回cost

def dijkstra():
  heap = [(0, 0, 0)] # cost, row, col
  visited = set()

  while heap:
    cost, r, c = heapq.heappop(heap)

    # reach end
    if r = ROW - 1 and c = COL - 1:
      return cost

    if (r, c) in visited:
      continue

    # logic
    heapq.headpush(heap, (newCost, r, c))

    # add to visited
    visited.add((r, c))

• Dijkstra algorithm | Single source shortest path algorithm - YouTube
• 相關題目: 2290, 2577

Euler

• Euler path: 每一個邊都走恰好一次
  • 所有節點的indegree都是偶數，除了起點和終點
  • 起點特性: outdegree[i] - indegree[i] = 1
  • 終點特性: indegree[i] - outdegree[i] = 1
• Euler circuit: 每一個邊都走恰好一次，且起始點與終點相同
  • 所有節點的indegree都是偶數
• Hierholzer's algorithm
  1. build adj, indegree, outdegree

  adj = defaultdict(list)
  indegree = defaultdict(int)
  outdegree = defaultdict(int)
  
  for u, v in pairs:
    adj[u].append(v)
    indegree[v] += 1
    outdegree[u] += 1
  

  2. find start node
  • 如果 outdegree[i] - indegree[i] == 1 只能由i作為start node
  • 其他任何outdegree > 0都可以作為start node

  startNode = None
  for node in outdegree:
    if outdegree[node] - indegree[node] == 1:
      startNode = node
      break
    if outdegree[node] > 0:
      startNode = node
  

  3. 使用dfs建立eulerian path(順序會是反的)
  • 從start node i開始，outdegree[i] -= 1，找到相鄰node adj[i][outdegree[i]]
  • 遇到outdegree[i]為0時，將i加入到eulerian path

  eulerian_path = []
  def dfs(node, eulerian_path):
    while outdegree[node] > 0:
      outdegree[node] -= 1
      nextNode = adj[node][outdegree[node]]
      dfs(nextNode, eulerian_path)
    eulerian_path.append(node)
  
  dfs(startNode, eulerian_path)
  

  • 相關題目: 2097

字串比對

問題: 在一個字串(s)中搜尋子字串(pattern)

Brute force: O(n * m)

n: 字串s長度
m: 子字串pattern長度

KMP

解決問題: 用O(n + m)的時間複雜度，在一個字串中搜尋一個子字串
參考: 最浅显易懂的 KMP 算法讲解

def build_next(pattern):
  next = [0]
  prefix_len = 0
  i = 1
  while i < len(pattern):
    if pattern[prefix_len] == pattern[i]:
      prefix_len += 1
      next.append(prefix_len)
      i += 1
    else:
      if prefix_len == 0:
        next.append(0)
        i += 1
      prefix_len = next[prefix_len - 1]
  return next

def kmp(s, pattern):
  next = build_next(pattern)
  i = 0
  j = 0
  while i < len(s):
    if s[i] == pattern[j]:
      i += 1
      j += 1
    elif j > 0:
      j = next[j - 1]
    else:
      i += 1
    if j == len(pattern):
      return i - j
  return -1

return kmp("sadbutsad", "sad")

相關題目: 28