那些你不能不知道的東西

建表

1
2
3
4
5
6
7
8
9
one_d = [0]*4
two_d = [[0]*4 for _ in range(3)]
print(one_d)
print(two_d)
# 輸出: [0, 0, 0, 0]

# 輸出: [[0, 0, 0, 0],
# [0, 0, 0, 0],
# [0, 0, 0, 0]]

Lambda

1
2
3
4
5
arr = [[1, 5], [2, 3], [1, 2]]
arr.sort(key=lambda x: (x[0], -x[1]))
print(arr)
# 輸出: [[1, 5], [1, 2], [2, 3]]
# 第一列升序,第二列降序

埃氏篩

1
2
3
4
5
6
7
8
def sieve(n):
a = [True] * (n+1)
a[0] = a[1] = False
for i in range(2, int(n**0.5)+1):
if a[i]:
for j in range(i*i, n+1, i):
a[j] = False
return [i for i in range(n+1) if a[i]]

Itertools 排列組合

1
2
3
4
5
6
7
8
9
10
import itertools

itertools.permutations 所有排列
#(A,B), (B,A), (A,C), (C,A), (B,C), (C,B)
itertools.combinations 所有組合
#(A,B), (A,C), (B,C)
combinations_with_replacement 所有組合可重複
#(A,A), (A,B), (A,C), (B,B), (B,C), (C,C)

#記得都要用for x in combinations(可疊代,數量)去做

圖論之建圖(defaultdict)

1
2
3
4
5
6
7
8
from collections import defaultdict
n, m = map(int, input().split())
g = defaultdict(list)

for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u) #無向圖要加這行

圖論之BFS

1
2
3
4
5
6
7
8
9
10
def dfs(start):
queue = [start]
vis = {start}

while queue:
x = queue.pop(0) # 先進先出
for i in g[x]:
if i not in vis:
vis.add(i)
queue.append(i)

圖論之DFS

1
2
3
4
5
6
7
8
9
10
def dfs(start):
stack = [start]
vis = {start}

while stack:
x = stack.pop() # 後進先出
for i in g[x]:
if i not in vis:
vis.add(i)
stack.append(i)

DP之最少最少硬幣數量

1
2
3
4
5
6
7
8
9
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for i in range(1, amount + 1):
for c in coins:
if i - c >= 0:
dp[i] = min(dp[i], dp[i - c] + 1)

print(dp[amount])

DP之硬幣組合數量

1
2
3
4
5
6
7
8
dp = [0] * (amount + 1)
dp[0] = 1

for c in coins:
for i in range(c, amount + 1):
dp[i] += dp[i - c]

print(dp[amount])

DP之0-1背包(每個物品一次)

1
2
3
4
5
6
7
dp = [0]*(W+1)

for i in range(len(weights)):
for w in range(W, weights[i]-1, -1):
dp[w] = max(dp[w], dp[w-weights[i]] + values[i])

print(dp[W])

DP之完全背包(每個物品無限次)

1
2
3
4
5
6
7
dp = [0]*(W+1)

for i in range(len(weights)):
for w in range(weights[i], W+1):
dp[w] = max(dp[w], dp[w-weights[i]] + values[i])

print(dp[W])