AcWing数据结构 - 数据结构在算法比赛中的应用(上)

简介: AcWing数据结构 - 数据结构在算法比赛中的应用(上)

单链表

思路:

工程链表:

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

算法表示法:

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

#include <iostream>
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 <iostream>
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;
}

模拟栈

#include <iostream>
using namespace std;
const int N = 100010;
int st[N];
int top,n;
int main()
{
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        if(s=="push")
        {
            int a;
            cin>>a;
            st[++top]=a;
        }
        else if(s=="pop")
        {
            --top;
        }
        else if(s=="query")
        {
            cout<<st[top]<<endl;
        }
        else if(s=="empty")
        {
            cout<<(top==0?"YES":"NO")<<endl;
        }
    }
    return 0;
}

表达式求值模板

#include<iostream>
#include<stack>
#include<unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}};//数值表示优先级
void eval()
{
    int a=num.top();
    num.pop();
    int b=num.top();
    num.pop();
    char p=op.top();
    op.pop();
    int r=0;
    if(p=='+') r=b+a;
    if(p=='-') r=b-a;
    if(p=='*') r=b*a;
    if(p=='/') r=b/a;
    num.push(r);
}
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))//如果是数字则转化入栈
        {
            int x=0,j=i;
            while(j<s.size()&&isdigit(s[j]))
            {
                x=x*10+s[j]-'0';
                j++;
            }
            num.push(x);
            i=j-1;
        }
        else if(s[i]=='(')
        {
            op.push(s[i]); 
        }
        else if(s[i]==')')//遇到右括号直接操作括号里的
        {
            while(op.top()!='(') eval();
            op.pop();
        }
        else
        {
            //前一个符号优先级不小于当前符号,说明可以计算后再加入当前符号
            while(op.size()&&h[op.top()]>=h[s[i]]) eval();
            op.push(s[i]);
        }
    }
    while(op.size()) eval();
    cout<<num.top()<<endl;
    return 0;
}

模拟队列

#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N];
int main()
{
    int n;
    cin>>n;
    int hh=0,tt=0;
    while(n--)
    {
        string op;
        int x;
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            q[tt++]=x;
        }
        else if(op=="pop") hh++;
        else if(op=="empty")
        {
            if(hh<tt) puts("NO");
            else puts("YES");
        }
        else cout<<q[hh]<<endl;
    }
    return 0;
}

单调栈

cin,cout速度大幅提高方法:

cin.tie(0);
ios::sync_with_stdio(false);
#include <iostream>
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]<<" ";
        stk[ ++ tt] = x;    //当前值入栈,与下一个数比较
    }
    return 0;
}

单调队列&滑动窗口

思路:


利用双端队列思想

设 队列q[hh],q[tt]分别表示窗口左边界(队头)与右边界(队尾),存储下标

用 i 表示窗口进程,则窗口范围【i-k+1,i】

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


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

#include <iostream>
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-q[hh]+1>k) hh++;
        while(hh<=tt&& a[q[tt]]>=a[i]) tt--;//不符合单增
        q[++tt]=i;//先看前面元素与当前值是否构成单增再入队
        if(i>=k-1) cout<<a[q[hh]]<<" ";//始终确保q[hh]为最小值,即单调递增序列
    }
    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<iostream>
using namespace std;
const int N=100010,M=1000010;
char q[N],s[M];
int ne[N];//保存next数组
int main()
{
    int n,m;
    cin>>n>>q+1>>m>>s+1;//下标均从1开始
    for(int i=2,j=0;i<=n;i++)
    //j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
    {
        while(j&&q[i]!=q[j+1]) j=ne[j];
        //如果不行可以换到next数组
        if(q[i]==q[j+1]) j++;
        //成功了就加1
        ne[i]=j;
        //对应其下标
    }
    //j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=q[j+1]) j=ne[j];
        //如果匹配不成功,则换到j对应的next数组中的值
        if(s[i]==q[j+1]) j++;
        //匹配成功了,那么j就加1,继续后面的匹配
        if(j==n)//如果长度等于n了,说明已经完全匹配上去了
        {
            printf("%d ",i-j);
            //因为题目中的下标从0开始,所以i-j不用+1;
            j=ne[j];
            //为了观察其后续是否还能跟S数组后面的数配对成功
        }
    }
    return 0;
}
相关文章
|
1天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
16天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
2月前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
74 0
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1

热门文章

最新文章