【第二讲】数据结构（1）-阿里云开发者社区

2.1单链表

单链表 —— 模板题 AcWing 826. 单链表

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

2.1.1 826. 单链表

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；

删除第 k 个插入的数后面的数；

在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

H x，表示向链表头插入一个数 x。

D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。

I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000

所有操作保证合法。

输入样例：

H 9

I 1 1

D 1

D 0

H 6

I 3 6

I 4 5

I 3 4

D 6

输出样例：

6 4 6 5

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int m;
int head,e[N],ne[N],idx;
void init()
{
    head=-1;
    idx=1;
}
void add_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}
void add(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
void myremove(int k)
{
    if(k==0)
    {
        head=ne[head];
    }
    else
    {
        ne[k]=ne[ne[k]];
    }
}
int main()
{
    cin>>m;
    init();
    while(m--)
    {
        char ch;
        cin>>ch;
        if(ch=='H')
        {
            int x;
            cin>>x;
            add_head(x);
        }
        else if(ch=='D')
        {
            int k;
            cin>>k;
            myremove(k);
        }
        else
        {
            int k,x;
            cin>>k>>x;
            add(k,x);
        }
    }
    int p=head;
    while(p!=-1)
    {
        cout<<e[p]<<" ";
        p=ne[p];
    }
    return 0;
}

2.2双链表

双链表 —— 模板题 AcWing 827. 双链表

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

2.2.1 827. 双链表

实现一个双链表，双链表初始为空，支持 5 种操作：

在最左侧插入一个数；

在最右侧插入一个数；

将第 k 个插入的数删除；

在第 k 个插入的数左侧插入一个数；

在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。

R x，表示在链表的最右端插入数 x。

D k，表示将第 k 个插入的数删除。

IL k x，表示在第 k 个插入的数左侧插入一个数。

IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

1≤M≤100000

所有操作保证合法。

输入样例：

R 7

D 1

L 3

IL 2 10

D 3

IL 2 7

L 8

R 9

IL 4 7

IR 2 2

输出样例：

8 7 7 3 2 9

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int m;  
int e[N],l[N],r[N],idx;
void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}
void add(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}
void myremove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main()
{
    cin>>m;
    init();
    while(m--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op=="L")
        {
            k=0;
            cin>>x;
            add(k,x);
        }
        else if(op=="R")
        {
            k=l[1];
            cin>>x;
            add(k,x);
        }
        else if(op=="D")
        {
            cin>>k;
            myremove(k+1);
        }
        else if(op=="IL")
        {
            cin>>k>>x;
            k=l[k+1];
            add(k,x);
        }
        else
        {
            cin>>k>>x;
            add(k+1,x);
        }
    }
    int p=r[0];
    while(p!=1)
    {
        cout<<e[p]<<" ";
        p=r[p];
    }
    return 0;
}

2.3栈

栈 —— 模板题 AcWing 828. 模拟栈

// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}

2.3.1 828. 模拟栈

实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 x；

pop – 从栈顶弹出一个数；

empty – 判断栈是否为空；

query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤100000,

1≤x≤109

所有操作保证合法。

输入样例：

push 5

query

push 6

pop

query

pop

empty

push 4

query

empty

输出样例：

YES

#include<bits/stdc++.h>
using namespace std;
int m;
stack<int> sk;
int main()
{
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        int x;
        if(op=="push")
        {
            cin>>x;
            sk.push(x);
        }
        else if(op=="pop")
        {
            sk.pop();
        }
        else if(op=="empty")
        {
            if(sk.empty())
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<sk.top()<<endl;
        }
    }
    return 0;
}

2.3.2 3302. 表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加减乘整除），可能包含括号，请你求出表达式的最终值。

注意：

数据保证给定的表达式合法。

题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。

题目保证表达式中所有数字均为正整数。

题目保证表达式在中间计算过程以及结果中，均不超过 231−1。

题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。

C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105。

输入样例：

(2+2)*(1+1)

输出样例：

