template:数据结构

双链表

#include<iostream>
using namespace std;
const int N = 100010;
int m;
int e[N],l[N],r[N],idx;
void insert(int k,int x)  //第k个节点右边插入一个数
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx;
    idx++;

}
void del(int k)
{

    l[r[k]]=l[k];
    r[l[k]]=r[k];
}
void init()
{
    r[0]=1;
    l[1]=0;

    idx=2;
}
C++

模拟栈

s.empty()判断非空

#include <iostream>
#include <stack>

int main() {
    // 创建栈（默认使用deque）
    std::stack<int> s;
    
    // 压栈操作
    s.push(10);
    s.push(20);
    s.push(30);

    // 查看栈顶
    std::cout << "栈顶元素: " << s.top() << std::endl; // 30

    // 出栈操作
    s.pop();
    std::cout << "弹出后栈顶: " << s.top() << std::endl; // 20
 
    return 0;
}

C++

模拟队列

q.empty()判断非空

#include<iostream>
#include<string>
using namespace std;
const int N=100001;
int a[N],hh=0,tt=-1; //定义队头对位俩指针，这样初始化，当hh==tt队内有一个元素，当hh>tt的时候·队内无元素。
int main()
{
    int M;
    cin>>M;
    for(int i=0;i<M;i++)
    {
        string s;
        cin>> s;
        if(s == "push")
        {
            int x; cin>>x;
            tt++;
            a[tt]= x;
        }
        else if(s=="empty")
        {
            if(hh>tt) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else if(s=="pop")
        {
            hh++;
        }
        else{
            cout<<a[hh]<<endl;
        }
    }
}
C++

单调栈

来源问题:给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

单调栈：用一个栈，维护一个单调的不定长序列，举个例子:

7 6 2 1 3 8 栈内维护降序列
7 7,6 7,6,2 7,6,2,1 7,6,3 8

手模一遍之后思路很清晰了，对所有数进行遍历，如果新数小于栈顶的数直接入栈，如果新数大于栈顶的数，则不断弹栈直到栈顶元素小于新数。

#include<iostream>
using namespace std;
const int N=1e5+10;
int s[N],top=-1;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) 
    {
        int x;
        scanf("%d",&x);
        if(top==-1) cout<<"-1"<<" ";
        else{
            while(s[top]>=x) top--;
            if(top>-1) cout<<s[top]<<" ";
            else cout<<"-1"<<" ";
        }
        s[++top]=x;
    }
}
C++

滑动窗口/单调双端队列

问题描述

给定一个大小为n ≤ 10⁶的数组。，有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。你只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。

以下是一个例子：

数组 2 6 5 7 8 6

每次的窗口中的值分别为 265 657 578 786

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

解决这一问题可以直接暴力搜索，但是时间复杂度近似于O(n²)。我们引入一种使用单调双端队列的方式，即维护一个定长k的升序/降序区间。首先来确定双端队列的结构。

• 使用数组模拟，队头在左，队尾在右，这是因为队尾会不断有新元素入队，倘若队尾在左的话会导致数组越界
• 符号法则:初始hh=0 tt=-1,检查队列非空判断hh<=tt即可，队尾入队总是使用q[++tt],队头出队总是使用hh++.
• 队尾出队的条件:队列不空且新元素更优，则队尾不断出队
• 队头出队的条件:滑出了窗口范围

本题的思路是，使用一个单调双端队列维护窗口内的一个单调序列，遍历每一个元素入队的过程，做两次判断，先判断队头元素是否需要滑出，再判断多少队尾元素会被等待入队的更优元素淘汰。然后入队新元素，如果i>k-1则输出队头元素。

从这一思路我们也可以看出，应当使用q存储元素在数组中的下标而非元素值本身，因为算法涉及到判断队头元素是否需要划出，这是不能使用元素值判断的，必须通过比较队头元素下标q[hh]和当前窗口尾坐标i-k+1来判断

综上所述，由于每个元素最多入队出队一次，因此本题得以在O(2N)的时间复杂度内求解

//队头是要出队的，hh放在左，tt放在右
#include<iostream>
using namespace std;
const int N=1e6+10;
//q[N]存存储元素的下标
int q[N],a[N],hh=0,tt=-1;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    //找最小元素
    for(int i=0;i<n;i++)
    {    
        //如果队列非空并且队头指标已经不在遍历范围之内，则队头出队
        if(tt>=hh&&q[hh]<i-k+1) hh++;
        //为ai入队做准备，如果队列非空，则一直排除更大的老元素
        while(tt>=hh&&a[q[tt]]>a[i]) tt--;
        //ai入队
        q[++tt]=i;
        //超过k个数才可以打印，这是为了防止开始的情况
        if(i>=k-1) cout<<a[q[hh]]<<' ';
        
    }
    hh=0,tt=-1;
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        if(tt>=hh&&q[hh]<i-k+1) hh++;
        while(tt>=hh&&a[q[tt]]<a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<' ';
    }

}


C++

KMP字符串

用小字符串在大字符串中匹配，找最开始出现的脚标。
算法的核心在于引入了next函数

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;

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

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    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;
    }

    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)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}
C++

trie树/字典树

需求描述：要求维护一个字符串集合，这个集合应当拥有两个功能

• 查询一个字符串是否出现过
• 查询一个字符串的出现次数

引入一种高效的数据结构：字典树

