数据结构和算法模板

并查集

Java

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
class UnionFind {
	private int[] parent; // 每个节点的parent域指向其父节点的下标。其实就是树的双亲表示法

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始时每个节点都是自己的根节点，自成一树
        }
    }

    // 将返回下标为x的节点的根节点的下标
    // 在find的过程中进行路径压缩
    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // 这行代码用于隔代压缩
            x = parent[x];
        }
        return x;
    }

    // 将下标为x和下标为y的两个节点各自所在的子树进行合并
    public void union(int x, int y) {
        // 分别找到两个节点各自的根节点
        int a = find(x);
        int b = find(y);
        // 不必进行按秩合并了
        parent[a] = b;
    }

    // 判断下标为x和y的两个节点是否在同一个集合中
    // i.e. 是否具有相同的根节点
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}
JAVA

Go

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
// UnionFind usage:
//
// uf := &UnionFind{}
//
// uf.init(n)
type UnionFind struct {
	n      int
	parent []int
	size   []int
}

func (union *UnionFind) init(sz int) {
	union.n = sz
	union.parent = make([]int, sz)
	union.size = make([]int, sz)
	for i := 0; i < sz; i++ {
		union.parent[i] = i
		union.size[i] = 1
	}
}
func (union *UnionFind) find(x int) int {
	for union.parent[x] != x {
		union.parent[x] = union.parent[union.parent[x]] // 隔代压缩
		x = union.parent[x]
	}
	return x
}
func (union *UnionFind) union(x, y int) {
	if union.isConnected(x, y) {
        // 这个判断是必要的，否则会导致size数组计算错误
		return
	}
	rootX := union.find(x)
	rootY := union.find(y)
	szX := union.size[rootX]
	szY := union.size[rootY]
    // 按秩合并
	if szX > szY {
		union.parent[rootY] = rootX
		union.size[rootX] += szY
	} else {
		union.parent[rootX] = rootY
		union.size[rootY] += szX
	}
}
func (union *UnionFind) isConnected(x, y int) bool {
	return union.find(x) == union.find(y)
}
func (union *UnionFind) getCap(x int) int {
	return union.size[x]
}
GO

前缀树

参考 https://www.notion.so/exapricity/3485-K-1b804c046fb180c9ac65e2c9f29b28cc?pvs=4

Java

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
class TrieNode {
    boolean isWord;
    TrieNode[] children;

