本篇文章是转专业机考前抱佛脚所写，可能有点马虎和功利。

itertools 全排列和全组合

combinations和permutations两者都是itertools中的函数，可以实现生成字符串、字典、列表，元组中的排列和组合后的元素，形式为元组。先从itertools中引入。

1
2
3
4
5
6
7
8
9
from itertools import combinations,permutations
# 语法为combinations(iterable,元素个数)——
# permutation中，元素个数不写则默认为全部
n,m = map(int,input().split())
l = [str(x) for x in range(1,n+1)]
for i in combinations(l,m):
    print(' '.join(i))#全组合
for j in permutations(l):
    print(' '.join(j))#全排列

另外，全排列和全组合也可以通过dfs实现

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
def dfs(u):#全排列
    if u == n:
        for i in range(n):
            if state[i] == 1:
                print(i+1,end = ' ')
        print()
        return
    dfs(u+1)
    state[u] = 1
    dfs(u+1)
    state[u] = 0

def dfs2(x):#全组合
    if x == m:
        for i in range(m):
                print(res[i],end = ' ')
        print()
        return
    for j in range(n):
        if state[j] == 0 and (j + 1 > res[x-1] or x == 0):
            res[x] = j + 1
            state[j] = 1
            dfs2(x+1)
            state[j] = 0
n,m = map(int,input().split())            
res = [0]*m
state = [0]*n 
dfs2(0)

functools_排序

cmp_to_key将比较函数改为key函数

1
2
3
4
5
6
7
8
9
import functools
def compare(a,b):
    if a > b:
        return 1 # 1表示调换顺序
    else:
        return -1
arr = [1,3,4,2]
arr.sort(key=functools.cmp_to_key(compare))
# arr:[1,2,3,4]

collections

  1. deque

    用于实现单调队列和双端队列

1
2
3
4
5
6
from collections import deque
q = deque()
q.append()
q.pop()
q.popleft()

  1. defautdict

    初始化字典，免去了初始赋值

    1
    2
    3
    4
    from collections import defaultdict
    d = defaultdict(int)# 初始化类型,int,str,list...
    print(d)
    # defaultdict(<class 'int'>, {})

计算相关

最大公约数和最小公倍数

math库提供了gcd函数用于求最大公约数：

1
2
3
4
from math import gcd
a = gcd(1,12)
print(a)
# 1

对于最小公倍数，由于lcm和gcd存在以下关系，
$$
LCM(a, b) = abs(ab) // GCD(a, b)
$$

1
2
3
from math import gcd
a = gcd(3,4)
lcm = (3*4) // a

约分化简

1
2
3
from fractions import Fraction
print(Fraction(1,12)+Fraction(2,12))
# 1/4 输出格式可以转成string后再操作