2）数据结构

文章目录

• 双链表
• 单调栈
• 单调队列（滑动窗口）
• KMP
• Trie树
• • Trie 字符串统计
  • 最大异或对
• 并查集
• • 合并集合
  • 连通块中点的数量
  • 食物链
• 堆
• • 堆排序
  • 模拟堆
• 哈希表
• • 模拟散列表
  • 字符串哈希

---

双指针、单调栈、单调队列：先想暴力做法，然后根据单调性进行优化改造！

双链表

#include

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;
        
        if(op == "L"){
            
            cin >> x;
            insert(0, x);
        }else if(op == "R"){
            
            cin >> x;
            insert(l[1], x);
        }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

using namespace std;

const int N = 100010;

int stk[N], tt;

int main(){
    
    int n;
    scanf("%d", &n);
    
    // 求x左边的比x小的离x最近的数
    for(int i = 0; i < n; i++){
        
        int x;
        scanf("%d", &x);
        
        while(tt && stk[tt]>=x) tt--;
        if(tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        
        stk[++tt] = x;
    }
    
    return 0;
}

单调队列（滑动窗口）

#include

using namespace std;

const int N = 1000010;

int a[N], q[N];

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++){
        
        // 保证hh指向的头部在以i为尾区间长度为k的区间内部
        while(hh <= tt && i - k + 1 > q[hh]) hh++;  // 这里用 if 也可以
        
        // 求最小值时, 窗口向后滑动, 此时如果a[i] <= a[q[tt]], 
        // 包括当前窗口（或者项后滑动时），tt位置的值对min值没有贡献,
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        
        // 当 i < k 时, 不构成一个长度为k的滑动窗口(i从0开始)
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    
    puts("");
    
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++){
        
        while(hh <= tt && q[hh] < i - k + 1) 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

#include

using namespace std;

const int N = 100010, M = 1000010;

char a[N], s[M];
int n, m;
int ne[N];

int main(){
    
    scanf("%d%s%d%s", &n, a+1, &m, s+1);
    
    // ne[1]=0;
    // 求next数组
    for(int i = 2,j = 0;i <= n; i++){
        
        while(j && a[i]!=a[j+1]) j = ne[j];
        if(a[i]==a[j+1]) j++;
        
        ne[i] = j;
    }
    
    // kmp
    for(int i = 1, j = 0; i <= m; i++){
        
        while(j && s[i]!=a[j+1]) j = ne[j];
        if(s[i]==a[j+1]) j++;
        
        if(j == n){
            printf("%d ", i - n);
            j = ne[j];
        } 
    }
    
    return 0;
}

Trie树 Trie 字符串统计

// I x 向集合中插入一个字符串 x；
// Q x 询问一个字符串在集合中出现了多少次。



#include

using namespace std;

const int N = 100010;

// son[i][j] 代表当前第i个节点的第j个子分支存储的子节点的索引
// cnt[i] 代表以从根节点出发到编号为i的节点结束的字符串的数量
// idx代表第几个新节点
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[]){
    
    // 根节点为0
    int p = 0;
    for(int i = 0; str[i]; i++){
        
        // 算出在26个字母中的位置
        int u = str[i] - 'a';
        
        // 如果当前节点的u这个位置未出现过, 则添加新节点
        // idx代表新节点的索引
        if(!son[p][u]) son[p][u] = ++idx;
        
        // 指向他的子节点
        p = son[p][u];
    }
    
    // 以p节点结束的字符串++
    cnt[p]++;
}

// 查询某字符串出现的次数
int query(char str[]){
    
    int p = 0;
    for(int i = 0; str[i]; i++){
        
        int u = str[i] - 'a';
        
        if(!son[p][u]) return 0;
        
        p = son[p][u];
    }
    
    return cnt[p];
}

