数据结构模板

数据结构模板

1.单链表

package datastructure

// 静态链表
// head存储链表头，e存储节点的值，ne存储节点的next指针，idx表示当前用到了哪个节点
var (
	head int
	e    []int
	ne   []int
	idx  int
)

// 初始化
func init() {
	head = -1
	idx = 0
}

// 在链表头插入一个数a
func Inserthead(a int) {
	e[idx] = a
	ne[idx] = head
	head = idx
	idx++
}

// 将头节点删除
func Removehead() {
	if head != -1 {
		head = ne[head]
	}
}

2.双链表

package datastructure

var (
	// e   []int
	l []int
	r []int
	// idx int
)

func init() {
	// 0是左端点，1是右端点
	r[0] = 1
	l[1] = 0
	idx = 2
}

// 在节点a的右边插入一个数x
func InsertR(a, x int) {
	e[idx] = x
	l[idx] = a
	r[idx] = r[a]
	l[r[a]] = idx
	r[a] = idx
	idx++
}

// 删除节点a
func Remove(a int) {
	l[r[a]] = l[a]
	r[l[a]] = r[a]
}

3.栈

package datastructure

// stk表示栈，tt表示栈顶
var (
	stk []int
	tt  int
)

// 向栈顶插入一个数
func InsertTop(x int) {
	tt++
	stk[tt] = x
}

// 从栈顶弹出一个数
func RemoveTop() {
	tt--
}

// 获取栈顶的值
func Query() int {
	return stk[tt]
}

// 判断栈是否为空
func EmptyStk() bool {
	return tt <= 0
}

/*
单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
*/

var n int

func MonotonicStack() {
	for i := 1; i <= n; i++ {
		for !EmptyStk() && check(stk[tt], i) {
			tt--
		}

		InsertTop(i)
	}
}

// 判断a，b的某种性质
func check(a, b int) bool {
	return a < b
}

4.队列

package datastructure

// q模拟队列，hh表示队头，tt表示队尾
var (
	q  []int
	hh int = 0
	// tt int = -1
)

// 向队尾插入一个数
func InsertTail(x int) {
	tt++
	q[tt] = x
}

// 从队头弹出一个数
func RemoveT() {
	hh++
}

// 取出队头的值
func QueryQ() int {
	return q[hh]
}

// 判断队列是否为空
func EmptyQ() bool {
	return hh > tt
}

/*
单调队列
常见模型：找出滑动窗口中的最大值/最小值
*/
func MonotonicQueue() {
	for i := 0; i < n; i++ {
		for !EmptyQ() && check_out(q[hh]) {
			hh++
		}

		for !EmptyQ() && check(q[tt], i) {
			tt--
		}
		InsertTail(i)
	}
}

// 判断队头是否符合性质，是否需要移除滑动窗口
func check_out(x int) bool {
	return true
}

5.KMP

package datastructure

/*
s是长文本
p是模式串
需要预处理，例如：
s = "bschueoan"
处理后：s = " bschueoan"
*/
var (
	s, p string
	next []int
)

// 求模式串的next数组
func CalNext() {
	for i, j := 2, 0; i <= len(p)-1; i++ {
		for j > 0 && p[i] != p[j+1] {
			j = next[j]
		}
		if p[i] == p[j+1] {
			j++
		}
		next[i] = j
	}
}

// KMP匹配
func Matching() {
	for i, j := 1, 0; i < len(s)-1; i++ {
		for j > 0 && s[i] != p[j+1] {
			j = next[j]
		}
		if s[i] == p[j+1] {
			j++
		}
		if j == len(p)-1 {
			j = next[j]
			// 匹配成功后的逻辑
		}
	}
}

6.trie树

package datastructure

/*
0号节点既是根节点，又是空节点
son存储树中每个节点的子节点
cnt存储以每个节点结尾的单词数量
*/
var (
	son [][26]int
	cnt []int
	// idx int
)

// 插入一个字符串
func InsertStr(str string) {
	p := 0
	for i := 0; i < len(str); i++ {
		u := int(str[i] - 'a')
		if son[p][u] == 0 {
			idx++
			son[p][u] = idx
		}
		p = son[p][u]
	}
	cnt[p]++
}

// 查询字符串出现的次数
func QueryTrie(str string) int {
	p := 0
	for i := 0; i < len(str); i++ {
		u := int(str[i] - 'a')
		if son[p][u] == 0 {
			return 0
		}
		p = son[p][u]
	}
	return cnt[p]
}

7.并查集

package datastructure

/*
朴素并查集
pa 存储每个点的祖宗节点
size 表示祖宗节点所在集合的点的数量。size只有祖宗节点的才有意义
*/

var pa, size []int

// 返回x的祖宗节点
func Find(x int) int {
	if pa[x] != x {
		pa[x] = Find(pa[x])
	}
	return pa[x]
}

// 初始化，假定节点编号是1~n
func init() {
	for i := 1; i <= n; i++ {
		pa[i] = i
		// size初始化
		size[i] = 1
	}
}

// 合并a和b所在的两个集合
func MergeSet(a, b int) {
	pa[Find(a)] = Find(b)
	// 处理size
	size[Find(b)] += size[Find(a)]
}

8.堆

package datastructure

/*
heap 存储堆中的值，和h[1]是对顶，x的左儿子是2x，x的右儿子是2x+1
sizeH 表示堆的大小
*/

var (
	heap  []int
	sizeH int
)

// 向下排序
func Down(u int) {
	t := u
	if u*2 <= sizeH && heap[u*2] < heap[t] {
		t = u * 2
	}

	if u*2+1 <= sizeH && heap[u*2+1] < heap[t] {
		t = u*2 + 1
	}
	if t != u {
		heap[t], heap[u] = heap[u], heap[t]
	}
}

// 向上排序
func Up(u int) {
	for u/2 > 0 && heap[u] < heap[u/2] {
		heap[u], heap[u/2] = heap[u/2], heap[u]
		u /= 2
	}
}

// O(n)建堆
func Build() {
	for i := n / 2; i > 0; i-- {
		Down(i)
	}
}

9.一般哈希

package datastructure

/*
1.拉链法
mod 为模数
*/
var h []int

const mod = 1e6

//向哈希表中插入一个数
func InsertHash(x int) {
	k := (x%mod + mod) % mod
	e[idx] = x
	ne[idx] = h[k]
	h[k] = idx
	idx++
}

// 在hash表中查询某个数是否存在
func FindHash_1(x int) bool {
	k := (x%mod + mod) % mod
	for i := h[k]; i != -1; i = ne[i] {
		if e[i] == x {
			return true
		}
	}
	return false
}

/*
2.开放寻址法
N 为h的最大长度
*/
var N int

// 如果x在哈希表中，返回x的下标，如果不在哈希表中，返回x应该插入的位置
func FindHash_2(x int) int {
	k := (x%mod + mod) % mod
	for h[k] != 0 && h[k] != x {
		k++
		if k == N {
			k = 0
		}
	}
	return k
}

10.字符串哈希

package datastructure

/*
核心思想：将字符串看成是P进制数，P的经验值是131或者13331
hash[k] 存储字符串前k个字母的哈希值
pe[k]存储P的k次方
*/
const P = 131

var (
	hash, pe []uint64
	str      string
)

// 初始化
func init() {
	for i := 1; i <= n; i++ {
		hash[i] = hash[i-1]*P + uint64(str[i])
		pe[i] = pe[i-1] * P
	}
}

// 计算子串str[l:r]的哈希值
func GetHash(l, r int) uint64 {
	return hash[r] - hash[l-1]*pe[r-l+1]
}