    TrieNode() {
        this.isWord = false;
        this.children = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        var node = this.root;
        for (int i = 0; i < word.length(); i++) {
            char cur = word.charAt(i);
            if (node.children[cur - 'a'] == null) {
                node.children[cur - 'a'] = new TrieNode();
            }
            node = node.children[cur - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        var node = this.root;
        for (int i = 0; i < word.length(); i++) {
            char cur = word.charAt(i);
            if (node.children[cur - 'a'] == null) {
                return false;
            }
            node = node.children[cur - 'a'];
        }
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
        var node = this.root;
        for (int i = 0; i < prefix.length(); i++) {
            char cur = prefix.charAt(i);
            if (node.children[cur - 'a'] == null) {
                return false;
            }
            node = node.children[cur - 'a'];
        }
        return true;
    }
}
JAVA

Go

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
type TrieNode struct {
	isWord   bool
	children [26]*TrieNode
}
type Trie struct {
	root *TrieNode
}

func Constructor() Trie {
	return Trie{root: &TrieNode{isWord: false, children: [26]*TrieNode{}}}
}

func (this *Trie) Insert(word string) {
	cur := this.root
	for _, ch := range word {
		if cur.children[ch-'a'] == nil {
			cur.children[ch-'a'] = &TrieNode{isWord: false, children: [26]*TrieNode{}}
		}
		cur = cur.children[ch-'a']
	}
	cur.isWord = true
}

func (this *Trie) Search(word string) bool {
	cur := this.root
	for _, ch := range word {
		if cur.children[ch-'a'] == nil {
			return false
		}
		cur = cur.children[ch-'a']
	}
	return cur.isWord
}

func (this *Trie) StartsWith(prefix string) bool {
	cur := this.root
	for _, ch := range prefix {
		if cur.children[ch-'a'] == nil {
			return false
		}
        cur = cur.children[ch-'a']
	}
	return true
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
GO

线段树

Go

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
type SegmentTree struct {
	nums []int // original input on the segment tree
	// interesting info maintained by the tree. O(logn)
	// complete binary trees in array form, index starting from 1
	su     []int
	mx     []int
	mi     []int
	negInf int
	posInf int
	// todo: add more 'interesting' fields here
}

func NewSegmentTree(nums []int, negInf int, posInf int) *SegmentTree {
	ans := SegmentTree{
		nums:   nums,
		su:     make([]int, 4*len(nums)),
		mx:     make([]int, 4*len(nums)),
		mi:     make([]int, 4*len(nums)),
		negInf: negInf,
		posInf: posInf,
	}
	ans.build(1, 0, len(nums)-1)
	return &ans
}

func (st *SegmentTree) build(idx int, left int, right int) {
	// idx-th node in the tree corresponds nums[left, right]
	if left == right {
		// reach a terminal node(leaf)
		st.su[idx] = st.nums[left]
		st.mx[idx] = st.nums[left]
		st.mi[idx] = st.nums[left]
		return
	}
	mid := left + (right-left)/2
	st.build(idx*2, left, mid)
	st.build(idx*2+1, mid+1, right)
	st.pushUp(idx)
}
func (st *SegmentTree) pushUp(idx int) {
	// push up: gather info from children nodes to update self
	st.su[idx] = st.su[idx*2] + st.su[idx*2+1]
	st.mx[idx] = max(st.mx[idx*2], st.mx[idx*2+1])
	st.mi[idx] = min(st.mi[idx*2], st.mi[idx*2+1])
	// todo: add more ops here
}

func (st *SegmentTree) add(idx int, left int, right int, delta int, i int) {
	// make nums[i] += delta
	if left == right {
		st.su[idx] += delta
		st.mx[idx] += delta
		st.mi[idx] += delta
		return
	}
	mid := left + (right-left)/2
	if i <= mid {
		st.add(idx*2, left, mid, delta, i)
	} else {
		st.add(idx*2+1, mid+1, right, delta, i)
	}
	st.pushUp(idx)
}
func (st *SegmentTree) Add(i int, delta int) {
	st.add(1, 0, len(st.nums)-1, delta, i)
}

func (st *SegmentTree) update(idx int, left int, right int, val int, i int) {
	if left == right && i == left {
		st.su[idx] = val
		st.mx[idx] = val
		st.mi[idx] = val
		return
	}
	mid := left + (right-left)/2
	if i <= mid {
		st.update(idx*2, left, mid, val, i)
	} else {
		st.update(idx*2+1, mid+1, right, val, i)
	}
	st.pushUp(idx)
}
func (st *SegmentTree) Update(i int, val int) {
	st.update(1, 0, len(st.nums)-1, val, i)
}

func (st *SegmentTree) sum(idx int, left int, right int, L int, R int) int {
	if left >= L && right <= R {
		return st.su[idx]
	}
	mid := left + (right-left)/2
	ans := 0
	if L <= mid {
		ans += st.sum(idx*2, left, mid, L, R)
	}
	if R > mid {
		ans += st.sum(idx*2+1, mid+1, right, L, R)
	}
	return ans
}
func (st *SegmentTree) Sum(L int, R int) int {
	return st.sum(1, 0, len(st.nums)-1, L, R)
}

func (st *SegmentTree) max(idx int, left int, right int, L int, R int) int {
	if left >= L && right <= R {
		return st.mx[idx]
	}
	mid := left + (right-left)/2
	ans := st.negInf
	if L <= mid {
		ans = max(ans, st.max(idx*2, left, mid, L, R))
	}
	if R > mid {
		ans = max(ans, st.max(idx*2+1, mid+1, right, L, R))
	}
	return ans
}
func (st *SegmentTree) Max(L int, R int) int {
	return st.max(1, 0, len(st.nums)-1, L, R)
}

func (st *SegmentTree) min(idx int, left int, right int, L int, R int) int {
	if left >= L && right <= R {
		return st.mi[idx]
	}
	mid := left + (right-left)/2
	ans := st.posInf
	if L <= mid {
		ans = min(ans, st.min(idx*2, left, mid, L, R))
	}
	if R > mid {
		ans = min(ans, st.min(idx*2+1, mid+1, right, L, R))
	}
	return ans
}
func (st *SegmentTree) Min(L int, R int) int {
	return st.min(1, 0, len(st.nums)-1, L, R)
}
GO

跳表

Go

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
const LEVEL int = 10

type Node struct {
	val  int
	next []*Node
}

type Skiplist struct {
	dummy *Node
}

func Constructor() Skiplist {
	return Skiplist{
		dummy: &Node{
			val:  -1,
			next: make([]*Node, 10),
		},
	}
}

func (this *Skiplist) find(target int, pre []*Node) {
	cur := this.dummy
	for i := LEVEL - 1; i >= 0; i-- {
		for cur.next[i] != nil && cur.next[i].val < target {
			cur = cur.next[i]
		}
		pre[i] = cur
	}
}

func (this *Skiplist) Search(target int) bool {
	pre := make([]*Node, LEVEL)
	this.find(target, pre)
	return pre[0].next[0] != nil && pre[0].next[0].val == target
}

func (this *Skiplist) Add(num int) {
	pre := make([]*Node, LEVEL)
	this.find(num, pre)
	node := &Node{num, make([]*Node, LEVEL)}
	for i := 0; i < LEVEL; i++ {
		node.next[i] = pre[i].next[i]
		pre[i].next[i] = node
		// spread to upper level with 0.5 chance
		if rand.Intn(2) == 0 {
			break
		}
	}
}

func (this *Skiplist) Erase(num int) bool {
	pre := make([]*Node, LEVEL)
	this.find(num, pre)
	node := pre[0].next[0]
	if node == nil || node.val != num {
		return false
	}
	for i := 0; i < LEVEL && pre[i].next[i] == node; i++ {
		pre[i].next[i] = pre[i].next[i].next[i]
	}
	return true
}
GO

二叉堆

常用的编程语言中只有 Go 没有内置的堆实现

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
type Tuple struct {
	dis int
	x   int
	y   int
}

type Pq []Tuple // min heap usage: replace the `Tuple` struct

func (pq Pq) Len() int {
	return len(pq)
}

func (pq Pq) Less(i, j int) bool {
	// min heap or max heap?
	return pq[i].dis < pq[j].dis
}

func (pq Pq) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *Pq) Push(x interface{}) {
	*pq = append(*pq, x.(Tuple))
}

func (pq *Pq) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x // x should be cast
}

// usage
// pq := Pq{}
// heap.Init(&pq)
// heap.Push(&pq, ...)
// top := heap.Pop(&pq).(Tuple)
GO

最短路

Dijkstra

假设图以邻接矩阵作为入参

不带堆优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] dijkstra(int n, int k, int[][] graph) {
    // graph是一个n*n的邻接矩阵,k是起点
    int[] dis = new int[n];
    Arrays.fill(dis, Integer.MAX_VALUE / 2);
    dis[k] = 0;
    boolean[] done = new boolean[n];
    for (int p = 0; p < n; p++) {
        // 由于规定了循环次数，图不连通也不会有影响
        // 每次找到「dis[t]最小」且「未被更新」的节点t
        int t = -1;
        for (int i = 0; i < n; i++) {
            if (!done[i] && (t == -1 || dis[i] < dis[t])) {
                // TODO:这一步可以使用堆进行优化
                t = i;
            }
        }
        done[t] = true;
        // 用点t的dis更新其他dis
        for (int i = 0; i < n; i++) {
            dis[i] = Math.min(dis[i], dis[t] + graph[t][i]);
        }
    }
    return dis;
}
JAVA

