1.Trie树-字典树

用来高效的存储和查找字符串集合的数据结构
图片说明

const N int = 100010
//下标是0的节点，既是根节点，又是空节点
var son [N][26]int //串中每个节点的所有儿子，son[n][i]指的是节点n的儿子i,用来存储其在树中的下标，每个节点最多连26条边，因为一共26个字母
var cnt [N]int    //以当前这个点结尾的单词有多少个
var idx int       //存储当前用到的下标，trie树从空开始进行插入，不断地插入作为树的第几个节点
func insert(str []byte){
    p := 0
    for i:= 0 ; i < len(str) ; i++ {
        u := str[i]-'a'
        if son[p][u]==0 {//如果p节点不存在u儿子
            idx ++
            son[p][u] = idx    
        }
        p = son[p][u]
    }
    cnt[p]++
}
func query(str []byte) int {//字符串str出现的次数
    p := 0
    for i:= 0 ; i < len(str) ; i++ {
        u := str[i]-'a'
        if son[p][u] == 0 {
            return 0
        }
        p = son[p][u]
    }
    return cnt[p]
}

2.并查集 --重点重点

用来快速的处理：
1、将两个集合合并
2、询问两个元素是否在一个集合当中
并查集可以在接近O(1)的时间复杂度内完成上述两个操作

基本原理：用树的形式来维护集合，树的根节点的编号就是整个集合的编号，每个节点存储其父节点p[x]
图片说明
问题1：如何判断节点是不是根节点 : if p[x] == x
问题2：如何求x的集合的编号： for p[x] != x {x = p[x]}
问题3：如何合并两个集合，在两个树之间加一条边：p[x]是x的集合编号，p[y]是y的集合编号，p[x]=y

目前针对解决问题2的时间复杂度比较高，对此可以进行优化：
当我们搜索找到x所在树的根节点后，我们将x所在的整个路径上所有节点都直接指向根节点
图片说明

维护每个集合中节点的个数，在这里我们只需要保持根节点的size是正确的即可
图片说明

3.堆（手写堆）

如何手写一个堆？
基本操作：
1、插入一个数
2、求这个集合中的最小值
3、删除最小值
4、删除任意一个元素
5、修改任意一个元素

堆的基本结构

堆是一棵完全二叉树
以小根堆为例，每个节点的值都是小于等于左右儿子的值，所以根节点是整棵树中最小的值
图片说明

堆的存储

使用一维数组来进行存储
图片说明

基本操作

down（x）
{
将节点x下移，如果节点x变大，则每次都和左右儿子比较，选择最小的那个进行交换，直到找到属于自己的位置
}
up(x)
{
将节点x上移，将x变小，则每次和父节点进行比较，如果我比父节点小，则和父节点进行交换
}
heap为堆，size是当前堆的大小
下标是从1开始的

1、插入一个数
size++
heap[size]=x
up(size)
2、求这个集合中的最小值
heap[1]
3、删除最小值
heap[1]=heap[size]
size--
down(heap[1])
4、删除任意一个元素
heap[k] = heap[size]
size--
if 值变大{
    down(heap[k])
}else{
    up(heap[k]) 
}
5、修改任意一个元素
heap[k]=x
if 值变大{
    down(heap[k])
}else{
    up(heap[k])
}

图片说明

//后续操作

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}

4 hash表

hash表最主要的作用是将大规模数据映射到小的空间中

哈希表的存储结构

将值映射到hash表中可能会引起冲突，根据处理冲突的方式不同，将hash表的存储分为两种：

开放寻址法

图片说明
取模的数一般是一个质数，并且离2的整数次幂尽可能远一些

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];
int insert
int find(int x)//如果x存在，则返回它当前所在的位置，否则返回她应该存储的位置
{

    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;//插入操作
        else //查找操作 
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

拉链法

取模的数一般取一个质数
图片说明

#include <cstring>
#include <iostream>

using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

int main()
{
    int n;
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}