演算法與資料結構模板:Python 版
依據原始文章的主題架構,以 Python 重新設計與撰寫。說明文字、介面與實作均為重新整理;預設 Python 3.11+。
使用約定
- 陣列與圖的節點預設為
0-indexed;Fenwick Tree 內部使用1-indexed。 - 無限大使用
INF = 10**30,可依題目資料範圍調整。 - 圖的鄰接串列:無權圖為
graph[u] = [v, ...];加權圖為graph[u] = [(v, w), ...]。 - Python 遞迴深度有限。深樹優先用迭代 DFS;需要遞迴時再提高
sys.setrecursionlimit。 - 模板中的型別標註可刪除,不影響執行。
基礎模組
競程常用的標準函式庫:
import sys
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right, insort
from heapq import heappop, heappush, heapify
from itertools import accumulate, permutations
from math import gcd, inf, isqrt
各模組的常見用途:
sys:高速輸入輸出、調整遞迴深度。Counter:統計每個元素出現幾次。defaultdict:存取不存在的 key 時,自動建立預設值。deque:可從左右兩端O(1)加入或刪除,常用於 BFS、0-1 BFS、單調佇列。bisect_left:在已排序陣列中找第一個>= target的位置。bisect_right:在已排序陣列中找第一個> target的位置。insort:插入元素並維持排序;搜尋位置是O(log n),但串列搬移仍是O(n)。heappush、heappop、heapify:最小堆,常用於 Dijkstra、貪心與工作排程。accumulate:累積運算,最常用來建立前綴和。permutations:枚舉排列。gcd:最大公因數。inf:浮點正無限大;純整數題也常用10**30代表無限大。isqrt:整數平方根,不會有浮點誤差。
競程基本骨架
import sys
input = sys.stdin.readline # 比一般 input() 更適合大量逐行輸入
INF = 10**30 # 足夠大的整數,常用於最短路或 DP
MOD = 1_000_000_007 # 常見取模值,題目未要求時不用
def solve():
# 主要解題程式寫在這裡
pass
if __name__ == "__main__":
# 直接執行這個檔案時才呼叫 solve()
solve()
快速讀取全部整數
import sys
it = iter(map(int, sys.stdin.buffer.read().split()))
n = next(it)
values = [next(it) for _ in range(n)]
拆解
sys.stdin.buffer.read() 會一次把標準輸入的全部內容讀進來。
例如輸入:
5
10 20 30 40 50
讀進來的內容大致是:
b'5\n10 20 30 40 50\n'
前面的 b 表示資料是 bytes,也就是位元組資料。因為這裡只要讀整數,不必先把整份輸入解碼成一般字串,所以通常比逐行呼叫 input() 更快。
接著呼叫 .split(),它會按照空白、換行和 Tab 切開:
[b'5', b'10', b'20', b'30', b'40', b'50']
map(int, ...) 再把每一項轉成整數,概念上會得到:
5, 10, 20, 30, 40, 50
iter(...) 把這串數字變成 iterator(迭代器):
it = iter(...)
iterator 可以想成「記住目前讀到哪裡的取號器」。每呼叫一次 next(it),就拿出下一個數字,並自動往後移一格。
n = next(it)
第一次取出的數字是 5,所以:
n = 5
此時 iterator 的位置變化可以想成:
5 -> 10 -> 20 -> 30 -> 40 -> 50
^
下一個
最後這行:
values = [next(it) for _ in range(n)]
因為 n = 5,等同於:
values = []
for _ in range(5):
values.append(next(it))
它會依序取出 10、20、30、40、50,最後得到:
values = [10, 20, 30, 40, 50]
整段程式的用途
這段高速輸入:
it = iter(map(int, sys.stdin.buffer.read().split()))
n = next(it)
values = [next(it) for _ in range(n)]
在這個輸入格式下,相當於較直觀的逐行版本:
n = int(input())
values = list(map(int, input().split()))
差別在於逐行版每次只讀一行;sys.stdin.buffer.read() 則一次把全部輸入讀完。資料量很大時,整批讀取通常比較快;一般小題目則可優先使用較容易閱讀的 input()。
注意:使用
read()後,全部輸入已經一次取走。後面應繼續用同一個 iterator 讀資料,不要再混用input()。
資料結構
BIT(Fenwick Tree/樹狀陣列)
支援單點加值、前綴和與區間和;更新、查詢皆為 O(log n),空間 O(n)。公開索引採 0-indexed。
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
self.values = [0] * n
def add(self, index, delta):
self.values[index] += delta
i = index + 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def prefix_sum(self, right):
"""回傳 [0, right) 的總和。"""
total = 0
i = right
while i > 0:
total += self.tree[i]
i -= i & -i
return total
def range_sum(self, left, right):
"""回傳 [left, right) 的總和。"""
return self.prefix_sum(right) - self.prefix_sum(left)
def set(self, index, value):
self.add(index, value - self.values[index])
def lower_bound(self, target):
"""所有值非負時,找最小 i,使 prefix_sum(i + 1) >= target。"""
if target <= 0:
return 0
index = 0
step = 1 << (self.n.bit_length() - 1)
while step:
nxt = index + step
if nxt <= self.n and self.tree[nxt] < target:
index = nxt
target -= self.tree[nxt]
step >>= 1
return index
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
FenwickTree(n) 會建立三個重要欄位:
self.n:元素總數。self.values:保存每個位置目前的真實值,讓set()能計算差值。self.tree:Fenwick Tree 本體。它多開一格,內部索引使用1到n。
add(index, delta) 的外部 index 是 0-indexed,所以先執行 i = index + 1。接著:
i += i & -i
i & -i 會取出 i 最低位的 1,代表目前節點負責的區間長度。每次加上它,就會跳到下一個包含此位置的父節點。
prefix_sum(right) 計算半開區間 [0, right)。它反向執行:
i -= i & -i
每次移除最低位的 1,把數個互不重疊的區間加起來。於是 [left, right) 可寫成「右前綴減左前綴」。
例如陣列為 [3, 1, 4, 2]:
bit.range_sum(1, 4)
等同計算 1 + 4 + 2 = 7。
set(index, value) 不是直接把樹節點設成 value,而是先求:
delta = value - self.values[index]
再用 add() 把差值更新進去。
複雜度: add()、prefix_sum()、range_sum()、set() 都是 O(log n);空間 O(n)。
容易出錯: 公開介面是 0-indexed,樹內部是 1-indexed;不要把兩者混在一起。
Segment Tree(迭代式線段樹)
可自訂合併運算。建樹 O(n),單點更新與區間查詢 O(log n);區間採半開 [left, right)。
class SegmentTree:
def __init__(self, data, operation=min, identity=10**30):
self.operation = operation
self.identity = identity
self.size = 1
while self.size < len(data):
self.size <<= 1
self.tree = [identity] * (2 * self.size)
self.tree[self.size:self.size + len(data)] = data
for i in range(self.size - 1, 0, -1):
self.tree[i] = operation(self.tree[i << 1], self.tree[i << 1 | 1])
def set(self, index, value):
i = self.size + index
self.tree[i] = value
i >>= 1
while i:
self.tree[i] = self.operation(self.tree[i << 1], self.tree[i << 1 | 1])
i >>= 1
def query(self, left, right):
left += self.size
right += self.size
result_left = self.identity
result_right = self.identity
while left < right:
if left & 1:
result_left = self.operation(result_left, self.tree[left])
left += 1
if right & 1:
right -= 1
result_right = self.operation(self.tree[right], result_right)
left >>= 1
right >>= 1
return self.operation(result_left, result_right)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
線段樹把陣列區間不斷切成左右兩半。self.size 會擴充到不小於原陣列長度的最小 2 次方,這樣每個節點都能有完整的左右子節點。
self.tree[self.size:self.size + len(data)] = data
葉節點從 self.size 開始放。接著由下往上合併:
self.tree[i] = operation(self.tree[i << 1], self.tree[i << 1 | 1])
i << 1等同i * 2,是左子節點。i << 1 | 1等同i * 2 + 1,是右子節點。operation可以是min、max、加法或其他可結合的運算。
set(index, value) 先修改葉節點,再一路除以 2 回到根節點,重新計算沿途答案。
query(left, right) 查詢半開區間 [left, right):
- 若
left是右子節點,代表它不能和左邊兄弟一起取,所以先收進答案,再右移。 - 若
right是右邊界,先往左移一格;該節點代表的完整區間可收進答案。 - 之後兩端一起除以
2,往上一層繼續。
例如:
tree = SegmentTree([5, 2, 7, 1], min, 10**30)
tree.query(1, 4) # min([2, 7, 1]),結果為 1
複雜度: 建樹 O(n);單點更新和區間查詢 O(log n);空間 O(n)。
容易出錯: identity 必須是運算的單位元素。求最小值用正無限大,求最大值用負無限大,求總和用 0。
Sparse Table(稀疏表)
適合靜態、具冪等性的區間運算,例如 min、max、gcd。建表 O(n log n),查詢 O(1)。
class SparseTable:
def __init__(self, data, operation=min):
if not data:
raise ValueError("data must not be empty")
self.operation = operation
n = len(data)
self.log = [0] * (n + 1)
for i in range(2, n + 1):
self.log[i] = self.log[i >> 1] + 1
self.table = [data[:]]
k = 1
while (1 << k) <= n:
half = 1 << (k - 1)
previous = self.table[-1]
self.table.append([
operation(previous[i], previous[i + half])
for i in range(n - (1 << k) + 1)
])
k += 1
def query(self, left, right):
k = self.log[right - left]
return self.operation(
self.table[k][left],
self.table[k][right - (1 << k)],
)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
Sparse Table 適合「陣列不再修改,但要查很多次區間」的情況。
self.table[k][i] 表示:從 i 開始、長度為 2**k 的區間答案。
table[0][i]:長度 1
table[1][i]:長度 2
table[2][i]:長度 4
table[3][i]:長度 8
長度 2**k 可由兩段長度 2**(k-1) 合併:
operation(previous[i], previous[i + half])
查詢 [left, right) 時,先找不超過區間長度的最大 2 次方:
k = self.log[right - left]
接著取「從左端開始」與「到右端結束」的兩段。這兩段可能重疊,但 min、max、gcd 重複計算同一元素不會改變答案,所以可以 O(1) 查詢。
例如長度為 6 的區間,可用兩段長度 4 覆蓋;中間重疊沒有關係。
複雜度: 前處理 O(n log n),每次查詢 O(1),空間 O(n log n)。
容易出錯: 一般加法不能用這種重疊查詢,因為重疊元素會被加兩次。區間也不能為空。
<!-- END ALGORITHM EXPLANATION -->DSU(Disjoint Set Union/並查集)
路徑壓縮搭配按大小合併,均攤近似 O(1)。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
self.components -= 1
return True
def same(self, a, b):
return self.find(a) == self.find(b)
def component_size(self, x):
return self.size[self.find(x)]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
DSU 用來維護「哪些元素屬於同一組」。一開始每個元素自己是一組:
self.parent = list(range(n))
self.size = [1] * n
find(x) 沿著 parent 找到集合代表。這行是路徑壓縮:
self.parent[x] = self.parent[self.parent[x]]
它把 x 直接接到祖父節點,使之後的查詢路徑更短。
union(a, b) 先找到兩個集合的代表。若相同,表示已經連通,回傳 False。不同時,將小集合接到大集合:
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
這叫做「按大小合併」,可避免樹變得很深。
例如依序合併 (0, 1)、(2, 3)、(1, 3) 後,0、1、2、3 都會屬於同一組,而 component_size(2) 會得到 4。
複雜度: 搭配路徑壓縮與按大小合併後,單次操作均攤為 O(α(n)),實務上近似常數。
常見用途: Kruskal 最小生成樹、連通性查詢、離線加邊、判斷加入一條邊是否形成環。
<!-- END ALGORITHM EXPLANATION -->Monotone Stack(單調棧)
找每個位置右側第一個嚴格較小元素,總時間 O(n)。改變比較符號即可處理「較大」或允許相等的版本。
def next_smaller_indices(values):
answer = [-1] * len(values)
stack: list[int] = []
for i, value in enumerate(values):
while stack and values[stack[-1]] > value:
answer[stack.pop()] = i
stack.append(i)
return answer
def largest_rectangle(heights):
best = 0
stack: list[tuple[int, int]] = []
for i, height in enumerate(heights + [0]):
start = i
while stack and stack[-1][1] > height:
index, old_height = stack.pop()
best = max(best, old_height * (i - index))
start = index
if not stack or stack[-1][1] < height:
stack.append((start, height))
return best
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
next_smaller_indices() 的 stack 保存「還沒找到右側較小值」的索引,而且對應數值維持單調不減。
掃描到新值 value 時:
while stack and values[stack[-1]] > value:
answer[stack.pop()] = i
若棧頂比新值大,代表新值就是棧頂右側第一個較小元素。索引被彈出後不會再進棧,因此所有元素總共只進出一次。
例如 [4, 2, 5, 1]:
4遇到2,答案是索引1。2和5遇到1,答案都是索引3。1右側沒有更小值,保留-1。
largest_rectangle() 的棧保存 (最早起點, 高度)。遇到較矮柱子時,表示較高柱子的矩形不能再向右延伸,因此立刻計算:
old_height * (i - index)
最後附加的 0 是哨兵,強迫所有剩餘高度出棧,不必在迴圈後再寫一次清理。
複雜度: 兩個模板都是 O(n) 時間、O(n) 空間。
容易出錯: > 和 >= 對重複值的處理不同;題目要求嚴格較小、較小或相等時要調整比較符號。
Monotone Deque(單調雙端佇列)
滑動視窗最大值為 O(n);佇列存索引,便於移除過期元素。
from collections import deque
def sliding_window_maximum(values, k):
if k <= 0 or k > len(values):
return []
queue: deque[int] = deque()
answer = []
for i, value in enumerate(values):
while queue and queue[0] <= i - k:
queue.popleft()
while queue and values[queue[-1]] <= value:
queue.pop()
queue.append(i)
if i + 1 >= k:
answer.append(values[queue[0]])
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
佇列中保存索引而不是值,因為索引可以判斷元素是否已離開視窗。
每次處理索引 i 時先移除過期元素:
while queue and queue[0] <= i - k:
queue.popleft()
接著從右側刪掉不可能再成為最大值的元素:
while queue and values[queue[-1]] <= value:
queue.pop()
若舊值小於或等於新值,新值不但比較大,而且活得更久,所以舊值永遠不可能成為未來視窗的最大值。
例如 values = [1, 3, 2, 5]、k = 3:
- 視窗
[1, 3, 2]的最大值是3。 - 視窗向右移成
[3, 2, 5];加入5時會從右側移除2和3,最大值變成5。
佇列左端永遠是目前視窗最大值的索引。
複雜度: 每個索引最多進出佇列一次,總時間 O(n),空間 O(k)。
圖論
BFS(廣度優先搜尋)
無權圖最短距離為 O(V + E)。
from collections import deque
def bfs(graph, source):
n = len(graph)
distance = [-1] * n
parent = [-1] * n
distance[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if distance[v] == -1:
distance[v] = distance[u] + 1
parent[v] = u
queue.append(v)
return distance, parent
def restore_path(parent, target):
path = []
while target != -1:
path.append(target)
target = parent[target]
return path[::-1]
網格 BFS:
def grid_bfs(grid, start):
rows, columns = len(grid), len(grid[0])
distance = [[-1] * columns for _ in range(rows)]
sr, sc = start
distance[sr][sc] = 0
queue = deque([start])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue:
row, column = queue.popleft()
for dr, dc in directions:
nr, nc = row + dr, column + dc
if (0 <= nr < rows and 0 <= nc < columns
and grid[nr][nc] != "#" and distance[nr][nc] == -1):
distance[nr][nc] = distance[row][column] + 1
queue.append((nr, nc))
return distance
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
第一段程式處理無權圖。distance 初始為 -1,同時代表「尚未造訪」;起點距離設成 0。
BFS 使用 FIFO 佇列:先進去的節點先處理,所以會按距離 0、1、2、... 一層一層向外擴張。第一次到達某節點時,就是最少邊數的路徑。
distance[v] = distance[u] + 1
parent[v] = u
parent[v] 記錄「從哪個節點走到 v」,因此 restore_path() 可從終點沿父節點倒走,再把結果反轉。
例如邊為 0-1、0-2、1-3,從 0 開始:
distance = [0, 1, 1, 2]
第二段 grid_bfs() 把每個格子視為節點,只嘗試上下左右四個方向。條件同時檢查:
- 新座標沒有超出矩陣。
- 不是牆壁
#。 - 還沒被造訪。
複雜度: 一般圖 O(V + E);rows × columns 網格為 O(rows × columns)。
容易出錯: 將節點放入佇列時就要立刻標記距離,不能等取出時才標記,否則同一節點可能重複入列。
<!-- END ALGORITHM EXPLANATION -->0-1 BFS
邊權只能是 0 或 1。權重 0 的節點推到左側,權重 1 推到右側,時間 O(V + E)。
def zero_one_bfs(graph, source):
distance = [10**30] * len(graph)
distance[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v, weight in graph[u]:
candidate = distance[u] + weight
if candidate < distance[v]:
distance[v] = candidate
if weight == 0:
queue.appendleft(v)
else:
queue.append(v)
return distance
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
0-1 BFS 只適用邊權為 0 或 1 的圖。它與 Dijkstra 的概念相似,但不需要 heap。
若走一條權重 0 的邊,距離沒有增加,應優先處理:
queue.appendleft(v)
若權重是 1,距離增加一,放到右端:
queue.append(v)
因此 deque 內的節點會大致依距離由小到大排列。
例如 0 -> 1 權重 1,0 -> 2 權重 0,2 -> 1 權重 0。雖然直接到 1 的成本是 1,但 2 會被放到左端優先處理,最後找到 0 -> 2 -> 1,成本為 0。
if candidate < distance[v]:
... # 找到更短路徑時才更新
只有找到更短距離才更新,避免無意義的重複加入。
複雜度: O(V + E) 時間、O(V) 額外空間。
容易出錯: 若邊權出現 2、負數或其他值,就不能使用這個模板。
DFS(深度優先搜尋)
def iterative_dfs(graph, source):
visited = [False] * len(graph)
order = []
stack = [source]
while stack:
u = stack.pop()
if visited[u]:
continue
visited[u] = True
order.append(u)
for v in reversed(graph[u]):
if not visited[v]:
stack.append(v)
return order
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
DFS 會沿一條路盡量走到底,再回頭探索其他分支。此版本用 stack 模擬遞迴,因此不會遇到 Python 遞迴深度限制。
u = stack.pop()
串列尾端是棧頂,後放入的節點會先被處理。若節點已造訪就略過;否則標記並加入 order。
for v in reversed(graph[u]):
... # 反向推入棧,維持預期的走訪順序
反轉鄰居只是為了讓迭代版的造訪順序接近遞迴版。假設鄰居是 [1, 2, 3],反向推入棧後,1 會最先被取出。
小例子: 0 連到 1、2,1 再連到 3。依鄰接串列順序,結果可能是 [0, 1, 3, 2]。
複雜度: O(V + E) 時間、最壞 O(V) 空間。
常見用途: 連通元件、拓撲概念、樹遍歷、環偵測、Euler Tour。
<!-- END ALGORITHM EXPLANATION -->Dijkstra(非負權最短路徑)
使用二元堆,時間 O((V + E) log V)。含負權邊時不能使用。
from heapq import heappop, heappush
def dijkstra(graph, source):
n = len(graph)
distance = [10**30] * n
parent = [-1] * n
distance[source] = 0
heap = [(0, source)]
while heap:
current_distance, u = heappop(heap)
if current_distance != distance[u]:
continue
for v, weight in graph[u]:
candidate = current_distance + weight
if candidate < distance[v]:
distance[v] = candidate
parent[v] = u
heappush(heap, (candidate, v))
return distance, parent
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
distance[v] 保存目前找到的最短距離,heap 保存 (距離, 節點)。Python tuple 會先比較第一項,所以距離最小的狀態最先被取出。
current_distance, u = heappop(heap)
同一節點可能因為後來找到更短路徑而被重複放進 heap。這段會丟掉過期狀態:
if current_distance != distance[u]:
continue
對每條 u -> v、權重 weight 的邊做鬆弛:
candidate = current_distance + weight
if candidate < distance[v]:
... # 更新 distance、parent,再推入 heap
若新距離更短,就更新 distance[v]、記錄 parent[v] = u,再把新狀態推入 heap。
例如 0 -> 1 成本 5,0 -> 2 成本 1,2 -> 1 成本 2。演算法會把到 1 的答案從 5 改成 3。
複雜度: 使用鄰接串列與二元堆時為 O((V + E) log V)。
容易出錯: 不能有負權邊;若有負權邊應考慮 Bellman–Ford 或其他方法。
<!-- END ALGORITHM EXPLANATION -->Floyd–Warshall(全源最短路)
時間 O(n^3)、空間 O(n^2);可處理負權邊,但若 distance[i][i] < 0 代表存在負環。
def floyd_warshall(matrix):
distance = [row[:] for row in matrix]
n = len(distance)
for k in range(n):
for i in range(n):
if distance[i][k] >= 10**30:
continue
dik = distance[i][k]
for j in range(n):
distance[i][j] = min(distance[i][j], dik + distance[k][j])
return distance
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
distance[i][j] 表示從 i 到 j 的目前最短距離。初始化時:
distance[i][i] = 0。- 有直接邊就填邊權。
- 沒有邊填
INF。
三層迴圈的最外層 k 表示:現在允許使用編號 0..k 的節點作為中繼點。
distance[i][j] = min(
distance[i][j],
distance[i][k] + distance[k][j],
)
也就是比較「原本的路」與「先走到 k、再從 k 走到 j」哪個比較短。
例如原本 0 -> 2 成本 10,但 0 -> 1 成本 3、1 -> 2 成本 4,當 k = 1 時答案會更新成 7。
複雜度: O(n³) 時間、O(n²) 空間,適合節點數較小但需要大量任意兩點查詢的題目。
負環判斷: 完成後若任何 distance[i][i] < 0,表示存在可到達的負權環。
Topological Sort(Kahn 拓撲排序)
只適用有向無環圖;若結果少於 n 個節點,圖中存在環。
def topological_sort(graph):
indegree = [0] * len(graph)
for edges in graph:
for v in edges:
indegree[v] += 1
queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
拓撲排序只適用有向無環圖。indegree[v] 表示有多少條邊指向 v,也就是還有多少先決條件尚未完成。
先把所有入度為 0 的節點加入佇列:
queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
每取出一個節點 u,就視為已完成它,並刪除它指向鄰居的影響:
indegree[v] -= 1
若某鄰居的入度降到 0,代表其所有前置節點都已完成,可以加入佇列。
例如依賴關係 0 -> 2、1 -> 2,一開始 0、1 都可處理;兩者完成後 2 才能進入答案。
若最後 order 少於節點總數,代表剩下節點互相依賴,圖中存在環,所以回傳 None。
複雜度: O(V + E)。
延伸: 若題目要求字典序最小的拓撲序,可把 deque 改成最小堆。
<!-- END ALGORITHM EXPLANATION -->Kruskal(最小生成樹)
邊格式為 (weight, u, v);時間 O(E log E)。若最後選不到 n - 1 條邊,圖不連通。
def kruskal(n, edges):
dsu = DSU(n)
total = 0
chosen = []
for weight, u, v in sorted(edges):
if dsu.union(u, v):
total += weight
chosen.append((u, v, weight))
return (total, chosen) if len(chosen) == n - 1 else None
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
Kruskal 的貪心策略是:從權重最小的邊開始考慮,只要不形成環就選入。
for weight, u, v in sorted(edges):
... # 依邊權由小到大處理
邊使用 (weight, u, v),因此 Python 排序會優先依權重由小到大。
if dsu.union(u, v):
... # 合併成功代表加入此邊不會形成環
若 u 和 v 原本不在同一集合,union() 會成功,表示加入此邊不會形成環;接著累加權重並記錄選中的邊。若原本已連通,加入它一定會形成環,所以略過。
一棵含 n 個節點的生成樹必須剛好有 n - 1 條邊。若最後不足,代表原圖不連通,無法建立生成樹。
複雜度: 排序為 O(E log E);DSU 操作近似常數。
容易出錯: 無向邊只需放一次進 edges;若題目要最大生成樹,可改成依權重由大到小排序。
LCA(最近公共祖先/Binary Lifting)
前處理 O(n log n),每次查詢 O(log n)。
class LCA:
def __init__(self, tree, root = 0):
n = len(tree)
self.log = max(1, n.bit_length())
self.depth = [-1] * n
self.up = [[root] * n for _ in range(self.log)]
self.depth[root] = 0
stack = [root]
while stack:
u = stack.pop()
for v in tree[u]:
if self.depth[v] == -1:
self.depth[v] = self.depth[u] + 1
self.up[0][v] = u
stack.append(v)
for bit in range(1, self.log):
previous = self.up[bit - 1]
self.up[bit] = [previous[previous[v]] for v in range(n)]
def kth_ancestor(self, node, steps):
bit = 0
while steps:
if steps & 1:
node = self.up[bit][node]
steps >>= 1
bit += 1
return node
def query(self, a, b):
if self.depth[a] < self.depth[b]:
a, b = b, a
a = self.kth_ancestor(a, self.depth[a] - self.depth[b])
if a == b:
return a
for bit in range(self.log - 1, -1, -1):
if self.up[bit][a] != self.up[bit][b]:
a, b = self.up[bit][a], self.up[bit][b]
return self.up[0][a]
def distance(self, a, b):
ancestor = self.query(a, b)
return self.depth[a] + self.depth[b] - 2 * self.depth[ancestor]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
up[bit][v] 表示節點 v 往上跳 2**bit 步後到達的祖先。
前處理先用 DFS 建立:
depth[v]:節點深度。up[0][v]:直接父節點。
再用:
self.up[bit][v] = previous[previous[v]]
求出 2、4、8、... 步祖先。
查詢 query(a, b) 分兩階段:
- 若深度不同,先把較深節點往上跳,使兩者同一深度。
- 從最大
bit往下檢查;若兩者跳2**bit步後仍不同,就一起跳。最後兩者的父節點就是 LCA。
例如 0 是根,1、2 是其孩子,3、4 是 1 的孩子:LCA(3, 4) = 1,LCA(3, 2) = 0。
距離公式為:
depth[a] + depth[b] - 2 * depth[lca]
複雜度: 前處理 O(n log n);每次 LCA 或第 k 個祖先查詢 O(log n)。
Binary Lifting(通用倍增)
class BinaryLifting:
def __init__(self, next_node, max_steps):
levels = max(1, max_steps.bit_length())
self.jump = [next_node[:]]
for _ in range(1, levels):
previous = self.jump[-1]
self.jump.append([previous[previous[x]] for x in range(len(next_node))])
def move(self, node, steps):
bit = 0
while steps:
if steps & 1:
node = self.jump[bit][node]
bit += 1
steps >>= 1
return node
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
這個模板不限定是樹。只要每個狀態都有唯一的下一個狀態 next_node[x],就能快速跳很多步。
self.jump[0][x] = next_node[x]
代表跳 1 步;下一層透過跳兩次前一層建立:
previous[previous[x]]
因此 jump[1] 是 2 步、jump[2] 是 4 步、jump[3] 是 8 步。
move(node, steps) 把 steps 拆成二進位。例如 13 = 8 + 4 + 1,只需使用第 3、2、0 層,各跳一次。
if steps & 1:
node = self.jump[bit][node]
每次處理最低位後右移 steps。
複雜度: 前處理 O(n log K),查詢 O(log K),其中 K 是最大步數。
常見用途: 函數圖跳躍、祖先查詢、重複狀態轉移。
<!-- END ALGORITHM EXPLANATION -->Bipartite Check(二分圖判定)
def bipartite_coloring(graph):
color = [-1] * len(graph)
for source in range(len(graph)):
if color[source] != -1:
continue
color[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = color[u] ^ 1
queue.append(v)
elif color[v] == color[u]:
return None
return color
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
二分圖可以把每個節點塗成 0 或 1,且每條邊的兩端顏色都不同。
color = [-1] * n 中的 -1 表示尚未染色。因為圖可能不連通,所以外層迴圈會從每個尚未染色的節點開始一次 BFS。
color[v] = color[u] ^ 1
XOR 1 會把 0 變 1、1 變 0,因此鄰居會得到相反顏色。
若遇到已染色鄰居,而且:
color[v] == color[u]
表示一條邊的兩端同色,無法二分,立即回傳 None。
例如三角形 0-1-2-0 無法使用兩色完成,因為第三條邊必定連接相同顏色;偶數長度環則可以二分。
複雜度: O(V + E)。
常見判斷: 無向圖是二分圖,等價於圖中沒有奇數長度環。
<!-- END ALGORITHM EXPLANATION -->Cycle Detection(環偵測)
有向圖使用三色標記;0 未造訪、1 搜尋中、2 已完成。
def has_directed_cycle(graph):
color = [0] * len(graph)
def visit(start):
stack = [(start, 0)]
color[start] = 1
while stack:
u, edge_index = stack[-1]
if edge_index == len(graph[u]):
color[u] = 2
stack.pop()
continue
v = graph[u][edge_index]
stack[-1] = (u, edge_index + 1)
if color[v] == 1:
return True
if color[v] == 0:
color[v] = 1
stack.append((v, 0))
return False
return any(color[u] == 0 and visit(u) for u in range(len(graph)))
def has_undirected_cycle(graph):
visited = [False] * len(graph)
for source in range(len(graph)):
if visited[source]:
continue
visited[source] = True
stack = [(source, -1)]
while stack:
u, parent = stack.pop()
for v in graph[u]:
if not visited[v]:
visited[v] = True
stack.append((v, u))
elif v != parent:
return True
return False
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
有向圖版本使用三種顏色:
0:尚未造訪。1:正在目前 DFS 路徑中。2:此節點及其後續都已處理完成。
迭代棧保存 (節點, 下一條要看的邊索引),用來模擬遞迴進入與返回。
若從 u 看見 color[v] == 1,表示邊指回目前路徑上的祖先,這是一條 back edge,因此存在有向環。
無向圖版本則保存 (u, parent)。看到已造訪的鄰居時,如果它不是父節點,就表示從另一條路回到舊節點,形成環。
例如無向邊 0-1、1-2、2-0:從 2 看見已造訪且不是父節點的 0,即可判定有環。
複雜度: 兩個版本皆為 O(V + E)。
容易出錯: 有向圖不能只用一般 visited;必須區分「仍在目前路徑」和「已經完成」。
Tree Diameter(樹直徑)
無權樹做兩次 BFS。
def tree_diameter(tree):
def farthest(source):
distance = [-1] * len(tree)
distance[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in tree[u]:
if distance[v] == -1:
distance[v] = distance[u] + 1
queue.append(v)
node = max(range(len(tree)), key=distance.__getitem__)
return node, distance
a, _ = farthest(0)
b, distance = farthest(a)
return distance[b], a, b
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
樹直徑是樹上兩節點間的最長簡單路徑。無權樹可以用兩次 BFS:
- 從任意節點(程式用
0)出發,找到最遠節點a。 - 再從
a出發,找到最遠節點b。 distance[b]就是直徑長度,a、b是直徑兩端。
為什麼有效:第一次 BFS 找到的最遠節點一定可以作為某條直徑的端點;從它再找最遠點,就會到達另一端。
例如鏈狀樹 0-1-2-3:從 0 找到最遠的 3,再從 3 找到最遠的 0,直徑為 3 條邊。
node = max(range(len(tree)), key=distance.__getitem__)
這行取得 distance 最大的索引。
複雜度: 兩次 BFS 仍是 O(V + E);樹中 E = V - 1,所以是 O(V)。
加權樹: 若邊有非負權重,可把內層 BFS 改為 DFS 並累加距離。
<!-- END ALGORITHM EXPLANATION -->Euler Tour(DFS 序)
子樹對應 Euler 序中的連續半開區間 [tin[u], tout[u])。
def euler_tour(tree, root = 0):
n = len(tree)
tin = [0] * n
tout = [0] * n
parent = [-1] * n
order = []
stack = [(root, -1, 0)]
while stack:
u, p, state = stack.pop()
if state == 0:
parent[u] = p
tin[u] = len(order)
order.append(u)
stack.append((u, p, 1))
for v in reversed(tree[u]):
if v != p:
stack.append((v, u, 0))
else:
tout[u] = len(order)
subtree_size = [tout[u] - tin[u] for u in range(n)]
return order, tin, tout, parent, subtree_size
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
Euler Tour 會把樹攤平成一維陣列。此模板在第一次進入節點時記錄:
tin[u] = len(order)
order.append(u)
處理完所有子節點、準備離開時記錄:
tout[u] = len(order)
因此節點 u 的整棵子樹會剛好落在:
order[tin[u]:tout[u]]
例如根 0 有孩子 1、2,而 1 有孩子 3。一種 DFS 序可能是 [0, 1, 3, 2];節點 1 的子樹區間是 [1, 3),對應 [1, 3]。
棧中的 state:
0:第一次進入節點。1:所有子節點已安排處理,現在離開節點。
這種寫法在不使用遞迴的情況下,仍能同時取得進入與離開時間。
複雜度: O(n) 時間、O(n) 空間。
常見用途: 搭配 Fenwick Tree 或 Segment Tree 做子樹加總、子樹更新與祖先判斷。
<!-- END ALGORITHM EXPLANATION -->Subtree Size(子樹大小)
在上一節的 Euler Tour 中,subtree_size[u] = tout[u] - tin[u]。若只需要子樹大小,也可用後序累加:
def subtree_sizes(tree, root = 0):
parent = [-1] * len(tree)
order = [root]
for u in order:
for v in tree[u]:
if v != parent[u]:
parent[v] = u
order.append(v)
size = [1] * len(tree)
for u in reversed(order[1:]):
size[parent[u]] += size[u]
return size
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
第一個迴圈建立父節點與由上到下的 order:
parent[v] = u
order.append(v)
一開始每個節點的子樹至少包含自己,所以:
size = [1] * len(tree)
接著必須反向走訪 order。這樣孩子一定會在父節點之前完成:
for u in reversed(order[1:]):
size[parent[u]] += size[u]
每個節點把自己的子樹大小加給父節點,最後根節點的大小會是整棵樹節點數。
例如 0 的孩子是 1、2,1 的孩子是 3:
size[3] = 1
size[1] = 2
size[2] = 1
size[0] = 4
order[1:] 刻意跳過根,因為根的 parent 是 -1,不需要再往上加。
複雜度: 每條樹邊看固定次數,時間 O(n)、空間 O(n)。
DSU 離線刪邊(反向加邊)
若操作只有刪除與詢問連通性,可先移除所有將被刪的邊,再倒序把邊加回。
def offline_dynamic_connectivity(n, edges, operations):
normalize = lambda a, b: (a, b) if a < b else (b, a)
cut_edges = {normalize(u, v) for kind, u, v in operations if kind == "cut"}
dsu = DSU(n)
for u, v in edges:
if normalize(u, v) not in cut_edges:
dsu.union(u, v)
answer = []
for kind, u, v in reversed(operations):
if kind == "ask":
answer.append(dsu.same(u, v))
else:
dsu.union(u, v)
return answer[::-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
DSU 很會「加邊」,卻不容易真的刪邊。因此離線演算法把時間倒過來:正向的刪邊,在反向就變成加邊。
先收集所有將被刪除的邊:
cut_edges = {
normalize(u, v)
for kind, u, v in operations
if kind == "cut"
}
normalize() 把無向邊固定成較小端點在前,避免 (1, 3) 和 (3, 1) 被視為不同邊。
接著只把「最後仍存在」的邊加入 DSU。然後倒序處理操作:
- 原本的
ask:此刻直接用dsu.same(u, v)回答。 - 原本的
cut:反向時間中代表把這條邊加回,執行union(u, v)。
因為答案是倒序收集,最後要 answer[::-1] 回到原操作順序。
小例子: 原本先問 0、2 是否連通,再刪除 1-2,再問一次。反向時先處理第二次詢問,再把 1-2 加回,最後處理第一次詢問。
複雜度: O((E + Q) α(n)),近似線性。
限制: 此簡化模板假設無向邊不重複,且每條邊不會被重複刪除。
<!-- END ALGORITHM EXPLANATION -->動態規劃
0/1 Knapsack(0/1 背包)
每件物品最多選一次,因此容量必須由大到小更新。時間 O(nC)、空間 O(C)。
def zero_one_knapsack(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for current in range(capacity, weight - 1, -1):
dp[current] = max(dp[current], dp[current - weight] + value)
return dp[capacity]
若要判斷是否能湊出某個總和:
def subset_sum(values, target):
possible = 1
for value in values:
possible |= possible << value
return bool((possible >> target) & 1)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
dp[current] 表示容量不超過 current 時能取得的最大價值。
每件物品 (weight, value) 只能選一次,所以容量必須由大到小更新:
for current in range(capacity, weight - 1, -1):
... # 容量倒序,避免同一物品重複使用
這樣讀取的 dp[current - weight] 仍是「尚未使用目前物品」的上一輪狀態。轉移表示兩種選擇:
dp[current] = max(
dp[current], # 不選目前物品
dp[current - weight] + value # 選目前物品
)
例如容量 5,物品為 (2, 3)、(3, 4),兩件都選剛好裝滿,答案是 7。
第二段 subset_sum() 使用整數 bitset。第 s 個 bit 為 1,代表總和 s 可達:
possible |= possible << value
左移 value 位等於把所有既有總和都加上 value。
複雜度: 一般 DP 為 O(nC) 時間、O(C) 空間;bitset 版本通常更快,但仍受目標總和大小影響。
容易出錯: 若容量由小到大更新,同一物品會在同一輪被重複使用,變成完全背包。
<!-- END ALGORITHM EXPLANATION -->Unbounded Knapsack(完全背包)
每件物品可重複選;容量由小到大更新。
def unbounded_knapsack(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for current in range(weight, capacity + 1):
dp[current] = max(dp[current], dp[current - weight] + value)
return dp[capacity]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
完全背包與 0/1 背包的主要差別只有容量迴圈方向:
for current in range(weight, capacity + 1):
... # 容量正序,允許重複使用目前物品
由小到大更新時,dp[current - weight] 可能已在本輪使用過目前物品,所以同一物品可以再次被選。
例如容量 6,只有物品 (weight=2, value=3):
dp[2] = 3
dp[4] = dp[2] + 3 = 6
dp[6] = dp[4] + 3 = 9
最後答案為 9,代表選了三次。
複雜度: O(nC) 時間、O(C) 空間。
判斷方式:
- 每件最多一次:容量倒序。
- 每件可重複:容量正序。
Coin Change(硬幣問題)
最少硬幣數:
def minimum_coins(coins, target):
dp = [target + 1] * (target + 1)
dp[0] = 0
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount:
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
return -1 if dp[target] > target else dp[target]
組合數(順序不計):硬幣放外層。排列數(順序要計):金額放外層。
def coin_change_combinations(coins, target, mod=None):
dp = [0] * (target + 1)
dp[0] = 1
for coin in coins:
for amount in range(coin, target + 1):
dp[amount] += dp[amount - coin]
if mod:
dp[amount] %= mod
return dp[target]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
第一段求湊出 target 所需的最少硬幣數。dp[amount] 的初始值設為 target + 1,代表尚不可達;dp[0] = 0 表示湊出 0 元不需要硬幣。
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
表示最後使用一枚 coin,前面先湊出 amount - coin。
例如硬幣 [1, 3, 4]、目標 6,最佳是 3 + 3,答案 2,不是貪心選 4 + 1 + 1 的 3 枚。
第二段計算組合數。硬幣放在外層,能確保 [1, 2] 和 [2, 1] 只算同一種組合:
for coin in coins:
for amount in range(coin, target + 1):
... # 硬幣在外層,因此不同順序只算一次
若題目把不同順序視為不同方法,應改成 amount 外層、coin 內層。
複雜度: 兩個版本皆為 O(len(coins) × target) 時間、O(target) 空間。
LIS(最長遞增子序列)
只求長度可用 patience sorting,時間 O(n log n)。嚴格遞增使用 bisect_left;非嚴格遞增改用 bisect_right。
from bisect import bisect_left
def lis_length(values):
tails = []
for value in values:
index = bisect_left(tails, value)
if index == len(tails):
tails.append(value)
else:
tails[index] = value
return len(tails)
還原其中一組 LIS:
def longest_increasing_subsequence(values):
if not values:
return []
tails = []
tail_indices = []
previous = [-1] * len(values)
for i, value in enumerate(values):
position = bisect_left(tails, value)
if position == len(tails):
tails.append(value)
tail_indices.append(i)
else:
tails[position] = value
tail_indices[position] = i
if position:
previous[i] = tail_indices[position - 1]
result = []
index = tail_indices[-1]
while index != -1:
result.append(values[index])
index = previous[index]
return result[::-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
tails[length - 1] 保存「長度為 length 的遞增子序列,其結尾可能有的最小值」。它不是最後答案本身,但長度一定正確。
index = bisect_left(tails, value)
找第一個 >= value 的位置:
- 若找不到,
value可以接在所有尾端之後,LIS 長度加一。 - 若找到,就用較小的
value替換原尾端,讓未來更容易接上更大的數。
例如 [3, 5, 2, 4]:
3 -> [3]
5 -> [3, 5]
2 -> [2, 5]
4 -> [2, 4]
所以長度是 2。
第二段用 tail_indices 記住每個長度目前尾端的原陣列索引,previous[i] 則指向 values[i] 在該 LIS 中的前一個元素。最後從最長尾端反向追蹤並反轉,即可還原一組答案。
複雜度: O(n log n) 時間、O(n) 空間。
嚴格性: 嚴格遞增用 bisect_left;允許相等的非遞減序列改用 bisect_right。
LCS(最長公共子序列)
時間 O(nm);以下以滾動陣列降為 O(m) 空間。
def lcs_length(a, b):
if len(a) < len(b):
a, b = b, a
previous = [0] * (len(b) + 1)
for x in a:
current = [0]
for j, y in enumerate(b, 1):
if x == y:
current.append(previous[j - 1] + 1)
else:
current.append(max(previous[j], current[-1]))
previous = current
return previous[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
LCS 允許跳過元素,但不能改變順序。完整狀態原本是 dp[i][j]:a 前 i 個字元和 b 前 j 個字元的 LCS 長度。
若目前字元相同:
current.append(previous[j - 1] + 1)
答案來自左上角再加 1。若不同,就選擇跳過 a 或跳過 b:
max(previous[j], current[-1])
previous[j]:跳過目前的a字元。current[-1]:跳過目前的b字元。
程式只保留上一列 previous 和目前列 current,把空間從 O(nm) 降到 O(min(n, m))。
例如 a = "ABC"、b = "AC",LCS 是 "AC",長度為 2。
複雜度: O(nm) 時間、O(min(n, m)) 空間。
Edit Distance(編輯距離)
插入、刪除、替換的成本皆為 1。
def edit_distance(a, b):
if len(a) < len(b):
a, b = b, a
previous = list(range(len(b) + 1))
for i, x in enumerate(a, 1):
current = [i]
for j, y in enumerate(b, 1):
current.append(min(
current[-1] + 1,
previous[j] + 1,
previous[j - 1] + (x != y),
))
previous = current
return previous[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
previous[j] 和 current[j] 分別代表上一列與目前列 DP。每個狀態比較三種操作:
current[-1] + 1 # 插入
previous[j] + 1 # 刪除
previous[j - 1] + (x != y) # 替換或不操作
(x != y) 在 Python 中是布林值,但參與加法時 False = 0、True = 1:
- 字元相同,不需成本。
- 字元不同,替換成本為
1。
第一列 0, 1, 2, ... 表示把空字串變成 b 前綴需要連續插入;每列的第一個值 i 表示把 a 前綴全部刪除。
例如把 cat 變成 cut,只需把 a 替換成 u,距離為 1。
複雜度: O(nm) 時間、O(min(n, m)) 空間。
Grid DP(網格 DP)
由左上走到右下,只能向右或向下,求最小成本;時間 O(rows × columns)。
def minimum_grid_path(cost):
rows, columns = len(cost), len(cost[0])
dp = [10**30] * columns
dp[0] = 0
for row in range(rows):
for column in range(columns):
from_up = dp[column]
from_left = dp[column - 1] if column else 10**30
dp[column] = cost[row][column] + min(from_up, from_left)
return dp[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
題目只允許從左上角往右或往下,因此到達 (row, column) 的前一步只可能來自上方或左方。
from_up = dp[column]
from_left = dp[column - 1] if column else 10**30
在更新前,dp[column] 仍保存上一列同欄的答案;dp[column - 1] 已更新成目前列左邊格子的答案。
dp[column] = cost[row][column] + min(from_up, from_left)
加入目前格子的成本,選較便宜的進入方向。
第一格使用初始 dp[0] = 0,因此答案會從 cost[0][0] 正確開始。不存在的左方以 INF 表示。
例如:
1 3
2 1
最佳路徑是 1 -> 2 -> 1,總成本 4。
複雜度: O(rows × columns) 時間、O(columns) 空間。
Interval DP(區間 DP)
典型狀態是 dp[left][right],按區間長度由短到長計算。下例為矩陣鏈乘最少乘法次數,時間 O(n^3)。
def matrix_chain_cost(dimensions):
n = len(dimensions) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for left in range(n - length + 1):
right = left + length - 1
dp[left][right] = min(
dp[left][middle] + dp[middle + 1][right]
+ dimensions[left] * dimensions[middle + 1] * dimensions[right + 1]
for middle in range(left, right)
)
return dp[0][n - 1] if n else 0
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
區間 DP 的狀態依賴較短區間,因此外層先枚舉 length,從長度 2 慢慢增加。
矩陣鏈中,dimensions = [d0, d1, ..., dn] 表示第 i 個矩陣大小為 dimensions[i] × dimensions[i+1]。
dp[left][right] 是把第 left..right 個矩陣相乘的最少成本。枚舉最後一次切割位置 middle:
dp[left][middle] + dp[middle + 1][right]
+ dimensions[left] * dimensions[middle + 1] * dimensions[right + 1]
前兩項是左右兩半各自的成本,最後一項是把兩個結果矩陣乘起來的成本。
例如尺寸 [10, 30, 5, 60]:先算 (10×30)(30×5) 再乘 (5×60),通常比另一種括號順序省很多。
複雜度: O(n³) 時間、O(n²) 空間。
共同模式: 回文、石子合併、括號化等題目也常用「區間長度 → 左端 → 分割點」三層迴圈。
<!-- END ALGORITHM EXPLANATION -->Bitmask DP(狀態壓縮 DP)
旅行推銷員:dp[mask][u] 表示從 0 出發,走過 mask 中節點且停在 u 的最小成本。時間 O(n²2ⁿ)。
def traveling_salesperson(distance):
n = len(distance)
full = 1 << n
dp = [[10**30] * n for _ in range(full)]
dp[1][0] = 0
for mask in range(full):
for u in range(n):
if not (mask >> u) & 1:
continue
for v in range(n):
if (mask >> v) & 1:
continue
new_mask = mask | (1 << v)
dp[new_mask][v] = min(
dp[new_mask][v], dp[mask][u] + distance[u][v]
)
return min(dp[-1][u] + distance[u][0] for u in range(n))
枚舉 mask 的所有非空子集合:
subset = mask
while subset:
# 使用 subset
subset = (subset - 1) & mask
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
第 v 個 bit 是否為 1,代表節點 v 是否已走過:
(mask >> v) & 1
dp[mask][u] 表示從節點 0 出發,走過 mask 中所有節點,最後停在 u 的最小成本。初始:
dp[1][0] = 0
因為 mask = 1 只有第 0 bit 為 1。
轉移到尚未造訪的 v:
new_mask = mask | (1 << v)
最後所有節點都走過後,再加上回到起點的成本。
第二段:
subset = (subset - 1) & mask
可依序枚舉 mask 的所有非空子集合,不會產生 mask 以外的 bit。
複雜度: TSP 為 O(n²2ⁿ) 時間、O(n2ⁿ) 空間,只適合 n 較小的題目。
Game DP(Nim/Sprague–Grundy)
Nim 的必勝條件是所有石堆大小 XOR 不為 0。
from functools import reduce
from operator import xor
def nim_first_player_wins(piles):
return reduce(xor, piles, 0) != 0
一般無環公平組合遊戲可計算 SG 值:
def mex(values):
seen = set(values)
result = 0
while result in seen:
result += 1
return result
def grundy_numbers(graph):
sg = [-1] * len(graph)
def solve(state):
if sg[state] == -1:
sg[state] = mex(solve(next_state) for next_state in graph[state])
return sg[state]
for state in range(len(graph)):
solve(state)
return sg
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
Nim 中每回合可從任一石堆拿走正數顆石頭。所有石堆大小 XOR:
reduce(xor, piles, 0)
若結果不為 0,先手存在必勝走法;若為 0,在雙方最佳策略下先手必敗。
例如 [1, 2, 3]:1 ^ 2 ^ 3 = 0,先手必敗;[1, 2, 4] 的 XOR 不為 0,先手必勝。
一般公平組合遊戲用 SG 值。終止狀態沒有後繼狀態,其後繼 SG 集合為空,所以 mex({}) = 0。
sg[state] = mex(solve(next_state) for next_state in graph[state])
mex 是集合中未出現的最小非負整數。例如 {0, 1, 3} 的 mex 是 2。
多個獨立子遊戲組合時,把各自 SG 值 XOR;非零為必勝。
限制: grundy_numbers() 假設遊戲狀態圖無環,否則遞迴不會正常結束。
Tree DP(樹 DP)
最大權重獨立集:相鄰節點不能同時選。skip[u] 不選 u,take[u] 選 u。
def maximum_weight_independent_set(tree, weight, root=0):
parent = [-1] * len(tree)
order = [root]
for u in order:
for v in tree[u]:
if v != parent[u]:
parent[v] = u
order.append(v)
skip = [0] * len(tree)
take = weight[:]
for u in reversed(order):
for v in tree[u]:
if parent[v] == u:
skip[u] += max(skip[v], take[v])
take[u] += skip[v]
return max(skip[root], take[root])
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
最大權重獨立集要求相鄰節點不能同時選。每個節點有兩個狀態:
take[u]:選擇u。skip[u]:不選u。
若選 u,孩子一定不能選:
take[u] += skip[v]
若不選 u,每個孩子可自由選擇較好的狀態:
skip[u] += max(skip[v], take[v])
第一個迴圈先建立父節點與由上到下的順序;第二個迴圈反向處理,確保計算父節點前,所有孩子都已完成。
例如只有一條邊 0-1,權重為 [5, 8],答案會選節點 1,得到 8;若根還有另一個權重 7 的孩子,則可同時選兩個孩子得到 15。
複雜度: O(n) 時間、O(n) 空間。
Weighted Job Scheduling(加權工作排程)
工作格式 (start, end, profit),選互不重疊的工作使收益最大。排序與二分後為 O(n log n)。
from bisect import bisect_right
def weighted_job_scheduling(jobs):
jobs = sorted(jobs, key=lambda job: job[1])
ends = [end for _, end, _ in jobs]
dp = [0] * (len(jobs) + 1)
for i, (start, _, profit) in enumerate(jobs, 1):
compatible = bisect_right(ends, start, hi=i - 1)
dp[i] = max(dp[i - 1], dp[compatible] + profit)
return dp[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
工作格式是 (start, end, profit)。先依結束時間排序,dp[i] 表示只考慮前 i 個工作時的最大收益。
對第 i 個工作,用:
compatible = bisect_right(ends, start, hi=i - 1)
找出在目前工作開始前已結束的工作數量。因為 dp 多一個初始 0,這個數量可直接當成 DP 索引。
接著比較:
dp[i - 1] # 不選目前工作
dp[compatible] + profit # 選目前工作
例如工作 (1, 3, 5)、(2, 5, 6)、(4, 6, 5),第一和第三不重疊,總收益 10,優於只選第二個的 6。
複雜度: 排序 O(n log n),每個工作二分 O(log n),總計 O(n log n);空間 O(n)。
貪心
區間排程(Interval Scheduling)
結束時間越早越先選,可得到最多互不重疊區間。
def maximum_non_overlapping_intervals(intervals):
chosen = []
last_end = -10**30
for start, end in sorted(intervals, key=lambda interval: interval[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
目標是選最多個互不重疊區間。貪心規則是「每次選結束最早的區間」:它為後面的工作留下最多空間。
for start, end in sorted(intervals, key=lambda interval: interval[1]):
... # 優先考慮結束時間最早的區間
last_end 保存上一個已選區間的結束時間。若:
start >= last_end
代表新區間可接在後面,就把它加入答案並更新 last_end。
例如 (1, 4)、(2, 3)、(3, 5):先選結束最早的 (2, 3),接著可選 (3, 5),共兩個;若先選 (1, 4) 就只能得到一個。
複雜度: 排序 O(n log n),掃描 O(n)。
邊界: 此模板把 end == next_start 視為不重疊;若題意的端點是閉區間,條件可能要改成 start > last_end。
多機區間排程(k-Screen Scheduling)
每個節目只能安排一次;找結束時間不晚於開始時間且最晚空出的機器。Python 標準庫沒有 multiset,下例以排序陣列實作,適合中等資料量;大資料可改用 sortedcontainers.SortedList。
from bisect import bisect_right, insort
def k_machine_scheduling(intervals, k):
available = [-10**30] * k
count = 0
for start, end in sorted(intervals, key=lambda interval: interval[1]):
index = bisect_right(available, start) - 1
if index >= 0:
available.pop(index)
insort(available, end)
count += 1
return count
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
有 k 台機器時,available 保存每台機器目前工作的結束時間,並維持排序。
仍先按新工作的結束時間排序。對 (start, end),尋找不晚於 start 的最晚結束時間:
index = bisect_right(available, start) - 1
選「最晚但仍可用」的機器,是為了保留更早空出的機器給可能更早開始的其他工作。
找到後先移除舊結束時間,再插入新的 end:
available.pop(index)
insort(available, end)
例如兩台機器目前結束時間為 [3, 7],新工作從 5 開始,應使用結束於 3 的機器;結束於 7 的尚不可用。
複雜度: 此標準串列版本每次插入、刪除可能 O(k),總計最壞 O(nk)。大資料應使用支援有序 multiset 的結構。
最小化完成時間(Task Scheduling)
若每個工作的處理時間為 duration、完成後另有延遲 tail,常用 tail 由大到小安排,使整體完成時間最小。
def minimize_completion_time(tasks):
current = 0
answer = 0
for duration, tail in sorted(tasks, key=lambda task: -task[1]):
current += duration
answer = max(answer, current + tail)
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
每個工作有 (duration, tail):先花 duration 處理,之後還需等待 tail 才真正完成。機器同時只能處理一件工作,但 tail 可和之後的工作重疊。
因此 tail 越長越應優先開始:
sorted(tasks, key=lambda task: -task[1])
current 是目前累積的處理時間。完成某工作處理後,它的最終完成時刻是:
current + tail
答案取所有工作的最大值。
例如工作 (3, 10) 和 (2, 1):先做第一件,完成時刻分別為 13、6,總答案 13;反過來第一件會到 15 才完成。
複雜度: O(n log n)。
理解方式: 長 tail 若太晚開始,很容易成為整體最後完成的瓶頸。
<!-- END ALGORITHM EXPLANATION -->截止時間排程:Reverse Sweep
若每個工作有 (duration, deadline),全部都必須完成,從最晚截止時間往前排可求最晚開始時刻。
def latest_start_time(tasks):
current = 10**30
for duration, deadline in sorted(tasks, key=lambda task: task[1], reverse=True):
current = min(current, deadline) - duration
return current
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
每個工作為 (duration, deadline),所有工作都必須完成。程式從時間軸右側往左排。
先按 deadline 由晚到早排序。對每個工作:
current = min(current, deadline) - duration
min(current, deadline):工作最晚只能在自己的 deadline 或下一個已排工作開始前完成。- 再減去
duration:得到此工作的開始時間。
例如工作 (3, 10)、(2, 6):先把第一件放在 [7, 10],第二件最晚放在 [4, 6],中間可有空檔,整體最晚開始時間為 4。
若結果為負數,代表必須在時間 0 以前開始;若題目禁止,可能表示排程不可行。
複雜度: 排序 O(n log n),掃描 O(n)。
截止時間排程:Forward Sweep(EDF)
目標是選最多能在截止時間前完成的工作:按截止時間掃描;若超時,移除目前耗時最大的工作。
from heapq import heappop, heappush
def maximum_on_time_jobs(tasks):
total = 0
selected = []
for duration, deadline in sorted(tasks, key=lambda task: task[1]):
total += duration
heappush(selected, -duration)
if total > deadline:
total += heappop(selected)
return len(selected)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
目標是選最多能準時完成的工作。先按 deadline 由早到晚掃描,因為最早截止者最緊急。
每個工作先暫時加入:
total += duration
heappush(selected, -duration)
selected 用負值模擬最大堆。若累積時間超過目前 deadline,表示目前選擇無法全部準時完成,此時移除耗時最長的工作:
total += heappop(selected)
因為彈出的是負數,加回去等同從 total 扣除該 duration。移除最長工作能釋放最多時間,同時只少一個工作。
例如 (4, 4)、(3, 5)、(1, 5):加入前兩件後超時,移除耗時 4 的工作,之後可保留 3 和 1,共兩件。
複雜度: O(n log n)。
最小費用合併(Huffman/Min Cost Merge)
每次合併最小的兩堆,時間 O(n log n)。
from heapq import heapify, heappop, heappush
def minimum_merge_cost(sizes):
heap = sizes[:]
heapify(heap)
total = 0
while len(heap) > 1:
merged = heappop(heap) + heappop(heap)
total += merged
heappush(heap, merged)
return total
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
每次合併兩堆時,成本是兩堆大小之和;合併後的新堆還會參與後續合併。因此越早產生的大數,越可能被重複計費。
最佳策略是每次取最小的兩堆:
merged = heappop(heap) + heappop(heap)
把合併成本加入 total,再把新堆放回 heap。
例如 [1, 2, 7]:
先合併 1+2 = 3,成本 3
再合併 3+7 = 10,總成本 13
若先合併 2+7=9,再合併 1+9=10,總成本會是 19。
複雜度: 建 heap O(n),進行 n-1 次合併,每次 O(log n),總計 O(n log n)。
應用: Huffman 編碼、檔案合併、繩索連接問題。
<!-- END ALGORITHM EXPLANATION -->Multiset 貪心配對:最大匹配(Ticket Assignment)
對每個上限 limit,取不大於它的最大票價。排序陣列版刪除為 O(n),適合中等資料量。
def assign_tickets(prices, limits):
prices.sort()
answer = []
for limit in limits:
index = bisect_right(prices, limit) - 1
answer.append(prices.pop(index) if index >= 0 else -1)
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
對每位顧客的預算 limit,要出售「不超過預算的最高票價」。
index = bisect_right(prices, limit) - 1
bisect_right 找第一個大於 limit 的位置,往左一格就是最大合法票價。若 index < 0,代表所有票都太貴,答案為 -1。
配到票後要從可用票中刪除:
prices.pop(index)
例如票價 [5, 7, 8],顧客預算依序 [7, 8]:第一位拿 7,第二位拿 8。
為什麼不拿更便宜的 5?把 5 留給未來預算較低的顧客,通常能完成更多匹配。
複雜度: 二分是 O(log n),但串列中間刪除是 O(n),因此最壞 O(qn)。大資料需要真正的有序 multiset 或 Fenwick Tree。
Multiset 貪心配對:最小費用(Min Cost Matching)
排序後同序配對可最小化絕對差總和。
def minimum_absolute_matching(a, b):
if len(a) != len(b):
raise ValueError("two groups must have the same size")
return sum(abs(x - y) for x, y in zip(sorted(a), sorted(b)))
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
兩組元素數量相同,要一對一配對並最小化絕對差總和。將兩組各自排序後,同位置配對:
zip(sorted(a), sorted(b))
這樣不會出現交叉配對。若 a1 <= a2、b1 <= b2,將 a1 配 b2、a2 配 b1 不會比同序配對更好。
例如:
a = [1, 10]
b = [2, 9]
同序成本是 |1-2| + |10-9| = 2;交叉成本是 |1-9| + |10-2| = 16。
複雜度: 排序 O(n log n),配對加總 O(n)。
限制: 此模板要求兩組大小相同;若可略過元素或有額外限制,通常要改用 DP 或其他匹配方法。
<!-- END ALGORITHM EXPLANATION -->遞增陣列(Increasing Array)
只允許增加元素,使陣列成為非遞減;線性掃描即可。
def minimum_increments_to_nondecreasing(values):
moves = 0
current = -10**30
for value in values:
if value < current:
moves += current - value
else:
current = value
return moves
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
題目只允許增加元素,不能減少。current 保存處理到目前為止,下一個值至少必須達到的高度。
若 value < current,只能把它增加到 current:
moves += current - value
若 value >= current,不需要修改,並把新的基準更新成 value。
例如 [3, 2, 5, 1]:
3 保持 3
2 增加到 3,成本 1
5 保持 5
1 增加到 5,成本 4
總成本 5
最後陣列等價於 [3, 3, 5, 5]。
複雜度: O(n) 時間、O(1) 額外空間。
容易出錯: current 只在遇到更大值時更新;把小值補高後,基準仍是原本的 current。
集合等分(Set Partition)
把總和盡量平均分成兩組,可轉成容量為 sum(values) // 2 的 0/1 子集合和。
def minimum_partition_difference(values):
total = sum(values)
reachable = 1
for value in values:
reachable |= reachable << value
half = total // 2
best = max(i for i in range(half + 1) if (reachable >> i) & 1)
return total - 2 * best
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
設所有數總和為 total。若其中一組總和為 s,另一組就是 total - s,差值為:
total - 2*s
因此只需找不超過 total // 2 的最大可達子集合和。
reachable 是 bitset:第 s bit 為 1,代表能選出總和 s。
reachable |= reachable << value
把所有舊總和複製一份並加上 value,同時保留不選 value 的舊狀態。
例如 [1, 2, 4],總和 7,一半為 3;可達最大值是 3 = 1 + 2,所以最小差為 7 - 2*3 = 1。
複雜度: 從演算法觀點取決於總和 S;Python 大整數位元運算通常比逐格布林 DP 快很多。
限制: 此技巧直接適用非負整數;含負數時需位移索引或改用集合 DP。
<!-- END ALGORITHM EXPLANATION -->間隔覆蓋(Minimum Intervals to Cover Range)
要覆蓋 [target_left, target_right],每步從所有起點不晚於目前位置的區間中,選右端最遠者。
def minimum_cover(intervals, target_left, target_right):
intervals.sort()
i = 0
current = target_left
count = 0
while current < target_right:
farthest = current
while i < len(intervals) and intervals[i][0] <= current:
farthest = max(farthest, intervals[i][1])
i += 1
if farthest == current:
return -1
current = farthest
count += 1
return count
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
current 表示目前已保證覆蓋到的位置。每一輪把所有 start <= current 的區間納入候選,並找右端最遠的:
farthest = max(farthest, intervals[i][1])
選最遠右端可以讓每次使用的區間發揮最大效果,因而得到最少區間數。
若一輪結束後:
farthest == current
代表沒有任何區間能從目前位置繼續延伸,目標範圍無法完整覆蓋,回傳 -1。
例如要覆蓋 [0, 10],區間有 (0, 4)、(2, 8)、(4, 10):先從可用者選到 4,再考慮起點不超過 4 的區間,可直接延伸到 10。
複雜度: 排序 O(n log n),每個區間只掃一次,掃描 O(n)。
間距最小化(Gap Minimization)
在每段長度 gap 中可插入點,二分最小可能最大間距。required(max_gap) 必須隨 max_gap 單調不增。
def minimize_maximum_gap(points, extra_points):
points = sorted(points)
gaps = [b - a for a, b in zip(points, points[1:])]
def required(max_gap):
return sum((gap - 1) // max_gap for gap in gaps)
left, right = 1, max(gaps, default=0)
while left < right:
middle = (left + right) // 2
if required(middle) <= extra_points:
right = middle
else:
left = middle + 1
return left
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
答案具有單調性:如果最大間距 x 可行,那麼任何更大的間距也一定可行,因此可以二分答案。
對原本長度為 gap 的一段,若要求每小段最多 max_gap,需要插入:
(gap - 1) // max_gap
例如 gap = 10:
- 最大間距
5,插入1點,切成5 + 5。 - 最大間距
3,插入3點,切成不超過3的四段。
required(middle) <= extra_points 代表目前間距可行,可以嘗試更小答案;否則要放寬。
if required(middle) <= extra_points:
right = middle
else:
left = middle + 1
複雜度: 每次檢查 O(n),二分約 O(log max_gap) 次,總計 O(n log max_gap)。
PQ 貪心移除(Priority Queue Greedy Removal)
選最多工作且總耗時不超過限制:逐一加入最大堆,超限時移除最耗時者。
def maximum_tasks_within_time(durations, limit):
selected = []
total = 0
for duration in durations:
total += duration
heappush(selected, -duration)
if total > limit:
total += heappop(selected)
return len(selected)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
逐一把工作加入候選,total 保存目前總耗時,最大堆保存已選工作的 duration。
Python heapq 是最小堆,因此放入負值:
heappush(selected, -duration)
若 total > limit,代表目前選太多工作。為了只移除一件就釋放最多時間,應刪除耗時最長者:
total += heappop(selected)
彈出的是最大的 duration 的負值,所以加回 total 等同扣除它。
例如 durations [4, 2, 3]、限制 5:加入 4、2 後超限,移除 4,留下 2;再加入 3,剛好總耗時 5,共兩件。
複雜度: 每項最多進出 heap 一次,O(n log n)。
前提: 這種貪心適用「每件價值相同,只想選最多件」的情況。
<!-- END ALGORITHM EXPLANATION -->掃描線(Sweep Line)
半開區間 [start, end) 的同座標事件應先處理結束 -1,再處理開始 +1。
def maximum_overlap(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
active = answer = 0
for _, delta in sorted(events, key=lambda event: (event[0], event[1])):
active += delta
answer = max(answer, active)
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
每個區間 [start, end) 轉成兩個事件:
(start, +1) # 有一個區間開始
(end, -1) # 有一個區間結束
事件依座標排序後,active 就是目前同時存在的區間數,答案取歷史最大值。
同一座標時按 delta 排序,-1 會在 +1 前處理。這符合半開區間:在時間 t 結束的工作,和時間 t 開始的工作不算重疊。
例如 [1, 3) 和 [3, 5):座標 3 先执行 -1 再执行 +1,最大重疊仍是 1。
若題意使用閉區間 [start, end],同座標應先處理開始事件,排序規則要改。
複雜度: 建立 2n 個事件並排序,為 O(n log n);掃描 O(n)。
滑動中位數(Sliding Median)
雙堆加延遲刪除可達 O(n log k)。small 保存較小的一半(以負值模擬最大堆),large 保存較大的一半。
from collections import Counter
from heapq import heappop, heappush
def sliding_median(values, k):
small, large = [], []
delayed = Counter()
small_size = large_size = 0
def prune(heap, sign):
while heap and delayed[sign * heap[0]]:
value = sign * heappop(heap)
delayed[value] -= 1
def rebalance():
nonlocal small_size, large_size
if small_size > large_size + 1:
heappush(large, -heappop(small))
small_size -= 1
large_size += 1
prune(small, -1)
elif small_size < large_size:
heappush(small, -heappop(large))
small_size += 1
large_size -= 1
prune(large, 1)
def add(value):
nonlocal small_size, large_size
if not small or value <= -small[0]:
heappush(small, -value)
small_size += 1
else:
heappush(large, value)
large_size += 1
rebalance()
def remove(value):
nonlocal small_size, large_size
delayed[value] += 1
if value <= -small[0]:
small_size -= 1
if value == -small[0]:
prune(small, -1)
else:
large_size -= 1
if large and value == large[0]:
prune(large, 1)
rebalance()
answer = []
for i, value in enumerate(values):
add(value)
if i >= k:
remove(values[i - k])
if i + 1 >= k:
answer.append(-small[0])
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
程式用兩個 heap:
small:較小的一半,用負值模擬最大堆;-small[0]是中位數候選。large:較大的一半,使用一般最小堆。
平衡條件是 small 和 large 一樣大,或 small 多一個元素。故視窗長度為奇數時,中位數是 -small[0];偶數時此模板回傳較小的中位數。
heap 不支援任意位置刪除,所以 remove() 只在 delayed[value] 記帳。prune() 發現堆頂已被標記時,才真正彈出,稱為延遲刪除。
small_size、large_size 計算的是有效元素數,不包含等待刪除的舊元素。rebalance() 在兩堆間移動堆頂,恢復大小條件。
例如視窗 [1, 5, 2]:較小半可為 [1, 2],較大半為 [5],中位數是 2。
複雜度: 每個元素加入、移除與搬動均為 O(log k),總計 O(n log k);空間 O(k) 加延遲標記。
容易出錯: 有重複值時不能只用 set,必須用 Counter 記錄待刪數量。
搜尋與排序
Binary Search(二分搜)
找第一個使單調布林函式 check(x) 成立的整數:
def first_true(left, right, check):
"""答案必須存在於閉區間 [left, right]。"""
while left < right:
middle = (left + right) // 2
if check(middle):
right = middle
else:
left = middle + 1
return left
找最後一個成立者:
def last_true(left, right, check):
while left < right:
middle = (left + right + 1) // 2
if check(middle):
left = middle
else:
right = middle - 1
return left
已排序陣列可直接用 bisect_left(values, target) 找第一個 >= target 的位置,用 bisect_right 找第一個 > target 的位置。
拆解
二分搜答案要求 check(x) 具有單調性,例如:
False False False True True True
first_true() 要找第一個 True。每次取中點:
middle = (left + right) // 2
- 若
check(middle)成立,middle可能就是答案,但左側可能還有更小答案,所以令right = middle。 - 若不成立,答案一定在右側,令
left = middle + 1。
當 left == right 時只剩一個候選位置。
last_true() 找最後一個成立者,中點使用:
(left + right + 1) // 2
刻意向右取整,可避免只剩兩個數時 left 不再前進而形成無限迴圈。
例如最小可行容量為 7,搜尋 [0, 10],check(x) 為 x >= 7,first_true() 會得到 7。
複雜度: O(log(range)) 次 check()。
容易出錯: 必須先證明單調性,並確認答案一定存在於初始區間。
<!-- END ALGORITHM EXPLANATION -->Ternary Search(三分搜)
離散單峰函式求最小值;最後保留少量位置暴力比較。
def discrete_ternary_search(left, right, function):
while right - left >= 3:
third = (right - left) // 3
middle1 = left + third
middle2 = right - third
if function(middle1) > function(middle2):
left = middle1 + 1
else:
right = middle2 - 1
position = min(range(left, right + 1), key=function)
return position, function(position)
連續實數版本:
def real_ternary_search(left, right, function, iterations=100):
for _ in range(iterations):
middle1 = (2 * left + right) / 3
middle2 = (left + 2 * right) / 3
if function(middle1) > function(middle2):
left = middle1
else:
right = middle2
position = (left + right) / 2
return position, function(position)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
三分搜適用單峰或單谷函式。求最小值時,函式應先下降後上升。
離散版本在區間中取兩點:
middle1 = left + third
middle2 = right - third
若 function(middle1) > function(middle2),表示往右仍在下降,最小值不會位於最左側,可移動 left;否則移動 right。
離散整數可能有平台或相等區段,所以當候選範圍少於三格時,直接:
min(range(left, right + 1), key=function)
實數版本沒有「剩幾個整數」的概念,因此固定迭代約 100 次。每輪把區間縮成約 2/3,最後取中點。
複雜度: 離散版 O(log range) 次函式計算;實數版是 iterations 次。
容易出錯: 函式若有多個分離的局部極值,三分搜不保證找到全域最佳解。
<!-- END ALGORITHM EXPLANATION -->Two Pointers/Sliding Window(雙指標/滑動視窗)
排序後判斷三數和:
def three_sum_exists(values, target):
values = sorted(values)
n = len(values)
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
total = values[i] + values[left] + values[right]
if total == target:
return True
if total < target:
left += 1
else:
right -= 1
return False
最長不含重複元素子陣列:
def longest_distinct_subarray(values):
last_position = {}
left = 0
answer = 0
for right, value in enumerate(values):
if value in last_position:
left = max(left, last_position[value] + 1)
last_position[value] = right
answer = max(answer, right - left + 1)
return answer
最多含 k 種不同值的子陣列數量:
from collections import defaultdict
def count_subarrays_with_at_most_k_distinct(values, k):
frequency = defaultdict(int)
left = distinct = answer = 0
for right, value in enumerate(values):
if frequency[value] == 0:
distinct += 1
frequency[value] += 1
while distinct > k:
old = values[left]
frequency[old] -= 1
if frequency[old] == 0:
distinct -= 1
left += 1
answer += right - left + 1
return answer
兩人一組且總重不超過上限,求最少組數:
def minimum_pairs_with_limit(weights, limit):
weights.sort()
left, right = 0, len(weights) - 1
groups = 0
while left <= right:
if left < right and weights[left] + weights[right] <= limit:
left += 1
right -= 1
groups += 1
return groups
兩組數值在容許差 tolerance 內做最大匹配:
def maximum_close_matching(a, b, tolerance):
a.sort()
b.sort()
i = j = answer = 0
while i < len(a) and j < len(b):
if b[j] < a[i] - tolerance:
j += 1
elif b[j] > a[i] + tolerance:
i += 1
else:
answer += 1
i += 1
j += 1
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
本節有五種常見模式。
1. 三數和
先排序並固定 i,再用 left、right 夾逼:總和太小就增加左端,太大就減少右端。每個固定 i 只需線性掃描,因此總時間 O(n²)。
2. 最長無重複子陣列
last_position[value] 保存某值上次出現位置。若重複,左端至少跳到上次位置的下一格:
left = max(left, last_position[value] + 1)
max 很重要,避免左端倒退。
3. 最多 k 種不同值的子陣列數
右端每加入一個值就更新頻率;種類數超過 k 時移動左端。窗口合法後,以 right 結尾的合法子陣列共有 right - left + 1 個。
4. 兩人一組且重量有限
每輪最重者一定要佔一組;若能和最輕者搭配就一起帶走,否則最重者單獨一組。
5. 容許誤差的一對一匹配
兩組排序後,哪一側值太小就移動哪一側;落在容許範圍內就同時配對並前進。
例如無重複窗口處理 [1, 2, 1, 3]:看到第二個 1 時,left 從 0 跳到 1,最後最長窗口 [2, 1, 3] 長度為 3。
共同重點: 指標只向前走、不回頭,通常能把雙層暴力降成 O(n);需要排序的版本則另加 O(n log n)。
Meet in the Middle(折半搜尋)
把 n 個元素分半,枚舉兩側子集合和,常把 O(2ⁿ) 降為 O(2^(n/2)) 等級。
from collections import Counter
def subset_sums(values):
sums = [0]
for value in values:
sums += [current + value for current in sums]
return sums
def count_subsets_with_sum(values, target):
middle = len(values) // 2
left_counts = Counter(subset_sums(values[:middle]))
return sum(left_counts[target - right] for right in subset_sums(values[middle:]))
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
直接枚舉 n 個元素所有子集合要 2**n 次。折半搜尋把陣列切成左右兩半,各自只需約 2**(n/2) 個子集合。
subset_sums() 從只有空集合和 0 開始:
sums = [0]
加入新值時,將所有既有總和各加上它,再接回原串列:
sums += [current + value for current in sums]
這同時代表「不選」和「選」目前元素。
左半總和使用 Counter 計數,因為不同子集合可能產生相同總和。對每個右半總和 right,需要左半補出 target - right:
left_counts[target - right]
例如 [1, 2, 3, 4]、目標 5,可找到 {1,4}、{2,3} 等組合。
複雜度: 約 O(2^(n/2)) 時間與空間;通常適合 n 約 40 左右而數值範圍很大的題目。
Merge Sort:Inversion Count(逆序對計數)
def inversion_count(values):
def sort_and_count(array):
if len(array) <= 1:
return array, 0
middle = len(array) // 2
left, left_count = sort_and_count(array[:middle])
right, right_count = sort_and_count(array[middle:])
merged = []
i = j = 0
count = left_count + right_count
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
count += len(left) - i
merged.extend(left[i:])
merged.extend(right[j:])
return merged, count
return sort_and_count(values)[1]
Fenwick Tree 版本(先離散化):
def inversion_count_fenwick(values):
ranks = {value: rank for rank, value in enumerate(sorted(set(values)))}
bit = FenwickTree(len(ranks))
answer = 0
for value in reversed(values):
rank = ranks[value]
answer += bit.prefix_sum(rank)
bit.add(rank, 1)
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
逆序對是 i < j 但 values[i] > values[j] 的索引對。
合併排序版本先遞迴把左右兩半排序。合併時若:
left[i] > right[j]
因為左半已排序,所以 left[i:] 的所有元素都比 right[j] 大,一次增加:
len(left) - i
例如左半 [2, 5, 7]、右半目前值 3,5、7 都和 3 形成逆序對,一次加 2。
Fenwick 版本先把值離散化成排名,再由右往左掃。已插入的元素都位於目前位置右側:
bit.prefix_sum(rank)
計算已插入且排名較小的數量,也就是目前元素形成的逆序對數。
使用 sorted(set(values)) 可讓相同值取得相同排名;相等元素不算逆序對。
複雜度: 兩個版本皆為 O(n log n) 時間、O(n) 空間。
數學
Fast Exponentiation(快速冪)
Python 內建 pow(base, exponent, modulus) 已使用快速冪。手寫版本如下,時間 O(log exponent)。
def mod_power(base, exponent, modulus):
result = 1
base %= modulus
while exponent:
if exponent & 1:
result = result * base % modulus
base = base * base % modulus
exponent >>= 1
return result
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
指數用二進位表示。例如 13 = 8 + 4 + 1,不必把底數乘 13 次,只需反覆平方。
if exponent & 1:
result = result * base % modulus
若目前最低 bit 是 1,就把這一位代表的冪乘進答案。
base = base * base % modulus
exponent >>= 1
底數平方,代表從 base^1 依序變成 base^2、base^4、base^8...;指數右移一位,繼續處理下一個 bit。
例如 3^13 會組合 3^1 × 3^4 × 3^8。
每次乘法後立即 % modulus,可保持數字較小;Python 雖不會整數溢位,但大整數乘法仍會變慢。
複雜度: O(log exponent) 時間、O(1) 空間。
Python 內建: 實務上可直接使用 pow(base, exponent, modulus)。
Sieve of Eratosthenes(埃氏篩)
時間約 O(n log log n),空間 O(n)。
def prime_sieve(limit):
is_prime = bytearray(b"\x01") * (limit + 1)
if limit >= 0:
is_prime[0] = 0
if limit >= 1:
is_prime[1] = 0
for prime in range(2, int(limit**0.5) + 1):
if is_prime[prime]:
start = prime * prime
is_prime[start:limit + 1:prime] = b"\x00" * (((limit - start) // prime) + 1)
primes = [number for number in range(2, limit + 1) if is_prime[number]]
return primes, is_prime
最小質因數篩,方便快速質因數分解:
def smallest_prime_factors(limit):
spf = list(range(limit + 1))
for prime in range(2, int(limit**0.5) + 1):
if spf[prime] == prime:
for multiple in range(prime * prime, limit + 1, prime):
if spf[multiple] == multiple:
spf[multiple] = prime
return spf
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
埃氏篩先假設 0..limit 都是質數,再把 0、1 標成非質數。
若 prime 尚未被劃掉,它就是質數;其倍數都不是質數。從:
start = prime * prime
開始即可,因為更小倍數早已被較小質數處理。
is_prime[start:limit + 1:prime] = b"\x00" * count
這是 Python 的切片批次賦值,一次把所有倍數設成 0,通常比 Python 層的逐項迴圈快。
第二段最小質因數篩 spf[x] 保存 x 最小的質因數。分解 x 時可反覆取 spf[x] 並令 x //= spf[x]。
例如 spf[84] = 2,除後得到 42,再取 2、3、7,所以 84 = 2² × 3 × 7。
複雜度: 埃氏篩約 O(n log log n),空間 O(n)。
Factorial Trailing Zeros(階乘尾零)
十進位尾零來自因數 10 = 2 × 5;階乘中 2 較多,只需計算 5 的次方貢獻。
def factorial_trailing_zeros(n):
answer = 0
while n:
n //= 5
answer += n
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
十進位尾零由因數 10 = 2 × 5 產生。n! 中因數 2 遠多於 5,所以只需計算總共有幾個因數 5。
n //= 5
answer += n
第一次加上 5 的倍數數量;第二次加上 25 的倍數額外提供的第二個 5;之後還有 125、625...。
例如 n = 100:
100 // 5 = 20
100 // 25 = 4
總計 24 個尾零
程式透過反覆把 n 除以 5 得到同樣結果。
複雜度: O(log₅ n) 時間、O(1) 空間。
容易出錯: 不能只算 n // 5,因為 25、125 等數字含有不只一個因數 5。
Kadane's Algorithm(最大子陣列和)
可正確處理全負數陣列,時間 O(n)。
def maximum_subarray_sum(values):
if not values:
raise ValueError("values must not be empty")
ending_here = answer = values[0]
for value in values[1:]:
ending_here = max(value, ending_here + value)
answer = max(answer, ending_here)
return answer
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
ending_here 表示「一定以目前位置結尾」的最大子陣列和。加入新值時只有兩種選擇:
ending_here = max(
value, # 從目前位置重新開始
ending_here + value # 接在前一段後面
)
answer 保存所有位置的最佳結果。
例如 [4, -6, 3, 2]:
4:ending = 4,answer = 4
-6:ending = -2,answer = 4
3:重新開始,ending = 3
2:接上去,ending = 5,answer = 5
最佳子陣列是 [3, 2]。
初始值使用 values[0] 而不是 0,所以全負數陣列也能正確回傳最大單一元素。例如 [-5, -2] 的答案是 -2。
複雜度: O(n) 時間、O(1) 額外空間。
前綴和
1D Prefix Sum(一維前綴和)
prefix[i] 表示前 i 個值的總和,區間 [left, right) 為 prefix[right] - prefix[left]。
from itertools import accumulate
values = [3, 1, 4, 1, 5]
prefix = [0, *accumulate(values)]
def range_sum_1d(prefix, left, right):
return prefix[right] - prefix[left]
差分陣列可做多次區間加值:
def range_additions(n, updates):
difference = [0] * (n + 1)
for left, right, delta in updates: # [left, right)
difference[left] += delta
difference[right] -= delta
result = []
current = 0
for i in range(n):
current += difference[i]
result.append(current)
return result
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
prefix = [0, *accumulate(values)]
前面的 0 代表取零個元素的總和。若 values = [3, 1, 4]:
prefix = [0, 3, 4, 8]
半開區間 [left, right) 的總和是:
prefix[right] - prefix[left]
因為前 right 個元素的總和減掉前 left 個,就只剩中間區間。例如 [1, 3) 為 8 - 3 = 5,對應 1 + 4。
第二段差分陣列用於多次區間加值。對 [left, right) 加 delta:
difference[left] += delta
difference[right] -= delta
最後做一次前綴累加,就能還原每個位置實際增加多少。
複雜度: 建前綴和 O(n),每次區間查詢 O(1);差分每次更新 O(1),最後還原 O(n)。
2D Prefix Sum(二維前綴和)
矩形採半開座標 [top, bottom) × [left, right);建表 O(rows × columns),查詢 O(1)。
class PrefixSum2D:
def __init__(self, matrix):
rows, columns = len(matrix), len(matrix[0])
self.prefix = [[0] * (columns + 1) for _ in range(rows + 1)]
for row in range(rows):
row_sum = 0
for column in range(columns):
row_sum += matrix[row][column]
self.prefix[row + 1][column + 1] = self.prefix[row][column + 1] + row_sum
def query(self, top, left, bottom, right):
p = self.prefix
return p[bottom][right] - p[top][right] - p[bottom][left] + p[top][left]
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
prefix[r][c] 表示原矩陣左上角到 (r-1, c-1) 的矩形總和,也就是前 r 列、前 c 欄。
建表時 row_sum 保存目前這一列從第 0 欄累加到當前欄的總和:
self.prefix[row + 1][column + 1] = self.prefix[row][column + 1] + row_sum
上方矩形加目前列片段,就得到新的左上矩形。
查詢 [top, bottom) × [left, right) 使用容斥:
大矩形
- 上方
- 左方
+ 被重複減掉的左上角
對應程式:
p[bottom][right] - p[top][right] - p[bottom][left] + p[top][left]
複雜度: 建表 O(rows × columns)、查詢 O(1)、空間 O(rows × columns)。
容易出錯: 前綴表多一列一欄的 0,可省掉邊界特判;查詢座標採半開區間。
3D Prefix Sum(三維前綴和)
長方體查詢使用三維容斥;以下座標皆為半開區間。
class PrefixSum3D:
def __init__(self, data):
x_size, y_size, z_size = len(data), len(data[0]), len(data[0][0])
self.prefix = [
[[0] * (z_size + 1) for _ in range(y_size + 1)]
for _ in range(x_size + 1)
]
p = self.prefix
for x in range(1, x_size + 1):
for y in range(1, y_size + 1):
for z in range(1, z_size + 1):
p[x][y][z] = (
data[x - 1][y - 1][z - 1]
+ p[x - 1][y][z] + p[x][y - 1][z] + p[x][y][z - 1]
- p[x - 1][y - 1][z] - p[x - 1][y][z - 1]
- p[x][y - 1][z - 1] + p[x - 1][y - 1][z - 1]
)
def query(self, x1, y1, z1, x2, y2, z2):
p = self.prefix
return (
p[x2][y2][z2]
- p[x1][y2][z2] - p[x2][y1][z2] - p[x2][y2][z1]
+ p[x1][y1][z2] + p[x1][y2][z1] + p[x2][y1][z1]
- p[x1][y1][z1]
)
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
三維前綴和把二維容斥擴充到三個軸。prefix[x][y][z] 表示座標原點到 (x-1, y-1, z-1) 的長方體總和。
建表時:
- 加入三個方向的面:
x-1、y-1、z-1。 - 減掉三個被重複加入的交叉區域。
- 加回被前一步多減的共同交集。
查詢長方體 [x1,x2) × [y1,y2) × [z1,z2) 也遵循相同的三維容斥,共有 2³ = 8 個角落項。
理解符號的方法:每個下界被選用一次就改變一次正負號。最右上後角 p[x2][y2][z2] 為正;含一個下界的三項為負;含兩個下界的三項為正;三個下界全含時為負。
複雜度: 建表 O(XYZ)、每次查詢 O(1)、空間 O(XYZ)。
建議: 先熟悉二維容斥,再記三維版本;大型三維陣列很耗記憶體。
<!-- END ALGORITHM EXPLANATION -->其他技巧
Permutation(排列枚舉)
itertools.permutations 會把相同值的不同位置視為不同,因此輸入有重複值時可能產生重複排列。
from itertools import permutations
for arrangement in permutations([1, 2, 3]):
print(arrangement)
# 去除重複排列(小資料適用)
unique = set(permutations([1, 1, 2]))
手寫下一個字典序排列:
def next_permutation(values):
i = len(values) - 2
while i >= 0 and values[i] >= values[i + 1]:
i -= 1
if i < 0:
values.reverse()
return False
j = len(values) - 1
while values[j] <= values[i]:
j -= 1
values[i], values[j] = values[j], values[i]
values[i + 1:] = reversed(values[i + 1:])
return True
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
permutations([1, 2, 3]) 會產生所有 3! = 6 種排列,而且每個結果是 tuple。
若輸入有重複值,例如 [1, 1, 2],兩個 1 的位置仍被視為不同,因此會產生重複 tuple。小資料可用:
set(permutations([1, 1, 2]))
去重,但會額外使用記憶體。
next_permutation() 產生下一個字典序排列:
- 從右找第一個
values[i] < values[i+1]的轉折點。 - 從右找第一個大於
values[i]的值並交換。 - 把
i右側反轉成最小順序。
例如 [1, 3, 2]:轉折點是 1,和右側大於它的最小候選 2 交換,再反轉尾端,得到 [2, 1, 3]。
若整列已是遞減,代表沒有下一個排列;函式把它反轉成最小排列並回傳 False。
複雜度: 單次 next_permutation() 為 O(n);枚舉全部排列必然是 O(n! × n)。
Gray Code(格雷碼)
相鄰兩個碼只差一個 bit;第 i 個 Gray code 是 i ^ (i >> 1)。
def gray_codes(bits):
return [format(i ^ (i >> 1), f"0{bits}b") for i in range(1 << bits)]
def gray_to_binary(gray):
value = 0
while gray:
value ^= gray
gray >>= 1
return value
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
Gray Code 的特性是相鄰兩個值的二進位表示只改變一個 bit。
第 i 個 Gray Code:
i ^ (i >> 1)
例如 2-bit:
i: 00 01 10 11
Gray:00 01 11 10
相鄰結果分別只改一位。
format(value, f"0{bits}b") 會輸出固定 bits 位,不足的左側補 0。
gray_to_binary() 反向轉換時,將 Gray Code 與其不斷右移的版本 XOR:
value ^= gray
gray >>= 1
直到 gray 變成 0。
複雜度: 產生全部 bits 位 Gray Code 需要 O(2^bits) 個結果;單次轉換為 O(bits)。
應用: 位元狀態枚舉、旋轉編碼器、希望相鄰狀態只變一個 bit 的問題。
<!-- END ALGORITHM EXPLANATION -->Fast Hash(防 hack 雜湊)
Python 的 str、bytes 雜湊預設每個行程隨機化;整數雜湊則較可預測。一般題目直接用 dict/set 即可。若平台刻意構造整數碰撞,可用隨機遮罩包裝鍵:
import secrets
_HASH_MASK = secrets.randbits(64)
def protected_key(value):
return value ^ _HASH_MASK
frequency = {}
value = 123456789
key = protected_key(value)
frequency[key] = frequency.get(key, 0) + 1
若之後需要還原原值,XOR 同一遮罩即可。
<!-- BEGIN ALGORITHM EXPLANATION -->拆解
Python 的 dict 和 set 平均查詢是 O(1),但極端碰撞可能退化。字串與 bytes 的雜湊通常已有每個行程隨機化;整數雜湊較直接。
_HASH_MASK = secrets.randbits(64)
建立每次執行都不同的 64-bit 遮罩。存入整數鍵前:
protected = value ^ _HASH_MASK
XOR 會可逆地打亂鍵值。若需要還原:
original = protected ^ _HASH_MASK
因為同一遮罩 XOR 兩次會回到原值。
此技巧主要用來避免有人針對可預測整數鍵安排惡意輸入。一般競程題直接使用原始整數作為 dict key 通常已足夠。
複雜度: 每次轉換 O(1)。
注意: 這不是密碼學加密,也不會改善演算法本身的錯誤複雜度。
<!-- END ALGORITHM EXPLANATION -->四數之和(Hash)
計算 a + b + c + d = target 的四元組數量;時間 O(n²)、空間 O(n²)。
from collections import Counter
def four_sum_count(a, b, c, d, target=0):
left_sums = Counter(x + y for x in a for y in b)
return sum(left_sums[target - z - w] for z in c for w in d)
同一陣列找四個不同索引,可在掃描中只把已位於目前兩索引左側的 pair 放入表:
def four_distinct_indices(values, target):
pair = {}
n = len(values)
for j in range(1, n):
for k in range(j + 1, n):
needed = target - values[j] - values[k]
if needed in pair:
i, h = pair[needed]
return i, h, j, k
for i in range(j):
pair.setdefault(values[i] + values[j], (i, j))
return None
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
第一段處理四個陣列。先枚舉所有 a + b 並用 Counter 記錄次數:
left_sums = Counter(x + y for x in a for y in b)
再枚舉 c + d。若四數總和要等於 target,左半需要:
target - z - w
Counter 的值是方法數,所以直接累加即可。
第二段要在同一陣列找四個不同索引。掃描到 (j, k) 時,pair 只保存結束索引小於 j 的舊 pair,因此找到的 (i, h, j, k) 天然互不重疊。
先查詢目前 j、k,查完後才把 (i, j) 放入表,順序不能反過來。
例如 [2, 7, 4, 0, 9]、目標 13,可找到 2 + 7 + 4 + 0 = 13。
複雜度: 兩種版本皆約 O(n²) 時間、O(n²) 空間,比四層暴力 O(n⁴) 快很多。
Josephus Problem(約瑟夫問題)
最後存活者的 0-indexed 編號可用 O(n) 遞推求得。
def josephus_survivor(n, step):
survivor = 0
for size in range(2, n + 1):
survivor = (survivor + step) % size
return survivor
需要完整淘汰順序且 n 較小時:
from collections import deque
def josephus_order(n, step):
people = deque(range(n))
order = []
while people:
people.rotate(-(step - 1))
order.append(people.popleft())
return order
<!-- BEGIN ALGORITHM EXPLANATION -->
拆解
josephus_survivor() 只求最後存活者。假設已知道人數 size - 1 時的答案,加入第 size 個人後,因為第一輪會向前移動 step,新答案為:
survivor = (survivor + step) % size
從只有一人時答案 0 開始,逐步推到 n 人。
例如 n = 5、step = 2:
size 1:0
size 2:(0+2)%2 = 0
size 3:(0+2)%3 = 2
size 4:(2+2)%4 = 0
size 5:(0+2)%5 = 2
最後存活者是 0-indexed 的 2,若題目編號從 1 開始要再加 1。
完整淘汰順序版本使用 deque。每輪:
people.rotate(-(step - 1))
把即將被淘汰的人轉到左端,再 popleft()。
複雜度: 只求存活者為 O(n) 時間、O(1) 空間;deque 模擬會受旋轉距離影響,適合較小資料。
Pragma 加速:Python 對應做法
C++ 的 #pragma GCC optimize 沒有 Python 等價語法。競程中應優先做以下調整:
- 使用正確的時間複雜度;這比任何微調都重要。
- 大量輸入使用
sys.stdin.buffer.read(),輸出先收集再"\n".join(...)。 - 熱迴圈內把常用方法綁到區域變數,例如
push = heapq.heappush。 - 避免在迴圈內反覆切片、建立大型暫存串列或使用深遞迴。
- 位元集合適合用 Python 任意精度整數,例如子集合和的
bits |= bits << value。 - 若評測允許,可使用 PyPy;但含大量物件或特殊套件時 CPython 可能較合適。
快速 I/O 完整骨架:
import sys
def solve(data):
iterator = iter(data)
n = int(next(iterator))
values = [int(next(iterator)) for _ in range(n)]
return str(sum(values))
if __name__ == "__main__":
tokens = sys.stdin.buffer.read().split()
sys.stdout.write(solve(tokens))
<!-- BEGIN PRAGMA EXPLANATION -->
快速 I/O 完整骨架拆解
程式進入點先讀取所有輸入:
tokens = sys.stdin.buffer.read().split()
結果是由 bytes 組成的串列,例如輸入 3\n10 20 30\n 會變成:
[b'3', b'10', b'20', b'30']
接著把整份資料傳給 solve(tokens)。在 solve() 內:
iterator = iter(data)
將串列轉成 iterator。next(iterator) 每次取出一個 bytes;int() 可以直接把 b'10' 轉成整數 10,不必先呼叫 .decode()。
n = int(next(iterator))
values = [int(next(iterator)) for _ in range(n)]
第一個數字是資料筆數 n,接著恰好讀取 n 個值。若輸入提供的數字不足,next() 會拋出 StopIteration,通常表示輸入格式或讀取數量寫錯。
solve() 回傳字串:
return str(sum(values))
最後使用:
sys.stdout.write(solve(tokens))
一次輸出結果。sys.stdout.write() 不會自動補換行;需要換行時可改成:
sys.stdout.write(solve(tokens) + "\n")
若要輸出很多行,先收集字串再一次寫出:
answers = ["10", "20", "30"]
sys.stdout.write("\n".join(answers))
這樣能減少大量小型輸出呼叫。
適用時機: 輸入資料量很大,而且格式主要由空白分隔的整數組成。
注意: buffer.read() 已把輸入全部取走,後續不要再混用 input();若題目需要逐行保留空白或讀取含空格字串,也不適合直接全部 .split()。
常見移植差異與陷阱
- C++
long long對應 Pythonint;Python 整數不會固定寬度溢位。 - C++ 整數除法向
0截斷;Python//向負無限取整。負數題目須確認規格。 - C++
lower_bound/upper_bound對應bisect_left/bisect_right。 - C++ 最大堆
priority_queue對應 Pythonheapq的負值技巧;Python 3.14+ 才另有 max-heap API。 - C++
set/map有序;Pythonset無序,dict保留插入順序但不按鍵排序。 - Python 標準庫缺少平衡樹 multiset。高頻任意刪除、前驅與後繼查詢可用座標壓縮 + Fenwick Tree,或在規則允許時使用
sortedcontainers。 - 建立二維陣列要用
[[0] * m for _ in range(n)],不可用[[0] * m] * n,否則每列會指向同一物件。 - Dijkstra 僅適用非負權;拓撲排序只適用 DAG;Sparse Table 的
O(1)重疊查詢需要冪等運算。 - 半開區間
[left, right)最貼近 Python 的range、切片與bisect,可減少邊界錯誤。
來源架構:郭10的 Blog:演算法、資料結構模板。本文件為 Python 重新實作版,最後整理日期:2026-08-11。