带堆优化

Java
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
private int[] dijkstra(int n, int start, int[][] graph) {
    // define graph as an n*n adjacent table
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    dist[start] = 0;
    boolean[] done = new boolean[n];
    // a[0] is the node number, a[1] is the cost
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.add(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int node = cur[0];
        if (done[node]) {
            continue;
        }
        done[node] = true;
        for (int i = 0; i < n; i++) {
            if (done[i]) {
                continue;
            }
            if (dist[node] + graph[node][i] < dist[i]) {
                dist[i] = dist[node] + graph[node][i];
                pq.add(new int[]{i, dist[i]});
            }
        }
    }
    return dist;
}
JAVA
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub fn dijkstra(n: usize, start: usize, graph: &Vec<Vec<i32>>) -> Vec<i32> {
    const INF: i32 = i32::MAX / 2;
    let mut dist = vec![INF; n];
    dist[start] = 0;
    let mut done = vec![false; n];
    let mut pq = BinaryHeap::new(); // this is a max heap!
    pq.push((0, start));
    while let Some((_, node)) = pq.pop() {
        if done[node] {
            continue;
        }
        done[node] = true;
        for i in 0..n {
            if done[i] {
                continue;
            }
            if dist[node] + graph[node][i] < dist[i] {
                dist[i] = dist[node] + graph[node][i];
                pq.push((-dist[i], i)); // this is a max heap, but we need a min heap
            }
        }
    }
    dist
}
RUST
Go
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
63
64
65
66
67
68
import (
	"container/heap"
	"math"
)