#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> op;
void eval()
{
    int b=num.top();num.pop();
    int a=num.top();num.pop();
    char c=op.top();op.pop();
    int x;
    if(c=='+')
    {
        x=a+b;
    }
    else if(c=='-')
    {
        x=a-b;
    }
    else if(c=='*')
    {
        x=a*b;
    }
    else
    {
        x=a/b;
    }
    num.push(x);
}
int main()
{
    map<char,int> mp;
    mp.insert(make_pair('+',1));
    mp.insert(make_pair('-',1));
    mp.insert(make_pair('*',2));
    mp.insert(make_pair('/',2));
    string str;
    cin>>str;
    for(int i=0;i<str.size();i++)
    {
        char c=str[i];
        if(isdigit(c))
        {
            int x=0,j=i;
            while(j<str.size()&&isdigit(str[j]))
            {
                x=x*10+str[j++]-'0';
            }
            i=j-1;
            num.push(x);
        }
        else if(c=='(') op.push(c);
        else if(c==')')
        {
            while(op.top()!='(') eval();
            op.pop();
        }
        else
        {
            while(op.size()&&op.top()!='('&&mp[op.top()]>=mp[c]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();
    cout<<num.top();
    return 0;
}

2.4队列

队列 —— 模板题 AcWing 829. 模拟队列

\1. 普通队列：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}

\2. 循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)
{
}

2.4.1 829. 模拟队列

实现一个队列，队列初始为空，支持四种操作：

push x – 向队尾插入一个数 x；

pop – 从队头弹出一个数；

empty – 判断队列是否为空；

query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

1≤M≤100000,

1≤x≤109,

所有操作保证合法。

输入样例：

push 6

empty

query

pop

empty

push 3

push 4

pop

query

push 6

输出样例：

YES

#include<bits/stdc++.h>
using namespace std;
int m;  
queue<int> q;
int main()
{
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        int x;
        if(op=="push")
        {
            cin>>x;
            q.push(x);
        }
        else if(op=="pop")
        {
            q.pop();
        }
        else if(op=="empty")
        {
            if(q.empty()) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else cout<<q.front()<<endl;
    }
    return 0;
}

2.5单调栈

单调栈 —— 模板题 AcWing 830. 单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

2.5.1 830. 单调栈

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

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1≤N≤105

1≤数列中元素≤109

输入样例：

3 4 2 7 5

输出样例：

-1 3 -1 2 2

#include<bits/stdc++.h>
using namespace std;
stack<int> sk;
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(!sk.empty()&&sk.top()>=x) sk.pop();
        if(sk.empty()) cout<<-1<<" ";
        else cout<<sk.top()<<" ";
        sk.push(x);
    }
    return 0;
}

2.6单调队列

调队列 —— 模板题 AcWing 154. 滑动窗口

常见模型：找出滑动窗口中的最大值/最小值

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

2.6.1 154. 滑动窗口

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

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

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3

1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3

3 3 5 5 6 7

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,k;
int a[N],q[N];
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int 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)
        {
            cout<<a[q[hh]]<<" ";
        }
    }
    cout<<endl;
    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)
        {
            cout<<a[q[hh]]<<" ";
        }
    }
    cout<<endl;
    return 0;
}

2.7KMP

KMP —— 模板题 AcWing 831. 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];
        // 匹配成功后的逻辑
    }
}

2.7.1 831. KMP字符串

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤N≤105

1≤M≤106

输入样例：

aba

ababa

输出样例：

0 2

#include<bits/stdc++.h>
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;
    cin>>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)
        {
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}

【第二讲】数据结构（1）

2.1单链表

2.1.1 826. 单链表

2.2双链表

2.2.1 827. 双链表

2.3栈

2.3.1 828. 模拟栈

2.3.2 3302. 表达式求值

2.4队列

2.4.1 829. 模拟队列

2.5单调栈

2.5.1 830. 单调栈

2.6单调队列

2.6.1 154. 滑动窗口

2.7KMP

2.7.1 831. KMP字符串

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【第二讲】数据结构（1）

2.1单链表

2.1.1 826. 单链表

2.2双链表

2.2.1 827. 双链表

2.3栈

2.3.1 828. 模拟栈

2.3.2 3302. 表达式求值

2.4队列

2.4.1 829. 模拟队列

2.5单调栈

2.5.1 830. 单调栈

2.6单调队列

2.6.1 154. 滑动窗口

2.7KMP

2.7.1 831. KMP字符串

热门文章

最新文章

相关课程

相关电子书