单链表

#include<iostream>
using namespace std;
const int N = 100010;
int idx, a[N], ae[N]; 
int head;
// idx 表示当前还未填入的数，可以表示第几个插入的顺序，不过从0开始
// a[i]表示第 i + 1 次插入的数值,ae[i] 表示当前元素的下一个元素在 a 数组中的下标idx
void add_to_head(int x)
{
    a[idx] = x;
    ae[idx] = head; // 如果只插入1个节点，那么此节点指向-1，说明下一个j
    head = idx;
    idx++;
}

void add(int k, int x) // 在第k(从0a)个插入的数后插入x
{
    a[idx] = x;
    ae[idx] = ae[k];
    ae[k] = idx;
    idx++;
}

void delt(int k) // 删除第k个插入的数后面的数
{
    ae[k] = ae[ae[k]]; // 指向把第k个数指向下下个下标位置
}


int main(){
    int n;
    idx = 0, head = -1; // 头结点刚开始没有
    cin >> n;

    while(n--)
    {
        char op;
        cin >> op;
        int k, x;
        if(op == 'H')
        {

            cin >> x;
            add_to_head(x);
        }
        if(op == 'D')
        {

            cin >> k;
            if(!k)  head = ae[head]; // k为0时删除头节点,head原来指向的第一个节点下标，那么head的值就是第一个节点的下标
            // 所以ne[head]是第二个节点的下标
             delt(k-1); // 第k个插入的数下标为 k - 1
        }
        else if(op == 'I'){
            int k, x;
            cin>>k>>x;
            add(k-1,x);
        }

    }
    for(int i=head;i!=-1;i=ae[i])
      cout<<a[i]<<" ";

    return 0;
}

双链表

题目： 双链表

• 双链表初始化时用0表示左端点、1表示右端点。无数据，真正的数据从e[2]开始。
• l、r数组表示某个端点左边和右边分别指向端点的索引idx

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx;

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

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main()
{
    cin >> m;

    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        // 在链表最左端插入x
        if (op == "L")
        {
            cin >> x;
            insert(0, x); // 在0端点右边插入
        }
        // 在链表最右端插入x
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x); // 在1端点左边的l[1]右边插入
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

模拟栈

题目： 模拟栈

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
// 让一个指针始终指向栈顶
int top = 0;

void push(int x) {
    a[++top] = x;
}

bool empty() {
    if(!top)   return true;
    else    return false;
}

void pop() {
    if(!empty())    top--;
}