type Tuple struct {
	dis  int
	node int
}

type Pq []Tuple // min heap usage: replace the `Tuple` struct

func (pq Pq) Len() int {
	return len(pq)
}

func (pq Pq) Less(i, j int) bool {
	// min heap or max heap?
	return pq[i].dis < pq[j].dis
}

func (pq Pq) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *Pq) Push(x interface{}) {
	*pq = append(*pq, x.(Tuple))
}

func (pq *Pq) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x // x should be cast
}

func dijkstra(graph [][]int, n int, src int) []int {
	const INF = math.MaxInt64 / 2
	dist := make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	dist[src] = 0
	done := make([]bool, n)
	pq := Pq{}
	heap.Init(&pq)
	heap.Push(&pq, Tuple{0, src})
	for pq.Len() > 0 {
		cur := heap.Pop(&pq).(Tuple)
		if cur.dis > dist[cur.node] {
			// this value is outdated
			continue
		}
		done[cur.node] = true
		for i := 0; i < n; i++ {
			if done[i] {
				continue
			}
			if dist[i] > cur.dis+graph[cur.node][i] {
				dist[i] = cur.dis + graph[cur.node][i]
				heap.Push(&pq, Tuple{dist[i], i})
			}
		}
	}
	return dist
}

GO

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[][] floyd(int n, int[][] graph) {
    int[][] dis = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = graph[i][j];
        }
    }
    for (int[] edge: graph) {
        int from = edge[0];
        int to = edge[1];
        int cost = edge[2];
    }
    for (int k = 0; k < n; k++) { // 枚举中转点
        for (int i = 0; i < n; i++) { // 枚举起点
            for (int j = 0; j < n; j++) { // 枚举终点
                dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    return dis;
}
JAVA

快速幂

使用二分减治和递归的思想进行快速幂的计算

Java（递归版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public double myPow(double x, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n == 1) {
        return x;
    }
    if (n < 0) {
        n = -n; // 可能导致溢出
        x = 1 / x;
    }
    int halfExpo = n / 2;
    double halfRes = myPow(x, halfExpo);
    double ans = halfRes * halfRes;
    if ((n & 1) == 1) {
        ans *= x;
    }
    return ans;
}
JAVA

注意这个 Java 代码无法通过 50. Pow(x, n) - 力扣（LeetCode），原因是某个用例的 n 为 int 类型的最小值，导致取相反数时溢出。可以重载一个 n 为 long 的函数解决

⭐Go（位运算版）

解析

例如我们想要计算 x15x^{15}, 观察发现 x15=x1∗x2∗x4∗x8x^{15}=x^{1} * x^{2} * x^{4} * x^{8}，而 15 的二进制为 1111。即从低到高的第 ii 个（从 0 开始计数）二进制位若为 1，整体的结果就额外乘上 x2ix^{2^{i}}。这个方法有些类似海明码的思想，更正式的名称是「指数的二进制展开」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func myPow(x float64, n int) float64 {
	// corner cases
	if n == 0 {
		return 1.0
	}
	if n < 0 {
		return myPow(1/x, -n)
	}
	if n == 1 {
		return x
	}
	ans := 1.0
	tmp := x
	for i := n; i > 0; i >>= 1 {
		if i&1 != 0 {
			ans *= tmp
		}
		tmp *= tmp
	}
	return ans
}
GO

组合数

普通循环

边乘边除，恒等式优化 C(n,k)=C(n,n−k)C(n, k) = C(n, n-k)

1
2
3
4
5
6
7
8
func comb(n, k int) int {
    k = min(k, n-k)
    res := 1
    for i := 1; i <= k; i++ {
        res = res * (n + 1 - i) / i
    }
    return res
}
GO

取模场景

当 nn 很大时，题目可能让我们对结果取一个模，例如典型的 1e9+7（要注意到这个数是一个质数！）

求组合数时要用到除法，但是模运算不能直接作用在除法上！

这里做一个简单的理解：

模运算其实是在划分等价类，例如 mod 6 下，4, 10, 16… 构成了一个等价类，2, 8, 14… 构成了一个等价类。

错误的理解是，(4/2) mod 6 = 2 mod 6 = 2，但是由于等价类的要求，(4/2) mod 6 = (10/2) mod 6，如果采用同样的计算方法，会发现 (10/2) mod 6 = 5 mod 6 = 5，这样就与事实矛盾了！因此在除法下进行模运算不是这么简单的！

事实上，除法下的模运算具有下列规则：

(a/b)mod  p=(a∗b−1)mod  p(a/b) \mod p = (a * b^{-1}) \mod p

注意这里的 b−1b^{-1} 不是 bb 的倒数，而是 bb 在模 pp 操作下的乘法逆元，即 b∗b−1≡1mod  pb*b^{-1} \equiv 1\mod p

当 xx 与 pp 互质时，xx 在模 pp 操作下具有乘法逆元

特别的，当 pp 本身就是质数（例如典型的 1e9+7），且 xx 不是 pp 的倍数时（xx 的范围也到不了这么大），由费马小定理：

对任意整数 aa，若 pp 是素数，则：

ap≡a(modp)a^p \equiv a \pmod{p}

或者：

如果 pp 是一个素数，且 aa 是一个不被 pp 整除的整数，则：

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

将上式同时乘以 a−1a^{-1}，即得到 ap−2≡a−1mod  pa^{p-2}\equiv a^{-1} \mod p

所以我们只需计算 ap−2mod  pa^{p-2} \mod p。这可以用快速幂进行优化

我们再回忆一下组合数的计算公式：C(n,k)=n!k!(n−k)!C(n, k) = \frac{n!}{k!(n-k)!}

在取模背景下，即 C(n,k)mod  p=n!⋅(k!(n−k)!)−1mod  p=n!⋅(k!)−1⋅((n−k)!)−1mod  pC(n, k) \mod p = n! \cdot (k!(n-k)!)^{-1} \mod p = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \mod p

综上我们得出模运算下求组合数的代码：

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
const MOD int = 1e9 + 7
const MaxN int = 1e6

var fact [MaxN + 1]int
var invFact [MaxN + 1]int

func powMod(a, b, mod int) int {
	res := 1
	for b > 0 {
		if b&1 == 1 {
			res = res * a % mod
		}
		a = a * a % mod
		b >>= 1
	}
	return res
}

func init() {
	fact[0] = 1
	for i := 1; i <= MaxN; i++ {
		fact[i] = fact[i-1] * i % MOD
	}
	invFact[MaxN] = powMod(fact[MaxN], MOD-2, MOD)
	for i := MaxN - 1; i >= 0; i-- {
		invFact[i] = invFact[i+1] * (i + 1) % MOD
	}
}

func comb(n, k int) int {
	if k < 0 || k > n {
		return 0
	}
	return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD
}
GO

注意，求阶乘时从小到大递推，求阶乘的逆元时从大到小递推

例题：https://leetcode.cn/problems/maximum-and-minimum-sums-of-at-most-size-k-subsequences/submissions/621842633/

埃氏筛

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int countPrimes(int n) {
    int ans = 0;
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) { // i is prime
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            ans++;
        }
    }
    return ans;
}
JAVA

