堆
传统堆
模板支持最大堆、最小堆切换。
package main
import (
"container/heap"
"fmt"
)
type Heap struct {
data []int
max bool // true: 最大堆, false: 最小堆
}
func (h Heap) Len() int { return len(h.data) }
func (h Heap) Less(i, j int) bool {
if h.max {
return h.data[i] > h.data[j] // 最大堆
}
return h.data[i] < h.data[j] // 最小堆
}
func (h Heap) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *Heap) Push(x interface{}) { h.data = append(h.data, x.(int)) }
func (h *Heap) Pop() interface{} {
n := len(h.data)
x := h.data[n-1]
h.data = h.data[:n-1]
return x
}
func main() {
h := &Heap{max: true} // 最大堆
heap.Init(h)
heap.Push(h, 3)
heap.Push(h, 1)
heap.Push(h, 5)
fmt.Println(heap.Pop(h)) // 输出 5
h.max = false // 切换为最小堆
heap.Init(h)
heap.Push(h, 3)
heap.Push(h, 1)
heap.Push(h, 5)
fmt.Println(heap.Pop(h)) // 输出 1
}
惰性删除堆
并查集
维护无向图的一种方法。
求无向图联通分量，最小生成树。（按边）
// 简单模板，只实现了路径压缩，没实现按秩合并。
func minCost(n int, edges [][]int, k int) int {
sort.Slice(edges, func(i, j int) bool {
return edges[i][2] < edges[j][2]
})
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
find := func(x int) int {
rt := x
for fa[rt] != rt {
rt = fa[rt]
}
for fa[x] != rt {
fa[x], x = rt, fa[x]
}
return rt
}
count := n
unite := func(from, to int) {
rt1 := find(from)
rt2 := find(to)
if rt1 == rt2 {
return
}
count--
fa[find(from)] = find(to)
}
if count == k {
return 0
}
for i := 0; i < len(edges); i++ {
unite(edges[i][0], edges[i][1])
if count == k {
return edges[i][2]
}
}
return math.MaxInt
}
拓展域并查集
type Pair struct {
i int
j int
dis int
}
func maxPartitionFactor(points [][]int) int {
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
dis := func(a, b []int) int {
return abs(abs(a[0]-b[0])) + abs(abs(a[1]-b[1]))
}
n := len(points)
pairs := []Pair{}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
pairs = append(pairs, Pair{i: i, j: j, dis: dis(points[i], points[j])})
}
}
sort.Slice(pairs, func(i, j int) bool {
return pairs[i].dis < pairs[j].dis
})
fa := make([]int, 2*n)
for i := range fa {
fa[i] = i
}
find := func(x int) int {
rt := x
for fa[rt] != rt {
rt = fa[rt]
}
for fa[x] != rt {
fa[x], x = rt, fa[x]
}
return rt
}
unite := func(from, to int) {
rt1 := find(from)
rt2 := find(to)
if rt1 == rt2 {
return
}
fa[find(from)] = find(to)
}
isSame := func(from, to int) bool {
return find(from) == find(to)
}
for i := 0; i < len(pairs); i++ {
if isSame(pairs[i].i, pairs[i].j) {
return pairs[i].dis
}
unite(pairs[i].i, pairs[i].j+n)
unite(pairs[i].i+n, pairs[i].j)
}
return 0
}
滑动窗口
一般如果不单调无法滑动窗口，只有单调的用。
前缀和、差分
树状数组
树状数组的下标从1开始，理解为带修改的前缀和，空间复杂度O(n)，时间复杂度O(logn)。
package main
const fenwickInitVal = 0 // -1e18
type fenwick []int
func newFenwickTree(n int) fenwick {
t := make(fenwick, n+1)
for i := range t {
t[i] = fenwickInitVal
}
return t
}
func (fenwick) op(a, b int) int {
return a + b // max(a, b)
}
// a[i] 增加 val
// 1<=i<=n
func (f fenwick) update(i, val int) {
for ; i < len(f); i += i & -i {
f[i] = f.op(f[i], val)
}
}
// 求前缀和 a[1] + ... + a[i]
// 1<=i<=n
func (f fenwick) pre(i int) int {
res := fenwickInitVal
i = min(i, len(f)-1)
for ; i > 0; i &= i - 1 {
res = f.op(res, f[i])
}
return res
}
// 求区间和 a[l] + ... + a[r]
// 1<=l<=r<=n
func (f fenwick) query(l, r int) int {
if r < l {
return 0
}
return f.pre(r) - f.pre(l-1)
}
func main() {
}
线段树
有序表
二分查找
开区间法、闭区间法，个人喜欢闭区间法。
BFS
两种写法，双数组法与队列法。
DFS
二叉树遍历： 前序：根、左、右。
中序：左、根、右。
后续：左、右、根。
DFS 无向图
from 是上一个节点，to != from 防止成环
func count(g [][]int) [2]int {
res := [2]int{}
var dfs func(cur, from, flag int)
dfs = func(cur, from, flag int) {
res[flag]++
for _, to := range g[cur] {
if to != from {
dfs(to, cur, flag ^ 1)
}
}
}
dfs(0, -1, 0)
return res
}
动态规划
数位DP
给每个位置填数。
func boolToByte(b bool) byte {
if b {
return 1
}
return 0
}
// 计算字典序在s1和s2之间的, 长度为n的字符串的个数
// s1, s2 由小写字母组成的字符串，s1 和 s2 的长度都为 n。
func findGoodStrings(n int, s1 string, s2 string, evil string) int {
dp := make([][2][2]int, n)
var dfs func(i int, lLimit, rLimit bool) int
dfs = func(i int, lLimit, rLimit bool) int {
if i == n {
return 1
}
iLimit := boolToByte(lLimit)
jLimit := boolToByte(rLimit)
if dp[i][iLimit][jLimit] != 0 {
return dp[i][iLimit][jLimit]
}
res := 0
left := byte('a')
right := byte('z')
if lLimit && rLimit {
left = s1[i]
right = s2[i]
} else if lLimit {
left = s1[i]
} else if rLimit {
right = s2[i]
}
for j := left; j <= right; j++ {
// 注意 lLimit, rLimit 逻辑是传递的
res += dfs(i + 1, lLimit && j == s1[i], rLimit && j == s2[i])
}
dp[i][iLimit][jLimit] = res
return res
}
return dfs(0, true, true)
}
回溯
数学
计算素数
func isPrime(n int) bool {
// 特殊情况处理
if n <= 1 {
return false // 1及更小的数不是质数
}
if n == 2 || n == 3 {
return true // 2和3是质数
}
if n%2 == 0 || n%3 == 0 {
return false // 能被2或3整除的数不是质数
}
// 检查从5到√n的所有可能因子
// 使用6k±1优化（所有大于3的质数都可表示为6k±1的形式）
for i := 5; i*i <= n; i += 6 {
if n%i == 0 || n%(i+2) == 0 {
return false
}
}
return true
}
带模运算的快速幂
func fastPowMod(a, n, mod int) int {
result := 1
// 首先对a取模，避免a很大的情况
a %= mod
for n > 0 {
if n & 1 == 1 {
result = (result * a) % mod
}
a = (a * a) % mod
n >>= 1
}
return result
}
计算乘法逆元
// 计算乘法逆元
func modInverse(a, p int) int {
// 确保a和p互质
if gcd(a, p) != 1 {
panic("乘法逆元不存在")
}
// 使用费马小定理计算乘法逆元
/*
从费马小定理推导：
a^(p-1) ≡ 1 (mod p)
a · a^(p-2) ≡ 1 (mod p)
因此，a 的乘法逆元为：a^(p-2) mod p
*/
return fastPowMod(a, p-2, p)
}
// 计算最大公约数
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
筛法求素数
package main
import "fmt"
// SieveOfEratosthenes 返回小于等于n的所有素数
func SieveOfEratosthenes(n int) []int {
// 初始化标记数组，默认所有数都是素数
isPrime := make([]bool, n+1)
for i := 2; i <= n; i++ {
isPrime[i] = true
}
// 筛选过程
for i := 2; i*i <= n; i++ {
if isPrime[i] {
// 将i的所有倍数标记为合数
for j := i * i; j <= n; j += i {
isPrime[j] = false
}
}
}
// 收集素数
primes := []int{}
for i := 2; i <= n; i++ {
if isPrime[i] {
primes = append(primes, i)
}
}
return primes
}
组合数打表
利用公式：\( C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k} \) 进行递推。
const N = 1000
const MOD = 10
var C [N + 1][N + 1]int
func build() {
C[0][0] = 1
for i := 1; i <= N; i++ {
C[i][0] = 1
for j := 1; j <= i; j++ {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
}
}
}
func init() {
build()
}
func triangularSum(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
sum := 0
for i := 0; i < n; i++ {
//fmt.Println(C[n - 1][i], nums[i])
sum = (sum + C[n - 1][i] * nums[i]) % MOD
//fmt.Println(sum)
}
return sum
}
字符串算法
前缀数组（KMP）
滚动哈希
核心是将字符串看作一个 base 进制数，计算其模 M 下的值。
递推公式：\( hash[i+1] = (hash[i] \times base + s[i]) \pmod {M} \) 。
防冲突策略（双哈希）：
采用 自然溢出 + 大质数取模 结合的方式，能极大降低冲突概率。
- 自然溢出：利用无符号整数溢出回绕特性，相当于对 \(2^{64} \) 取模。
- 大质数取模：选取一个大质数，如 \( 10^9+7 \) 取模。
模板题：最短回文串 - 给定字符串 s，求通过在前面添加字符能转换成的最短回文串。
const (
base = uint(131)
mod = uint(1000000007)
)
func shortestPalindrome(s string) string {
//baacaa
//fmt.Println(mod1*base)
n := len(s)
hash1L, hash1R, hash2L, hash2R := uint(0), uint(0), uint(0), uint(0)
mul1, mul2 := uint(1), uint(1)
res := -1
for i := 0; i < n; i++ {
cur := uint(s[i] - 'a')
hash1L = (hash1L*base + cur) % mod
hash1R = (hash1R + cur*mul1) % mod
hash2L = (hash2L*base + cur)
hash2R = (hash2R + cur*mul2)
if hash1L == hash1R && hash2L == hash2R {
res = i
}
mul1 = (mul1 * base) % mod
mul2 = mul2 * base
//fmt.Println(mul2)
}
if res == n - 1 {
return s
}
tmp := []byte(s[res+1:])
slices.Reverse(tmp)
return string(tmp) + s
}
进阶题：构造字符串的总得分和 ，利用前缀和计算区间哈希。
const (
base = uint(131)
M = uint(1000000007)
)
func sumScores(s string) int64 {
res := 0
n := len(s)
hashSum1 := make([]uint, n+1)
hashSum2 := make([]uint, n+1)
p1 := make([]uint, n+1)
p2 := make([]uint, n+1)
p1[0] = 1
p2[0] = 1
for i := 1; i <= n; i++ {
cur := uint(s[i-1] - 'a')
hashSum1[i] = (hashSum1[i-1]*base + cur) % M
hashSum2[i] = hashSum2[i-1]*base + cur
p1[i] = p1[i-1] * base % M
p2[i] = p2[i-1] * base
}
getLR := func(l, r int) (uint, uint) {
hash1 := (hashSum1[r] - hashSum1[l-1]*p1[r-l+1] + M*M) % M
hash2 := hashSum2[r] - hashSum2[l-1]*p2[r-l+1]
return hash1, hash2
}
for i := 0; i < n; i++ {
l := 1
r := n - i
for l <= r {
mid := (l + r) / 2
h1, h2 := getLR(1, mid)
s1, s2 := getLR(i+1, i+mid)
//fmt.Println(mid)
//fmt.Println(h1, h2)
//fmt.Println(s1, s2)
if h1 == s1 && h2 == s2 {
l = mid + 1
} else {
r = mid - 1
}
}
//fmt.Println(l - 1)
//fmt.Println("--------------------")
res += (l - 1)
}
return int64(res)
}
后缀数组
马拉车
前缀树
可以用来解决一些需要通过前缀来剪枝的问题。
真正使用的时候注意要灵活使用，end可以改为其他标识符，可以直接处理Node等等。
type Node struct {
nxt [26]*Node
end bool
}
type Trie struct {
root *Node
}
func Constructor() Trie {
return Trie{
root: &Node{},
}
}
func (this *Trie) Insert(word string) {
node := this.root
for i := 0; i < len(word); i++ {
idx := int(word[i] - 'a')
if node.nxt[idx] == nil {
node.nxt[idx] = &Node{}
}
node = node.nxt[idx]
}
node.end = true
}
func (this *Trie) Search(word string) bool {
node := this.root
for i := 0; i < len(word); i++ {
idx := int(word[i] - 'a')
if node.nxt[idx] == nil {
return false
}
node = node.nxt[idx]
}
return node.end
}
func (this *Trie) StartsWith(prefix string) bool {
node := this.root
for i := 0; i < len(prefix); i++ {
idx := int(prefix[i] - 'a')
if node.nxt[idx] == nil {
return false
}
node = node.nxt[idx]
}
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);
*/
路径压缩字典树
图论
计算矩阵的传递闭包
Floyd-Warshall 算法
for k := 0; k < n; k++ { // 尝试所有可能的中间节点
for i := 0; i < n; i++ { // 所有可能的起点
for j := 0; j < n; j++ { // 所有可能的终点
// 如果i->k和k->j都可达，那么i->j也可达
if tc[i][k] && tc[k][j] {
tc[i][j] = true
}
}
}
}
计算联通图最小生成树
计算最短路径
单源最短路径（Dijkstra）
有权图，如果无权直接 BFS 即可。 每次都贪心的选择距离最小的节点，如果无负环是可以的。
模板题：边反转的最小路径总成本
type E struct {
to int
w int
}
type P struct {
ed int
dis int
}
type Heap struct {
data []P
}
func (h Heap) Len() int { return len(h.data) }
func (h Heap) Less(i, j int) bool {
return h.data[i].dis < h.data[j].dis
}
func (h Heap) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *Heap) Push(x interface{}) { h.data = append(h.data, x.(P)) }
func (h *Heap) Pop() interface{} {
n := len(h.data)
x := h.data[n-1]
h.data = h.data[:n-1]
return x
}
func minCost(n int, edges [][]int) int {
g := make([][]E, n)
for _, v := range edges {
g[v[0]] = append(g[v[0]], E{to: v[1], w: v[2]})
g[v[1]] = append(g[v[1]], E{to: v[0], w: 2*v[2]})
}
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = math.MaxInt
}
dp[0] = 0
hp := &Heap{}
heap.Push(hp, P{ed: 0, dis: 0})
for hp.Len() != 0 {
top := heap.Pop(hp).(P)
if top.dis > dp[top.ed] {
continue
}
for _, nxt := range g[top.ed] {
to := nxt.to
w := nxt.w
if top.dis + w < dp[to] {
dp[to] = top.dis + w
heap.Push(hp, P{ed: to, dis: dp[to]})
}
}
}
if dp[n - 1] == math.MaxInt {
return -1
}
return dp[n - 1]
}