[数据结构与算法]Acwing-2-数据结构(1)

数组模拟单链表

模板

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

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

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

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

例题Acwing826

#include<iostream>
using namespace std;
const int N=100010;
int idx,head,e[N],ne[N];
int a;
void add_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void add(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
void remove(int k){
    ne[k]=ne[ne[k]];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    head=-1;idx=0;
    cin>>a;
    while(a--){
        string op;
        int k,x;
        cin>>op;
        if(op=="D")
        {
            cin>>k;
            //注意删除结点的时候要单独考虑头结点
            if(!k)head=ne[head];
            remove(k-1);
        }
        else if(op=="H")
        {
            cin>>x;
            add_head(x);
        }
        else if(op=="I"){
            int k,x;
            cin>>k>>x;
            add(k-1,x);
        }
    }
    //注意链表的遍历是从head开始，i=-1时结束
    for(int i=head;i!=-1;i=ne[i])
      cout<<e[i]<<" ";
    return 0;

}

数组模拟单链表注意点：

忘记单独考虑删除头结点是经常犯的错误！！！

1.超时多半是没有调用init()函数进行初始化
2.因为前后两个节点没有练习，所以不能调用
ne[k+1]，应该用ne[ne[k]]
3.注意删除结点的时候要单独考虑头结点！！！

数组模拟双链表

模板

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
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];
}

例题Acwing827

#include<iostream>
using namespace std;
const int N = 1e5+10;
int m, k, x;
int e[N], l[N], r[N], idx;

void init(){
    r[0] = 1, l[1] = 0;
    idx = 2;
}
//在第k个结点右侧插入一个数
void insert(int k, int x){
    e[idx] = x;
    //插入的点分别指向两个相邻节点
    l[idx] = k, r[idx] = r[k];
    //两个相邻节点均指向要插入的节点
    l[r[k]] = idx, r[k] = idx++;
}
void remove(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}
int main(){
    init();
    cin >> m;
    string op;
    while(m--){
        cin >> op;
        if(op == "L"){//最左端插入一个数
            cin >> x;
            insert(0, x);
        }
        else if(op == "R"){//最右端插入一个数
            cin >> x;
            insert(l[1], x);
        }
        else if(op == "IL"){//在第k个结点左边加入一个数
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else if(op == "IR"){
            cin >> k >> x;
            insert(k + 1, x);
        }
        else if(op == "D"){
            cin >> k;
            remove(k + 1);
        }
    }

    for(int i = r[0]; i != 1; i = r[i] )
        cout << e[i] << " ";
    
    return 0;
}

模板

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

例题Acwing828

#include<iostream>
using namespace std;

const int N = 1e5+10;
int stk[N], top;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m, x;
    string op;
    cin >> m;
    while(m--){
        cin >> op;
        if(op == "push"){
            cin >> x;
            stk[top++] = x;
        }
        else if(op == "pop"){
            --top;
        }
        else if(op == "empty"){
            if(top) printf("NO\n");
            else printf("YES\n");
        }
        else 
            printf("%d\n", stk[top-1]);
    }
    
    
    return 0;
}

模拟队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

例题

#include<iostream>
using namespace std;
const int N = 1e5+10;
int q[N], hh, tt;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, x;
    string op;
    cin >> m;
    while(m--){
        cin >> op;
        if(op == "push"){
            cin >> x;
            q[tt++] = x;
        }
        else if(op == "pop"){
            hh++;
        }
        else if(op == "empty"){
            if(hh < tt) printf("NO\n");
            else printf("YES\n");
        }
        else printf("%d\n", q[hh]);
    }
    
    return 0;
}

单调栈

找出每个数左边离它最近的比它大/小的数

模板

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

例题Acwing830

#include<iostream>
using namespace std;
const int N = 1e5+10;
int stk[N], tt;

int main(){
    int m;
    scanf("%d", &m);
    while(m--){
        int x;
        scanf("%d", &x);
        //删除栈中比它大的数
        while(tt && stk[tt] >= x) tt--;
        if(!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[++tt] = x;
    }
    
    return 0;
}

单调队列

单调队列应用->滑动窗口问题

模板

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

例题Acwing154

因为本题涉及的窗口每次只滑动一个位置，所以只需要用一个if来判断就可以了，但是如果是一次移动两个以上的位置，就需要用while循环来判断是否将队头元素滑出队列q
关于判断是否滑出：i - k + 1是当前元素结尾时候窗口的最左侧窗口元素的下标，和q[hh] (前一步的窗口最左侧元素下标)
每次输出q[hh]有递归的感觉
注意每次往q中入队的都是i，即下标，不是元素

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N], q[N], hh, tt;

int main(){
    int m, k;
    scanf("%d%d", &m, &k);
    for(int i = 0; i < m; i++){
        scanf("%d", &a[i]);
        //判断是否需要将队头元素滑出队列q
        if(i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[i] <= a[q[tt]]) tt--;
        q[++tt] = i;
        
        //注意要先将i加入队列再输出，因为可能输出的就是这个元素
        if(i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    printf("\n");
    hh = 0, tt = 0;
    for(int i = 0; i < m; i++){
        //判断是否需要将队头元素滑出队列q
        if(i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[i] >= a[q[tt]]) tt--;
        q[++tt] = i;
        
        if(i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    
    return 0;
}

KMP字符串

模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; 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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

注意while循环是找到p[i] != p[j+1]过后就停止了，不会再进行一步j = ne[j]。关键理解找不相等字符对应的j位置，再更新ne[i]

例题Acwing831

因为下标要从1开始，所以读入的时候要进行加1操作

#include<iostream>
using namespace std;
const int M = 1e5+10, N = 1e6+10;
char p[M], s[N];
int ne[M];

int main(){
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1; 
    
    for(int i = 2, j = 0; i <= n; i++){
    	//给当前状态下的i一直寻找p[i]和p[j+1]相等的j，
    	//找到这个j就停止了，不会再更新j = ne[j]
        while(j && p[i] != p[j+1]) j = ne[j];
        //j替换到下一个位置
        if(p[i] == p[j + 1]) j++;
        //更新ne[i]
        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;
}