字符串哈希（字串问题）

使用 Rabin-Karp 算法检测 s1 中是否包含字串 s2（改编自 Go 内置的 bytealg package - internal/bytealg - Go Packages）

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
// adopted from bytealgo.go/IndexRabinKarp
const PrimeRK = 16777619

func RabinKarp(s, sep string) bool {
	if len(s) < len(sep) {
		return false
	}
	if len(s) == len(sep) {
		return s == sep
	}
	hashss, pow := hashStr(sep)
	n := len(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*PrimeRK + uint32(s[i])
	}
	if h == hashss && s[:n] == sep {
		return true
	}
	for i := n; i < len(s); {
		h *= PrimeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashss && s[i-n:i] == sep {
			return true
		}
	}
	return false
}
func hashStr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*PrimeRK + uint32(sep[i])
	}
	var pow, sq uint32 = 1, PrimeRK
	// Fast Exponentiation
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		sq *= sq
	}
	return hash, pow
}
GO

子序列

LCS

时间复杂度 O(mn)O(mn)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// if text2 is a subsequence of text1?
func isSubseq(text1, text2 string) bool {
	if text1 == text2 {
		return true
	}
	return len(text2) == longestCommonSubsequence(text1, text2)
}
func longestCommonSubsequence(text1 string, text2 string) int {
	l1, l2 := len(text1), len(text2)
	dp := make([][]int, l1+1)
	for i := range dp {
		dp[i] = make([]int, l2+1)
	}
	for i, x := range text1 {
		for j, y := range text2 {
			if x == y {
				dp[i+1][j+1] = 1 + dp[i][j]
			}
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1], dp[i+1][j])
		}
	}
	return dp[l1][l2]
}
GO

