算法基础课-数据结构

单链表

题目链接：826. 单链表 - AcWing题库
思路：AcWing 826. 单链表---图解 - AcWing

需要注意的点在于理解ne[idx] = head，idx表示当前的点，意思是将当前的点链到头结点的后面，再将头结点链在当前idx的前面。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;

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

// 在链表头插入一个数a
void insert_to_head(int a)
{
    e[idx] = a;
    ne[idx] = head;
    head = idx ++ ;
}

void insert(int k,int a)
{
    e[idx] = a;
    ne[idx] = ne[k];
    ne[k] = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

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

双链表

题目链接：827. 双链表 - AcWing题库

思路：这个博客写的可好AcWing 827. 双链表 - AcWing。

需要注意的地方在于r数组和l数组的含义。r[idx]表示的是idx的右边，l[idx]表示idx的左边，开始时初始化0的左边是1，1的右边是左，所以r[0] = 1,l[1] = 0。

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

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

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点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(){
    int m;
    cin>>m;
    init();
    while(m--){
        string op;
        cin>>op;
        int k,x;
        if(op[0] == 'L'){
            cin>>x;
            insert(0,x);
        }else if(op[0] == 'R'){
            cin>>x;
            insert(l[1],x);
        }else if(op[0] == 'D'){
            cin>>k;
            remove(k+1);
        }else if(op[1] == 'L'){
            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]<<" ";
    }
    return 0;
}

栈的应用

题目链接：3302. 表达式求值 - AcWing题库
思路：这个题解写的很好AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 - AcWing。

主要的思路在符号栈上，符号栈内存储的符号优先级一定递增，即将进来的符号若小于当前栈顶优先级，则先对栈内高优先级符号进行运算，直到栈顶优先级低于待入栈符号优先级。

还需要注意的是，对于相同运算符来说，栈内的优先级大于栈外优先级，即遇到栈顶是一个加号，待入栈也是一个加号，先运算栈内加号，当栈为空或遇到更低优先级的符号时再将栈外加号入栈。

#include<bits/stdc++.h>

using namespace std;
stack<int> num;
stack<int> op;

unordered_map<char,int> h{
  {'+',1},{'-',1},{'*',2},{'/',2}};
void calc(){
    char ops = op.top();
    op.pop();
    int b = num.top();
    num.pop();
    int a = num.top();
    num.pop();
    
    if(ops == '+') num.push(a+b);
    if(ops == '-') num.push(a-b);
    if(ops == '*') num.push(a*b);
    if(ops == '/') num.push(a/b);
    
    return;
}

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(isdigit(s[i])){  //遇到数字的情况
            int j = i;
            int val = 0;
            while(j<s.size()&&isdigit(s[j])){
                val = val*10 + s[j] - '0';
                j++;
            }
            i=j-1;
            num.push(val);
        }else{  //遇到字符的情况
            if(s[i] == '(') op.push('(');
            else if(s[i] == ')'){
                while(op.top()!='('){
                    calc();
                }
                op.pop();
            }else{
                while(op.size() && h[op.top()] >= h[s[i]]){
                    calc();
                }
                op.push(s[i]);
            }
        }
    }
    while(op.size())
        calc();
    cout<<num.top()<<endl;
    return 0;
}

单调栈

题目链接：830. 单调栈 - AcWing题库

思路：维护一个数字单调递增的栈，若下一个待入栈数字小于栈顶时，持续出栈。感觉跟表达式求值中栈内优先级高于栈外优先级有点像，hh。

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];
int main(){
    int n;
    cin>>n;
    
    stack<int> stk;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        while(stk.size()&&stk.top() >= a[i]) stk.pop();
        if(stk.size()) cout<<stk.top()<<" ";
        else cout<<-1<<" ";
        stk.push(a[i]);
    }
    
    return 0;
}

单调队列