• 子节点的唯一标识是idx
• 儿子数组son[a][i]存储节点a沿着i这条边走到的子节点
• 每个节点最多有26个分支，用数字0_{25映射字母a}z
• idx=0为整个树的根

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N=1e5+10;
// son[a][i]  idx==a节点的第i个儿子的idx
// cnt：在idx结尾的数有多少个
int son[N][27],cnt[N]={0},idx=0;
void insertt(string str){
    int p=0;
    //p表示当前遍历到的节点
    //判断当前节点是否有对应的子节点，没有则创建，并把p更新为子节点
    for(int i=0;i<str.size();i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];  //为了单纯查找的情况的存在，不可写为 p=idx;
    }
    cnt[p]++;

}
int queryt(string str){
    int p=0;
    for(int i=0;i<str.size();i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) 
        {
            return 0;
        }
        p=son[p][u];
    }
    //最后在最终的字母对应的儿子的idx结尾
   return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string c, s;
        cin>>c>>s;
        if(c=="I") insertt(s);
        else cout<<queryt(s)<<endl;
    }
}
C++

并查集

并查集，顾名思义，它的功能应当有：

• 快速合并集合
• 查找两个元素是否属于同一个集合

考虑经典情形：一开始1-n n个数，处理多次合并与查询的操作

算法的核心在于：只存父节点，并通过find函数不断优化整个树的结构
只存父节点是因为只需要维护是否属于同一个集合的信息，不同以往的还需要维护整个序列的信息。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int p[N];
int find(int x)
{
    //在没找到祖宗节点之前，不停的对父节点调用find
    if(p[x]!=x) p[x]=find(p[x]);
    //找到祖宗节点后，返回祖宗节点，事实上前面的所有find函数收到的return都是祖宗节点
    //完成了find过程中的顺便优化
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        char c;
        cin>>c; 
        int a,b;
        scanf("%d%d",&a,&b);
        //合并a，b：a的祖宗节点归属于b的祖宗
        if(c=='M') p[find(a)]=find(b);
        else{
            if(find(a)==find(b)) cout<<"Yes";
            else cout<<"No";
            cout<<endl;
        }
    }
    
}

C++

堆排序

解决的问题：给定一个数列，从小到大输出前m个小的数
堆是一颗完全二叉树，任何一个节点的儿子都比父亲大，为此维护堆有两个基本的操作

void down(int u)
{
    //要找出三个里面的最小值作为新的父节点
    int t = u;
    //左儿子存在则判断左儿子是否更小
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    //右儿子存在则判断右儿子是否更小
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    //如果idx==u处的data被更新过了，继续down下去
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

//up操作相对比较简单，沿着一条线不停向上即可，注意到u/2可以包含u为奇数或者偶数的两种情况。
void up(int u)
{
    //
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}
C

两个函数接受的都是idx，考虑这个idx的节点data是否需要down下去或者up上来。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n,m;
//堆是一个完全二叉树，对于父节点u。定义其左儿子为2*u，右儿子为2*u+1，树的指向既定且无法修改，我们可以修改不同idx位置对应的data
int h[N],idx;
//把大数down到底下，确保这个局部的根节点是最小数，并继续进行递归。
void down(int u)
{
    int t=u;
    if(2*u<=idx&&h[2*u]<h[t]) t=2*u;
    if(2*u+1<=idx&&h[2*u+1]<h[t]) t=2*u+1;
    if(t!=u)
    {
        swap(h[t],h[u]);
        down(t);  //t位置变成了新的数，需要继续看看需不需要down。
    }
}
int main()
{
    cin>>n>>m;
    idx=n;
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    // n/2是最后一个有son的节点，从此开始down就可以建堆
    for(int i=n/2;i;i--) down(i);
    for(int i=0;i<m;i++)
    {
        printf("%d ",h[1]);
        h[1]=h[idx];
        idx--;
        down(1);
    }
}

C++

哈希

一般情况下的hash都可以用stl写，

#include<iostream>
#include<unordered_map>
unordered_map<int,bool> mp
int main()
{
    //类似数组的接口就可以完成基本的调用
    mp[1]=false;
    mp[2]=true;
}
C++

字符串哈希遇到基本需要手写

给定一个长度为 𝔫 的字符串，再给定 m 个询问，每个询问包含四个整数l₁, r₁, l₂, r₂,请你判断[l₁, r₁]和 [l₂, r₂]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

// h[i]前i个字符的hash值,从1开始计数
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
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;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P;            
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}

C++

一些常用的stl数据结构

queue/priority_queue

#include<queue>
//一般队列queue
queue<int> q;    
q.push(b);
int a = q.top();
q.pop();

//优先队列，默认是一个最大堆，也可以改为最小堆
priority_queue<int> q;
// 最小堆： priority_queue<int,greater<int>> heap;
q.push(b);  //注意vector是push_back()
int a = q.top();
q.pop();

//引入pii,会按照pii第一个元素进行排序
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> heap;
// 分别代表，元素类型，存储使用的底层容器，排序规则是小在上
C++

map/unordered_map

map和umap都是建立由键到值的映射，不过 - map原理是红黑树，会按照键进行升序排序，查找、插入和删除操作的时间复杂度是O(log n)。 - 而umap基于哈希，是无序的，查找、插入和删除操作的平均时间复杂度是O(1)。

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> wordCount;

    // 插入键值对
    wordCount["banana"] = 1;
    wordCount["apple"] = 2;
    wordCount["cherry"] = 1;

    // 遍历并输出键值对
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找元素
    auto it = wordCount.find("banana");
    if (it != wordCount.end()) {
        std::cout << "Found banana with count: " << it->second << std::endl;
    }

    return 0;
}
C++

运行结果为
apple: 2
banana: 1
cherry: 1
Found banana with count: 1

但是unordered结果完全无序：
apple: 2
cherry: 1
banana: 1
Found banana with count: 1