⭐双指针

时间复杂度 O(m+n)O(m+n)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// if text2 is a subsequence of text1?
func isSubseq(text1, text2 string) bool {
	if len(text1) < len(text2) {
		return false
	}
	if len(text1) == len(text2) {
		return text1 == text2
	}
	i, j := 0, 0
	for i < len(text1) && j < len(text2) {
		if text1[i] == text2[j] {
			i++
			j++
		} else {
			i++
		}
	}
	return j == len(text2)
}
GO

单调队列

用于维护一个可变区间中的最值

下面定义的队列中，元素从队首到队尾单调不减（允许重复元素）

Rust

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
use std::collections::VecDeque;
struct MonoQueue {
    queue: VecDeque<i32>,
}
impl MonoQueue {
    fn len(&self) -> usize {
        self.queue.len()
    }
    fn push(&mut self, val: i32) {
        while let Some(&back) = self.queue.back() {
            // use destructuring to avoid considering if the queue is empty
            if val > back {
                self.queue.pop_back();
            } else {
                break
            }
        }
        self.queue.push_back(val);
    }
    fn pop(&mut self, val: i32) {
        if self.queue.front() == Some(&val) {
            self.queue.pop_front();
        }
    }
    fn max(&self) -> i32 {
        *self.queue.front().unwrap_or(&0)
    }
    fn new() -> Self {
        MonoQueue {
            queue: VecDeque::new(),
        }
    }
}
RUST

Usage

Go

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
type MonoQueue struct {
	queue []int
}

func (mq *MonoQueue) Len() int {
	return len(mq.queue)
}
func (mq *MonoQueue) Push(v int) {
	for mq.Len() != 0 && mq.queue[mq.Len()-1] < v {
		mq.queue = mq.queue[:mq.Len()-1]
	}
	mq.queue = append(mq.queue, v)
}
func (mq *MonoQueue) Pop(v int) {
	if mq.queue[0] == v {
		mq.queue = mq.queue[1:]
	}
}
func (mq *MonoQueue) Max() int {
	return mq.queue[0]
}
func NewMonoQueue() *MonoQueue {
	return &MonoQueue{
		queue: make([]int, 0),
	}
}
GO

多数元素

求出数组中频率大于 ⌊n/k⌋\lfloor n/k \rfloor 的元素，其中 nn 为数组的长度

k=2k = 2 时对应摩尔投票法

k≥2k \geq 2 时对应 Misra-Gries 算法

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
const NOT_FOUND = 404 // magic number

func Misra_Gries(arr []int, k int) []int {
    // there are at most k-1 majority elements
    cnts := make(map[int]int)
    for _, x := range arr {
       if _, ok := cnts[x]; ok {
          cnts[x] += 1
       } else {
          if len(cnts) >= k-1 {
             for y := range cnts {
                cnts[y] -= 1
                if cnts[y] == 0 {
                   delete(cnts, y)
                }
             }
          } else {
             cnts[x] = 1
          }
       }
    }
    ans := make([]int, 0)
    for x := range cnts {
       if check(arr, x, k) {
          ans = append(ans, x)
       }
    }
    return ans
}
func Boyer_Moore(arr []int) int {
    cur := arr[0]
    cnt := 1
    for i := 1; i < len(arr); i++ {
       if arr[i] == cur {
          cnt++
       } else {
          if cnt == 0 {
             cur = arr[i]
             cnt = 2
          }
          cnt--
       }
    }
    if check(arr, cur, 2) {
       return cur
    }
    return NOT_FOUND
}
func check(arr []int, target int, k int) bool {
    cnt := 0
    for _, x := range arr {
       if x == target {
          cnt++
       }
    }
    return cnt >= len(arr)/k+1
}
GO
study
#算法 #数据结构
数据结构和算法模板
https://exapricity.tech/Algo-DS-Template.html
作者
Peiyang He
发布于
2024年3月4日
许可协议