int main(){
    
    int n;
    scanf("%d", &n);
    while(n--){
        
        char op[2];
        scanf("%s%s", op, str);
        
        if(op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
}

最大异或对

#include
#include

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x){
    
    int p = 0;
    
    for(int i = 30; i >= 0; i--){
        
        int t = x >> i & 1;
        
        if(!son[p][t]){
            
            son[p][t] = ++idx;
        }
        
        p = son[p][t];
    }
}

int search(int x){
    
    int p = 0, res = 0;
    
    // res记录异或后的结果
    // 所以当树上的当前和x的当前为相异时, res的此位被标记为1,否则为0;
    for(int i = 30; i >= 0; i--){
        
        int t = x >> i & 1;
        
        // 看当前位的取反是否存在
        if(son[p][!t]){
            
            //res += 1 << i;
            res = res << 1 | 1;　 // res = res * 2 + !t
            // 注意此处是!t
            p = son[p][!t];
        }else{
            
            res = res << 1;
            p = son[p][t];
        }
    }
    
    return res;
}


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

并查集 合并集合

#include

using namespace std;

const int N = 100010;

int p[N];

int find(int x){
    
    if(p[x] != x) p[x] = find(p[x]);  // 路径压缩
    return p[x];
}

int main(){
    
    int n, m;
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) p[i] = i;  // 初始化
    
    
    while(m--){
        
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'M') p[find(a)] = find(b);
        else{
            
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

连通块中点的数量

#include

using namespace std;

const int N = 100010;

int n, m;

// 父节点 // 以i节点为根节点的块的节点数量
int p[N], cnt[N];


int find(int x){
    
    // 路径压缩
    if(x != p[x]) p[x] = find(p[x]);
    
    return p[x];
}


int main(){
    
    cin >> n >> m;
    
    // 初始化
    for(int i = 1; i <= n; i++){
        
        p[i] = i;
        cnt[i] = 1;
    }
    
    while(m--){
        
        string op;
        int a, b;
        
        cin >> op;
        
        if(op == "C"){
            
            cin >> a >> b;
            
            a = find(a), b = find(b);
            if(a != b){
                
                p[a] = b;
                cnt[b] += cnt[a];
                // cnt[a] = 1;
            }    
        }else if(op == "Q1"){
            
            cin >> a >> b;
            
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        
        }else{
            
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
        
    }
    
    return 0;
}

食物链

#include

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x){
    
    if(x != p[x]){
        // 先记录上当前父节点
        // 防止路径压缩后,指向根节点后父节点信息丢失(要根据父节点求d[x] -- 到根节点的距离)
        int t = p[x];
        // 路径压缩
        p[x] = find(p[x]);
        // 到根节点的距离等于到父节点的距离 + 父节点到根节点的距离
        d[x] += d[t]; 
    }
    
    return p[x];
}

int main(){
    
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) p[i] = i;
    
    int res = 0;
    while(m--){
        
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        
        if(x > n || y > n) res++;
        else{
            
            int px = find(x), py = find(y);
            if(t == 1){
                // 如果x,y在一个集合,并且不是同一类
                if(px == py && (d[x] - d[y]) % 3) res++;
                else if(px != py){
                    // 如果未在一个集合,则先合并,再计算的d[px]
                    p[px] = py;
                    // (d[px] + d[x] - d[y]) % 3 == 0 
                    d[px] = d[y] - d[x];
                }
            }else{ // x吃y
                
                // 两个在一个集合,并且x不是y的上一个类(不为0则不是上一个类)
                if(px == py && (d[x] - d[y] - 1) % 3) res++;
                else if(px != py){
                    
                    p[px] = py;
                    // (d[px] + d[x] - d[y] - 1) % 3 = 0
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    
    printf("%d", res);
    
    return 0;
}

堆 堆排序

// 小根堆
#include
#include

using namespace std;

const int N = 100010;

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

// 下放 *** 作
void down(int u){
    
    // 先默认h[t = 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(t != u){
        
        swap(h[t], h[u]);
        down(t);
    }
}


int main(){
    
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;
    
    for(int i = n / 2; i; i--) down(i);
    
    while(m--){
        
        // 输出根节点（最小值）
        printf("%d ", h[1]);
        // 将最后一个叶子节点的值放到根节点
        // 并进行下放
        h[1] = h[cnt--];
        down(1);
    }
    
    puts("");
    
    return 0;
}

模拟堆

#include
#include
#include

using namespace std;

const int N = 100010;

// m: 当前的的元素是第k个插入的元素
// cnt: 堆中元素的个数(指向堆中的最后一个元素位置)
int n, m, cnt;

// h是原数组(堆)
// ph[m] = cnt, 代表第m个插入的元素是堆中的cnt位置
// hp[cnt] = m 代表堆中的cnt位置的元素是第m个插入的
int h[N], ph[N], hp[N];

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(t != u){
        
        heap_swap(t, u);
        down(t);
    }
}

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


int main(){
    
    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;
}

哈希表 模拟散列表

开放寻址法

// 开放寻址法(N的值取大于2C的第一个素数)

#include
#include

using namespace std;

// N一般取一个较大的素数
const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x){
    // 保证映射到的地址大于等于零,小于N
    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);
        
        // 找到第一个null的位置插入
        if(op[0] == 'I') h[find(x)] = x;
        else{
            
            if(h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    
    return 0;
}

拉链法

// 拉链法(N的值取大于 C 的第一个素数)

#include
#include

using namespace std;

// N一般取一个较大的素数
const int N = 100003;

// h[]: hash表,存储的当前链的第一个元素的下标
// e[]: 第i个插入的数的值(下标为i的对应的值)
// ne[]: 映射到同一位置处的下一个节点的地址
// idx: 第几个插入的数
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(){
    
    // 按字节填充
    memset(h, -1, sizeof(h));
    
    int n;
    scanf("%d", &n);
    
    while(n--){
        
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if(op[0] == 'I') insert(x);
        else{
            
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

字符串哈希

#include

using namespace std;

// 2^64,让其自然溢出,相当于对2^64取mod
typedef unsigned long long ULL;

// P(进制数)一般取131/13331
const int N = 100010, P = 131;

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

// 求[l, r]区间的字符串的hash值
ULL get(int l, int r){
    
    // 1 ~ (l - 1)(从高位到低位)
    // 1 ~ r (从高位到低位)
    // L ~ R (相当于把h[l - 1]左移动(r - (l - 1))位, 然后用h[r]减去)
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
    
    scanf("%d%d", &n, &m);
    scanf("%s", 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;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    
    return 0;
}