＜数据结构＞ - 数据结构在算法比赛中的应用（上）

目录

单链表

双链表

单调栈

单调队列&滑动窗口

KMP字符串

---

单链表
 

思路：

工程链表：

 
typedef struct SListNode
{
	int data; // val
	struct SListNode* next; // 存储下一个节点的地址
}SLN;

 算法表示法： 

head 表示头结点的下标，数组e[]表示链表 date值，ne[]表示存储下一个节点的地址的指针next，idx 存储当前已经用到了哪个点

#include 
 
using namespace std;
 
const int N = 100010;
 
 
// head 表示头结点的指针
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点,工程链表中的新地址
int head, e[N], ne[N], idx;
 
// 初始化
void init()
{
    head = -1;  //-1表示指向空
    idx = 0;    //下标索引从0开始
}
 
// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}
 
// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
 
// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];    //让结点直接指向下一个结点的next，不用管内存泄漏
}
 
int main()
{
    int m;
    cin >> m;
 
    init();
 
    while (m -- )
    {
        int k, x;
        char op;
 
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];    //如果k为0，删除头结点，ne[head]必指向空
            else remove(k - 1);    //k-1对应从0开始的idx
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
 
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
 
    return 0;
}

双链表

 思路：

与单链表类似，e[N]存值，l[N]、r[N]表示左右指针

双链表初始化：

0号店表示头结点，1号表示尾节点

    r[0] = 1, l[1] = 0;
    idx = 2;

删除节点a的remove（）函数

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

 在节点k的右边插入一个数x方法

第一步：开一个新节点，左右指针指向k，与k的下一个节点

第二步：先让k的下一个节点的左指针指向新点，再用k的右指针指向新点；顺序搞错会导致数据覆盖 

void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

#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);  //idx从2开始，插入节点夹在head与tail之间
        }
        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;
}
 

单调栈

cin，cout速度大幅提高方法： 

cin.tie(0);
ios::sync_with_stdio(false);

#include 
 
using namespace std;
 
const int N = 100010;
 
int stk[N], tt;
 
int main()
{
    //cin.tie(0);
   // ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin>>x;
        while (tt && stk[tt] >= x) tt -- ;  //不符合，出栈
        if (!tt) cout<<"-1"<<" ";
        else cout<" ";
        
        stk[ ++ tt] = x;    //当前值入栈，与下一个数比较
    }
 
    return 0;
}
 

单调队列&滑动窗口

思路：

• 利用双端队列思想
• 设 队列q[hh],q[tt]分别表示窗口左边界（队头）与右边界（队尾），存储下标
• 用 i 表示窗口进程，则窗口范围【i-k+1,i】

（先求最小值）根据滑动窗口性质，队头的数会先消失，如果队尾插入的值比前一个数小，则前数不是最小值，所以直到出窗口也不会被输出

核心操作：如果队尾插入的值比前一个数小，那么将前一个数移出队列，最终队列会形成单调递增，取最小值永远在q[hh]处取

#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 ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;  //队首出窗口，hh++
 
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;    //队列不满足单调，tt--将元素移出
        q[ ++ tt] = i;      //将新元素下标入队尾
 
        if (i >= k - 1) printf("%d ", a[q[hh]]);    //满足遍历个数大于窗口k值，输出队头
    }
 
    puts("");
 
    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]]);
    }
 
    puts("");
 
    return 0;
}
 

KMP字符串

一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。
                                                                                                                                      ------- KMP

#include
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++)   //构造next数组
    {
        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];  找到后直接跳过j段
        }
    }
    return 0;
}