int query() {
    return a[top];
}
int main() {
    int n;
    cin >> n;
    while(n--) {
        string op;
        int x;
        cin >> op;
        if(op == "push") {
            cin >> x;
            push(x);
        }else if(op == "query") {
            cout << query() << endl;
        }else if(op == "pop") {
            pop();
        }else if(op == "empty") {
            if(empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

    return 0;
}

模拟队列

题目： 模拟队列

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int hh = 1, tt = 0; // hh队头 tt队尾
void push(int x) {
    a[++tt] = x;
}

bool empty() {
    if(hh <= tt)   return false;
    return true;
}

void pop() {
    if(!empty())
        hh++; // 对头向右移动
}


int query() {
    return a[hh]; // i指向对头元素
}

int main() {
    int n;
    cin >> n;
    string op;
    int x;
    while(n--) {
        cin >> op;
        if(op == "push") {
            cin >> x;
            push(x);
        }
        else if(op == "pop")    pop();
        else if(op == "empty") {
            if(empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }else if(op == "query") cout << query() << endl;
    }
    return 0;
}

单调栈

题目： 单调栈

#include<iostream>
#include<stack>
using namespace std;
const int N = 100010;
int a[N];
stack<int> s;
// 维护一个单调递增的栈,当栈顶元素大于(入栈元素)出栈，则入栈时，栈顶是第一个小于入栈元素的值
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)    {
        scanf("%d",&a[i]);
    }
    s.push(a[0]);
    cout << "-1 ";
    for(int i = 1;i < n;i++) {
        // while(a[i] <= s.top() && !s.empty()) {
        //     s.pop(); // 出栈
        // } 这是错误的写法
        while(!s.empty() && a[i] <= s.top())    s.pop();
        s.push(a[i]);
    }
    return 0;
}

单调队列

• 单调队列可以维护一定范围数量的单调序列,如滑动窗口。

题目： 单调队列

#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N]; // q数组存放单调队列的下标

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int hh = 0, tt = -1; // 维护单调队列的下标
    for (int i = 0; i < n; i ++ )
    {
        // 如果队列中的数超过上限了，队头出队
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ; // 若加入的数小于队尾,我们要保证队首是最小的数
        q[ ++ tt] = i; // 下标入队尾

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}

KMP

题目： KMP字符串

#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
int ne[N];
char p[N], s[M]; // p是模式串、s是匹配串
int main() {
    int n,m;
    cin >> n >> p+1 >> m >> s+1;
    // 求next数组,模式串与自己匹配
    for(int i = 2, j = 0;i <= n;i++) {
        while(j && p[i] != p[j+1])  j = ne[j];
        if(p[i] == p[j+1])   j++;
        ne[i] = j;
    }

    // 利用next数组匹配需要匹配的串
    for(int i = 1,j = 0; i <= m;i++) {
        while(j && s[i] != p[j+1])  j = ne[j];
        if(s[i] == p[j+1])  j++;
        if(j == n) {
            cout << i - n << " "; // 本来是 i -n + 1,但我们初始时下标为1，本题是0
            j = ne[j]; // 匹配下一个,从j位置开始，当前j相当于从ne[j]的位置再次匹配
        }
    }

    return 0;
}

Trie树

题目： Trie树

#include <iostream>
using namespace std;
const int N = 100010;
int children[N][26], cnt[N], idx;
char s[N];

void insert(char *s) {
    int p = 0; // idx从0开始遍历，根节点没有数据
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!children[p][u])
            children[p][u] = ++idx; // 增加 p->u 的边
        p = children[p][u]; // 从当前索引继续查找或插入
    }
    cnt[p]++; // 最后p代表最后字符节点的索引值
}

int query(char *s) {
    int p = 0; // 从根节点开始查找
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!children[p][u])
            return 0; // 中间值都匹配，就不用往下查找了
        p = children[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    char c;
    cin >> n;
    while (n--) {
        cin >> c;
        if (c == 'I') {
            cin >> s;
            insert(s);
        }

        else if (c == 'Q') {
            cin >> s;
            cout << query(s) << endl;
        }

    }

    return 0;
}

并查集

题目： 连通块中点的个数

void init(int n)
{
    for (int i = 1; i <= n; i ++) fa[i] = i;
}

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int find(int x) {
    if(fa[x] != x)  fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y)
{
    fa[find(x)] = find(y);
}

// 查询是否在同一集合
bool query(int i, int j) {
    if(find(i) == find(j))  return true;
    return false;
}

带权并查集

题目： 食物链

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]]; // d[x]表示到合并后到根节点的距离
        p[x] = t;
    }
    return p[x];
}
// 合并函数视具体题目而定

模拟堆

• 下标从1开始

题目： 模拟堆

#include<iostream>
#include<string>
using namespace std;
const int N = 100010;
int h[N], mysize, cnt; // cnt记录第k次插入
int ph[N], hp[N];
// ph[k]: 第k个插入 --> 下标
// hp[k]: 下标k -->第几个插入
// 交换堆中的两个数，那么下标和第几次插入的关系也要变化
void swap_heap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a],h[b]); // 交换数值
}

void down(int i) {
    int t = i;
    if(2 * i <= mysize && h[2 * i] < h[t])  t = 2 * i;
    if(2 * i + 1 <= mysize && h[2 * i + 1] < h[t])  t = 2 * i + 1;
    if(t != i) {
        swap_heap(t, i);
        down(t);
    }
}

