基础算法模板

1.快速排序

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
package basic

func QuickSort(q []int, l, r int) {
	if l >= r {
		return
	}

	i, j, x := l-1, r+1, q[l+r>>1]
	for i < j {
		for q[i] < x {
			i++
		}

		for q[j] > x {
			j--
		}

		if i < j {
			q[i], q[j] = q[j], q[i]
		}
	}

	QuickSort(q, l, i)
	QuickSort(q, i+1, r)
}

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
package basic

func MergeSort(q []int, l, r int) {
	if l >= r {
		return
	}

	mid := l + r>>1
	MergeSort(q, l, mid)
	MergeSort(q, mid+1, r)

	i, j, k := l, mid+1, 0
	tmp := make([]int, r-l+1)
	for i <= mid && j <= r {
		if q[i] < q[j] {
			tmp[k] = q[i]
			k++
			i++
		} else {
			tmp[k] = q[j]
			k++
			j++
		}
	}
	for i <= mid {
		tmp[k] = q[i]
		k++
		i++
	}
	for j <= r {
		tmp[k] = q[j]
		k++
		j++
	}
	for k, v := range tmp {
		q[l+k] = v
	}
}

3.二分查找

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
package basic

// 检查x是否满足某种性质
func check(x int) bool {
	return x > 10
}

func checkFloat(x float32) bool {
	return x > 10
}

// 区间[l,r]被划分成[l,mid]和[mid+1,r]时使用
func Bsearch_1(l, r int) int {
	for l < r {
		mid := l + r>>1
		if check(mid) {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

// 区间[l,r]被划分成[l,mid-1]和[mid,r]时使用
func Bsearch_2(l, r int) int {
	for l < r {
		mid := l + r + 1>>1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

// 浮点数的二分查找模板
func Bsearch_3(l, r float32) float32 {
	const eps = 1e-6
	for r-l > eps {
		mid := (l + r) / 2
		if checkFloat(mid) {
			r = mid
		} else {
			l = mid
		}
	}
	return l
}

4.高精度计算

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
package basic

/*
处理超大数的加减乘除.
加减乘这里输入的数字字符串需要按照从小到大的顺序写入切片，例如：
输入： 123456
处理后：[6,5,4,3,2,1]
除法这里输入的数字字符串需要按照从大到小的顺序写入切片，例如：
输入： 123456
处理后：[1,2,3,4,5,6]
*/

// 高精度加法
func Add(a, b []int) []int {
	c := make([]int, 0)
	t := 0
	for i := 0; i < len(a) || i < len(b); i++ {
		if i < len(a) {
			t += a[i]
		}
		if i < len(b) {
			t += b[i]
		}

		c = append(c, t%10)
		t /= 10
	}
	if t != 0 {
		c = append(c, t)
	}
	return c
}

// 高精度减法；计算a-b。
func Sub(a, b []int) []int {
	c := make([]int, 0)
	t := 0
	for i := 0; i < len(a); i++ {
		t += a[i]
		if i < len(b) {
			t -= b[i]
		}
		c = append(c, (t+10)%10)
		if t < 0 {
			t = -1
		} else {
			t = 0
		}
	}
	// 处理前导0
	for len(c) > 1 && c[len(c)-1] == 0 {
		c = c[:len(c)-1]
	}
	return c
}

// 高精度乘法：a*b,其中b是正常的数。
func Mul(a []int, b int) []int {
	c := make([]int, 0)
	t := 0
	for i := 0; i < len(a); i++ {
		t = a[i]*b + t
		c = append(c, t%10)
		t /= 10
	}
	if t > 0 {
		c = append(c, t)
	}
	// 处理前导0
	for len(c) > 1 && c[len(c)-1] == 0 {
		c = c[:len(c)-1]
	}
	return c
}

// 高精度除法: a/b，其中b是正常的数。
func Div(a []int, b int) (c []int, t int) {
	t = 0
	for i := 0; i < len(a); i++ {
		t = t*10 + a[i]
		c = append(c, t/b)
		t %= b
	}
	// 处理前导0
	for len(c) > 1 && c[0] == 0 {
		c = c[1:]
	}
	return
}

5.前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package basic

/*
前缀和常用来便捷处理区间和，例如：
输入的a为：[1,2,3,4]
则前缀和s为：[1,3,6,10]
则区间和s[l, r]= s[r] - s[l-1]
*/
func PrifixSum_1(a []int) []int {
	s := make([]int, len(a))
	if len(a) > 0 {
		s[0] = a[0]
	}
	for i := 1; i < len(a); i++ {
		s[i] = a[i-1] + a[i]
	}
	return s
}

6.差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package basic

/*
差分数组用于快速处理给区间[l,r]内的元素均加上或者减去一个值。例如：
输入a为：[1,4,6,2]
则差分数组b为：[1,3,2,-4]
如果要给a数组的区间[l,r]都加上一个c，则b[l]+c,b[r+1]-c
然后对b数组求一遍前缀和，即可得出调整后的a数组。
*/
func Difference(a []int) []int {
	b := make([]int, len(a)+1)
	for i := 0; i < len(a); i++ {
		b[i] += a[i]
		b[i+1] -= a[i]
	}
	return b
}

7.位运算

1
2
3
4
5
6
7
8
9
10
11
12
package basic

// 求n的二进制表示的第k位数字
func TheK(n, k int) int {
	return n >> k & 1
}

// 求n的二进制表示的最后一位1
func Lowbit(n int) int {
	return n & -n
}

8.离散化

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
package basic

import "sort"

// 存储所有待离散化的值
var alls []int

// 将所有值排序
func Sort(alls []int) []int {
	sort.Ints(alls)
	return alls
}

// 去掉重复元素
func Unique(alls []int) []int {
	res := make([]int, 0)
	for i, j := 0, 0; i < len(alls); i = j {
		for j < len(alls) && alls[i] == alls[j] {
			j++
		}
		res = append(res, alls[i])
	}
	return res
}

// 二分求出x对应的离散化的值
func Find(x int) int {
	l, r := 0, len(alls)-1
	for l < r {
		mid := l + r>>1
		if alls[mid] >= x {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return r + 1
}

9.区间合并

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
package basic

import "sort"

type edge struct {
	l, r int
}

/*
给定 n个区间 [li,ri]，要求合并所有有交集的区间。例如：
[1,3]和[2,6]可以合并为一个区间[1,6]。
*/
func MergeEdge(edges []edge) []edge {
	// 按照区间的左端点从小到大排序，左端点一致的，按照右端点从大到小排序
	sort.Slice(edges, func(i, j int) bool {
		if edges[i].l == edges[j].l {
			return edges[i].r > edges[j].r
		}
		return edges[i].l < edges[j].l
	})
	res := make([]edge, 0)
	for i, j := 0, 0; i < len(edges); i = j {
		for j < len(edges) && edges[i].l < edges[j].r {
			edges[i].r = max(edges[i].r, edges[j].r)
		}
		res = append(res, edges[i])
	}
	return res
}