模板-第二讲数据结构

https://www.acwing.com/activity/content/punch_the_clock/11/

单链表

数组实现链表

#include <iostream>

using namespace std; 
const int N = 1e5 + 10;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init(){
    head = -1;
    idx = 1;
}

// 将x插到头结点
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 将x插到下标是k的点后面
void insert(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 将下标是k的点后面的点删掉
void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    int m;
    cin >> m;
    init();
    while(m--){
        char oper;
        int k, x;
        cin >> oper;
        if(oper == 'H'){
            cin >> x;
            add_to_head(x);
        }else if(oper == 'D'){
            cin >> k;
            if(k == 0) head = ne[head];
            else remove(k);
        }else{
            cin >> k >> x;
            insert(k, x);
        }
    }
    for(int i = head; i != -1; i = ne[i]){
        cout << e[i] << " ";
    }
    return 0;
}

双链表

#include <iostream>

using namespace std; 
const int N = 1e5 + 10;

int m, k, x;
string oper;
int e[N], l[N], r[N], idx;

//在右边插入 
void insert(int k, int x){
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    cin >> m;
    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0, idx = 2;
    while(m--){
        cin >> oper;
        if(oper == "L"){
            cin >> x;
            insert(0, x);
        }else if(oper == "R"){
            cin >> x;
            insert(l[1], x);
        }else if(oper == "D"){
            cin >> k;
            remove(k + 1);
        }else if(oper == "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 <bits/stdc++.h>

using namespace std; 
const int N = 1e5 + 10;

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

//在尾部插入 
void push(int x){
    e[idx] = x;
    idx++;
}

void pop(){
    idx--;
}

int get_top(){
    return e[idx - 1];
}

bool is_Empty(){
    return idx <= 0;
}

int main(){
    int m, x;
    cin >> m;
    string oper;
    idx = 0;
    while(m--){
        cin >> oper;
        if(oper == "push"){
            cin >> x;
            push(x);
        }else if(oper == "pop"){
            pop();
        }else if(oper == "empty"){
            if(is_Empty()) printf("YES\n");
            else printf("NO\n");
        }else{
            cout << get_top() << endl;
        }
    }
}

表达式求值

#include <bits/stdc++.h>

using namespace std; 

stack<int> num;
stack<char> op;

void eval(){
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main(){
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n; i++){
        auto c = s[i];
        if(isdigit(c)){
            int x = 0, j = i;
            while(j < n && isdigit(s[j])){
                x = x * 10 + s[j++] - '0';
            }
            num.push(x);
            i = j - 1;
        }else if(c == '('){
            op.push(c);
        }else if(c == ')'){
            while(op.top() != '(') eval();
            op.pop();
        }else{
            while(op.size() && op.top() != '(' && pr[c] <= pr[op.top()]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();
    printf("%d\n", num.top());
}

模拟队列

int head, e[N], idx;

//在尾部插入 
void push(int x){
    e[idx] = x;
    idx++;
}

void pop(){
    head++;
}

int get_top(){
    return e[head];
}

bool is_Empty(){
    return head >= idx;
}

单调栈

int stk[N], tt;

int main(){
    int n;
    cin >> n;
    tt = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt--;
        if(tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        stk[++tt] = x; 
    }
    return 0;    
}

单调队列

#include <bits/stdc++.h>

using namespace std; 
const int N = 1e6 + 10;

int a[N], q[N]; 

int main(){
    int n, k;
    cin >> n >> k;
    int minn = INT_MIN, maxn = INT_MAX;
    for(int i = 0; i < n; i++){
        cin >> 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]]);
    }
    printf("\n");
    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]]);
    }
    return 0;    
}

KMP

时间复杂度O(n+m)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 1000010; 