void up(int i) {
    while(i / 2 && h[i] < h[i / 2]) {
        swap_heap(i, i / 2);
        i /= 2; // 上升到父节点
    }
}
// 插入一个数,在最后插入
void insert(int x) {
    mysize++; // 记录下标
    cnt++; // 第几次插入
    ph[cnt] = mysize, hp[mysize] = cnt;
    h[mysize] = x;
    up(mysize);
}
// 删除第k个插入的数
void del(int k) {
    k = ph[k]; // 第k个插入的数对应的下标
    swap_heap(k, mysize);
    mysize--;
    down(k);
    up(k);
}
// 删除最小值，堆顶
void Del() {
    swap_heap(1, mysize);
    mysize--;
    down(1);
}

// 修改第k个插入的数
void change(int k, int x) {
    k = ph[k]; // 第k个插入的数对应的下标
    h[k] = x;
    down(k);
    up(k);
}
int main() {
    int n;
    cin >> n;
    string op;
    int x, y;
    while(n--) {
        cin >> op;
        if(op == "I") {
            cin >> x;
            insert(x);
        }else if(op == "PM") {
            cout << h[1] << endl;
        }else if(op == "D") {
            cin >> x;
            del(x);
        }else if(op == "DM") {
            Del();
        }else {
            cin >> x >> y;
            change(x, y);
        }
    }
    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; // e数组是存取插入所有数的数据
    ne[idx] = h[k]; // 开始终点为-1，指向上一个结点,记录单链表
    // 的上一个结点
    h[k] = idx++; // 结点递增
    /h[k]表示在这个节点上的链表的最后一个节点的idx
}
// 散列表查询
bool find(int x)
{
    // 找到所在的槽
    int k = (x%N+N)%N;
    for(int = h[k];i != -1;i=ne[i])
    {
        if(e[i] == x)   return true;
    }
    return false;
}
int main()
{
    // 先把每个槽都置为-1，因为没有上个结点存在
    memset(h,-1,sizeof h);

}

开放寻址法

在一个数组中存数，如果当前位置没有人，则可以插入；否则一直向后查找，直到找到一个空位进行插入。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nul = 0x3f3f3f3f;
// N 应该为数据总数的整数倍数
int h[N];

int find(int x) // 查找和插入通用的函数
{
    int k = (x%N+N)%N;// 先锁定下标,再找空位
    while(h[k] != nul && h[k]!=x)
    {
        k++;
        if(k==N) k = 0; // 到尾了，返回头部进行插入
    }
    return k;
}
int main()
{
    memset(h,0x3f,sizeof h);
    int x;
    cin >> x;
    int k = find(x);
    // 插入
    h[k] = x; // 找到可以插入的空位

    // 查询
    if(h[k] != nul) puts("存在该数字");
    // 如果当前的位置为空位，说明之前这个数字并没有进行插入，所以没有出现过

}

字符串哈希

将字符串映射为一个数字

前缀和公式 $h[i+1]=h[i]×P+s[i]h[i+1]=h[i]×P+s[i] i∈[0,n−1]i∈[0,n−1] $h为前缀和数组，s为字符串数组
区间和公式 $h[l,r]=h[r]−h[l−1]×P^{r−l+1}$

#include<iostream>
#include<cstring>
typedef unsigned long long ull;
using namespace std;
const int N = 100010, P = 131;
ull h[N], p[N]; // h[N]是字符串哈希值得前缀和

ull query(int l, int r) {
    return  h[r] - h[l-1] * p[r-l+1];     
}

int main() {
    int n, m;
    cin >> n >> m;
    string x;
    cin >> x;
    h[0] = 0, p[0] = 1;
    for(int i = 0;i < n;i++) {
        p[i+1] = p[i] * P;
        h[i + 1] = h[i] * P + x[i];  // hash数组下标从1开始
    }
    while(m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(query(l1, r1) == query(l2, r2))  cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}