优先队列

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
"""
[7,6,5,4,3,2,1]
 0,1,2,3,4,5,6
[1,2,3,4,5,6,7]
                    1
        2                       3
4               5       6               7

-----------------------------------
优先队列：

优先队列由堆建成（小根堆）
有插入，弹出，上滤，下滤等操作；
插入以及弹出均为    (logn)
上滤以及下滤同样为   (logn)
-----------------------------------

-----------------------------------
插入：

1. item从堆的顶部进入，然后使用下滤操作

2. item从堆的底部进入，然后使用上滤操作
-----------------------------------

-----------------------------------
弹出：

1. 小根堆从堆顶部弹出最小元素

2. 大根堆从堆顶部弹出最大元素

将底部元素移动到堆顶，然后下滤
-----------------------------------

-----------------------------------
上滤：

1. 大根堆
    1. 比父节点大 -> 交换位置
    2. 比父节点小 -> 不交换位置

2. 小根堆
    1. 比父节点大 -> 不交换位置
    2. 比父节点小 -> 交换位置
-----------------------------------

-----------------------------------
下滤：

1. 大根堆
    · 取孩子树下标对应值最大的下标
    1. 比孩子树大 -> 不交换位置
    2. 比孩子树小 -> 交换位置

2. 小根堆
    · 取孩子树下标对应值最大的下标
    1. 比孩子树大 -> 交换位置
    2. 比孩子树小 -> 不交换位置

-----------------------------------
"""

代码实现：

小根堆

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 入队
def heappush(heap: list, item):
    heap.append(item)
    # 堆顶是列表的尾巴heap[-1]，堆底部是列表的头heap[0]
    _siftdown(heap, 0, len(heap) - 1)


# 弹出
def heappop(heap):
    lastitem = heap.pop()
    if heap:
        # 获取要弹出的元素
        returnitem = heap[0]
        # 堆底放到堆顶
        heap[0] = lastitem
        # 堆顶元素下滤
        _siftup(heap, 0)
        # 返回弹出的元素
        return returnitem
    return lastitem


# 下滤
def _siftdown(heap: list, startpos, pos):
    # 要添加的元素
    newitem = heap[pos]
    while pos > startpos:
        # 父节点下标
        parentpos = (pos - 1) >> 1
        # 父节点值
        parent = heap[parentpos]
        # 父节点值大于新值，节点要下移，同时新值要上移
        if parent >= newitem:
            heap[pos] = heap[parentpos]
            pos = parentpos
            continue
        break
    heap[pos] = newitem


# 上滤
def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # 左孩子下标
    childpos = pos * 2 + 1
    while childpos < endpos:
        # 右孩子下标
        rightpos = childpos + 1
        # 左右孩子取值最小的
        if rightpos < endpos and heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = pos * 2 + 1
    heap[pos] = newitem
    # 调整父节点
    _siftdown(heap, startpos, pos)

大根堆

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 入队
def heappush(heap: list, item):
    heap.append(item)
    # 堆顶是列表的尾巴heap[-1]，堆底部是列表的头heap[0]
    _siftdown(heap, 0, len(heap) - 1)


# 弹出
def heappop(heap):
    lastitem = heap.pop()
    if heap:
        # 获取要弹出的元素
        returnitem = heap[0]
        # 堆底放到堆顶
        heap[0] = lastitem
        # 堆顶元素下滤
        _siftup(heap, 0)
        # 返回弹出的元素
        return returnitem
    return lastitem


# 下滤
def _siftdown(heap: list, startpos, pos):
    # 要添加的元素
    newitem = heap[pos]
    while pos > startpos:
        # 父节点下标
        parentpos = (pos - 1) >> 1
        # 父节点值
        parent = heap[parentpos]
        # 父节点值小于新值，节点要下移，同时新值要上移
        if parent <= newitem:
            heap[pos] = heap[parentpos]
            pos = parentpos
            continue
        break
    heap[pos] = newitem


# 上滤
def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # 左孩子下标
    childpos = pos * 2 + 1
    while childpos < endpos:
        # 右孩子下标
        rightpos = childpos + 1
        # 左右孩子取值最大的
        if rightpos < endpos and heap[rightpos] > heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = pos * 2 + 1
    heap[pos] = newitem
    # 调整父节点
    _siftdown(heap, startpos, pos)

回溯算法

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
	if (终止条件) {
		存放结果;
		return;
    }
    for (选择: 本层集合中的元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径，选择列表);
        回溯，撤销处理结果
    }
}

动态规划(DP)

数位DP

1
2
3
4
5
6
7
8
9
10
11
12
f(i: int, mask: int, is_limit: bool, is_nums: bool):
    if i == len(s):
        return int(is_nums)
    res = 0
    if not is_nums:
        res = f(i + 1, mask, False, False)
    low = 0 if is_nums else 1
    up = int(s[i]) if is_limit else 9
    for d in range(low, up + 1):
        if mask >> d & 1 == 0:
            res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
    return res

快速幂

1
2
3
4
5
6
7
8
9
def fast_pow(a, n, mod):
    ans = 1
    # ans %= mod  C++ 这里需要取模，因为防止溢出
    while n:
        if n & 1:
            ans = (ans * a) % mod
        a = a * a % mod
        n >>= 1
    return ans