题目链接：154. 滑动窗口 - AcWing题库
思路：排在后面的数字越小/大，越优秀，当这样的元素出现时，将右侧队列中的元素出队。由于要求队列能右侧出队，所以需要自己模拟队列（感觉可以使用双端队列实现）。

需要注意的点是队列中存储的是下标，是为了方便队头出队。

#include<bits/stdc++.h>

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

int a[N];
int q[N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int h=1,t=0;
    for(int i=0;i<n;i++){
        while(h<=t&&a[q[t]] >= a[i]) t--;
        q[++t] = i;
        if(q[h]<i-k+1) h++;
        if(i>=k-1) cout<<a[q[h]]<<" ";
    }
    h=1;t=0;
    cout<<endl;
    for(int i=0;i<n;i++){
        while(h<=t&&a[q[t]] <= a[i]) t--;
        q[++t] = i;
        if(q[h]<i-k+1) h++;
        if(i>=k-1) cout<<a[q[h]]<<" ";
    }
    return 0;
}

KMP

题目链接：831. KMP字符串 - AcWing题库

思路：对于模板串（短串）进行初始化ne数组，ne数组表示当前位置不匹配时，可以从哪个位置开始匹配。具体思路太复杂，放弃，可以考虑直接背过。时间复杂度为O(m+n)。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;
char p[N],s[M];
int ne[M];
void init(char p[],int n,int m){
    // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
    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;
    }
}

int main(){
    int n,m;
    cin>>n;
    cin>>p+1;
    cin>>m;
    cin>>s+1;
    init(p,n,m);
    // 匹配
    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<<' ';
            j = ne[j];
            // 匹配成功后的逻辑
        }
    }
    return 0;
}

Trie（字典树）

题目链接：835. Trie字符串统计 - AcWing题库
思路：ch[0][2]=1表示从0号结点开始往2('c')走能走到1号节点。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx = 1;



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

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

int main(){
    int n;
    cin>>n;
    while(n--){
        char op;
        string s;
        cin>>op>>s;
        if(op == 'I'){
            insert(s);
        }else cout<<query(s)<<endl;
    }
    return 0;
}

并查集

题目链接：836. 合并集合 - AcWing题库

思路：fa[i]表示i节点的父亲节点。开始时每个节点的父亲节点都是自己。

#include<bits/stdc++.h>

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

int fa[N];  //下标表示当前点，数组值表示其父亲节点的下标

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

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

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i] = i;
    
    while(m--){
        char op;
        cin>>op;
        int x,y;
        cin>>x>>y;
        if(op == 'M'){
            unionset(x,y);
        }else{
            if(find(x) == find(y)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

堆

题目链接：838. 堆排序 - AcWing题库

思路：主要的操作包括up和down，up表示将节点上移，一般在新节点进入时使用，down表示将节点下移，一般在删除元素时使用。

需要注意的点在于一些小细节，例如递归边界，up和down都使用递归的形式，需要注意什么时候递归停止或是什么时候采用递归。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];
int cnt;
void up(int x){
    if(x/2&&a[x]<a[x/2]){
        swap(a[x],a[x/2]);
        up(x/2);
    }
}

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

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[++cnt];
        up(cnt);

    }
    // for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
    // cout<<endl;
    while(m--){
        cout<<a[1]<<" ";
        swap(a[1],a[cnt]);
        cnt--;
        down(1);
        // for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
        // cout<<endl;
    }
    return 0;
}

哈希表

题目链接：841. 字符串哈希 - AcWing题库

思路：

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
typedef unsigned long long ULL;
ULL h[N],p[N];
int P = 131;
ULL getSeg(int l,int r){
    return h[r] - h[l-1] * p[r-l+1];
}
int main(){
    int n,m;
    cin>>n>>m;
    char s[N];
    cin>>s+1;
    p[0] = 1;
    for(int i=1;i<=n;i++){
        h[i] = h[i-1]*P + s[i];
        p[i] = p[i-1]*P;
    }
    while(m--){
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(getSeg(l1,r1) == getSeg(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}