int n, m;
char s[M], p[N];
int nextt[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1; //字符串从下标1开始 

    //计算next数组
    for(int i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]) j = nextt[j];
        if(p[i] == p[j + 1]) j++;
        nextt[i] = j;
    }

    //KMP匹配过程
    for(int i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j + 1]) j = nextt[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n){
            printf("%d ", i - n); //这里要求输出的下标从0开始计数 
            j = nextt[j]; 
        }
    }     
    return 0;
}

Trie

高效地存储和查找字符串集合的数据结构

#include <bits/stdc++.h>

using namespace std; 
const int N = 1e5 + 10;

int n;
string x;
char op;
int son[N][26], cnt[N], idx; //idx是节点序号，son[i][u]代表值为u的节点i的子节点 cnt[i]代表以节点i结尾的字符串个数

void insert(string x){
    int p = 0;
    for(int i = 0; i < x.size(); i++){
        int u = x[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
} 

int query(string x){
    int p = 0;
    for(int i = 0; i < x.size(); i++){
        int u = x[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main(){
    cin >> n;
    while(n--){
        cin >> op >> x;
        if(op == 'I'){
            insert(x);
        }else{
            printf("%d\n", query(x));
        }
    }
    return 0;    
}

最大异或树

#include <bits/stdc++.h>

using namespace std; 
const int N = 1e5 + 10, M = 3100010;

int n;
int a[N], son[M][2], idx; //idx是节点序号，son[i][u]代表值为u的节点i的子节点 

void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i--){
        int &s = son[p][x >> i & 1]; //用 int & 是C++里的引用，和指针类似，定义的变量和赋值的变量指向同一块内存，一个改变，另一个也会改变。 
        if(!s) s = ++idx;
        p = s;
    }
} 

int search(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--){
        int u = x >> i & 1;
        if(son[p][!u]) {
            res += 1 << i;
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return res;
}

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

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, search(a[i]));
    printf("%d\n", res);
    return 0;    
}

并查集

#include <bits/stdc++.h>

using namespace std; 
const int N = 1e5 + 10;

int p[N];

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

int main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    while(m--){
        char op;
        cin >> op >> a >> b;
        if(op == 'M'){
            p[find(a)] = find(b);
        }else{
            if(find(a) == find(b)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;    
}

堆排序和模拟堆

图片说明

#include <bits/stdc++.h>

using namespace std; 
const int N = 1e5 + 10;

int n, m;
int h[N], cnt;

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

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

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> h[i];
    cnt = n;
    for(int i = n / 2; i; i--) down(i);
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[cnt];
        cnt--;
        down(1);
    }
    return 0;    
}

哈希表

哈希表的存储结构
1. 开放寻址法
  提问：“开放寻址法的那个memset填充h不应该是0x3f3f3f3f吗？为什么变成了0x3f？，还有奥，按照这个办法来说的话，当h数组满了的话，应该会陷入死循环把”
  回答：①memset是按字节来初始化的，int中有四个字节，初始化成0x3f就是将每个字节都初始化成0x3f，所以每个int就是 0x3f3f3f3f。
  ②数组长度一般开到个数上限的2-3倍。
2. 拉链法
字符串哈希方式

开放寻址法，y总还讲了拉链法，代码也有，可以去看看。

#include <bits/stdc++.h>

using namespace std; 
const int N = 200003, null = 0x3f3f3f3f;

int n, x;
int h[N];  

int find(int 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));
    cin >> n;
    while(n--){
        string op;
        cin >> op >> x;
        if(op == "I"){
            h[find(x)] = x;
        }else{
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;    
}

字符串哈希

#include <bits/stdc++.h>

using namespace std; 
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

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

int main(){
    cin >> n >> m;
    cin >> str + 1;
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while(m--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");;
    }
    return 0;    
}

模板-第二讲 数据结构

单链表

双链表

模拟栈

表达式求值

模拟队列

单调栈

单调队列

KMP

Trie

最大异或树

并查集

堆排序和模拟堆

哈希表

模板-第二讲数据结构