链表、栈、队列
链表、栈、队列
链表
单链表
一、原理
详见 知乎上一篇写的很好的回答
二、代码实现
数组模拟链表(十分关键,涉及到后续存图所用的链式前向星)
题目:acwing826 单链表
实现一个单链表,链表初始为空,支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “H x”,表示向链表头插入一个数x。
(2) “D k”,表示删除第k个插入的数后面的数(当k为0时,表示删除头结点)。
(3) “I k x”,表示在第k个插入的数后面插入一个数x(此操作中k均大于0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
1 | 10 |
输出样例:
1 | 6 4 6 5 |
代码:
1 |
|
这题的指针写法笔者还没有调出来…感觉相当麻烦…同时指针写法中分配空间耗时较长,会TLE…
三、模板
指针写法链表:
1 |
|
四、例题和应用
- 约瑟夫问题
- 插入排序
双向链表
一、和单向链表的区别
顾名思义,双向链表中,每个结点既能指向它后面的一个结点,也能指向它前面的一个结点。
二、代码实现
实现一个双链表,双链表初始为空,支持5种操作:
(1) 在最左侧插入一个数;
(2) 在最右侧插入一个数;
(3) 将第k个插入的数删除;
(4) 在第k个插入的数左侧插入一个数;
(5) 在第k个插入的数右侧插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “L x”,表示在链表的最左端插入数x。
(2) “R x”,表示在链表的最右端插入数x。
(3) “D k”,表示将第k个插入的数删除。
(4) “IL k x”,表示在第k个插入的数左侧插入一个数。
(5) “IR k x”,表示在第k个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
1 | 10 |
输出样例:
1 | 8 7 7 3 2 9 |
数组模拟
1 |
|
栈
一、原理
先进后出
二、代码实现
实现一个栈,栈初始为空,支持四种操作:
(1) “push x” – 向栈顶插入一个数x;
(2) “pop” – 从栈顶弹出一个数;
(3) “empty” – 判断栈是否为空;
(4) “query” – 查询栈顶元素。
现在要对栈进行M个操作,其中的每个操作3和操作4都要输出相应的结果。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。
输出格式
对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。
其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示栈顶元素的值。
数据范围
1≤M≤100000
1≤x≤$$10^9$$
所有操作保证合法。
输入样例:
1 | 10 |
输出样例:
1 | 5 |
栈 模板
1 |
|
队列
一、原理
先进先出
二、代码实现
实现一个队列,队列初始为空,支持四种操作:
(1) “push x” – 向队尾插入一个数x;
(2) “pop” – 从队头弹出一个数;
(3) “empty” – 判断队列是否为空;
(4) “query” – 查询队头元素。
现在要对队列进行M个操作,其中的每个操作3和操作4都要输出相应的结果。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。
输出格式
对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。
其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示队头元素的值。
数据范围
1≤M≤100000
1≤x≤$$10^9$$
所有操作保证合法。
输入样例:
1 | 10 |
输出样例:
1 | NO |
队列模板
1 |
|
单调栈
一、使用背景
给定一个序列,求这个序列中每一个数的某一侧(左、右)离它最近的且满足某种性质的数在哪。
二、例题
acwing 830 单调栈
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤$$10^5$$
1≤数列中元素≤$$10^9$$
输入样例:
1 | 5 |
输出样例:
1 | -1 3 -1 2 2 |
解析:
考虑最最暴力的做法,对每一个数都枚举它左边的所有数,直到找到符合条件的为止,复杂度O($$n^2$$)
简单优化:从它的上一个数开始找,找到符合条件的就停,还是O($$n^2$$)
基于方法2的想法:对于当前的数,与之前的数比较,如果它比之前的数都要小(并且已经在之前的数后面出现),说明它更有潜力成为“第一个”符合条件(比当前数小)的数,那么就可以淘汰掉前面那些数了(因为他们永远不可能成为后面的数的答案),此时与栈这种数据结构结合就可以维护一个单调的序列。
举例说明:设存在a[i](i>5>3), a[3]>a[5] 且3<5,那么a[3]一定不会成为a[i]的答案,因为a[5]一定更优
代码:
1 |
|
单调队列
一、使用背景
滑动窗口中的最值
**“如果一个选手比你小还比你强,你就可以退役了。” ** ——单调队列的原理
二、例题
luogu P1886 滑动窗口
给定一个大小为n≤$$10^6$$的数组。
有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。
您只能在窗口中看到k个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子:
该数组为[1 3 -1 -3 5 3 6 7],k为3。
窗口位置 | 最小值 | 最大值 |
---|---|---|
[1 3 -1] -3 5 3 6 7 | -1 | 3 |
1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
1 3 -1 -3 5 [3 6 7] | 3 | 7 |
您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。
第二行有n个整数,代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
1 | 8 3 |
输出样例:
1 | -1 -3 -3 -3 3 3 |
解析
先考虑暴力做法,对每个窗口都枚举,时间复杂度O(nk)
与单调栈例题类似的想法,如果后面出现的数比前面出现的更优,那么前面的数就可以直接踢出去了。那么我们每次加入队列后面的一定是次优值,在队头的最优值被踢掉之后有潜力成为新的最优值,即整个队列一定是单调的,并且对于每一个窗口,队头元素都是我们要找的最优值!
我们把每一次求极值都变成直接访问队头,O(k)的操作就变成O(1),时间复杂度就降低了。
举例说明:我们现在要找最小值,在 3 -1 -3 这个k=3的窗口中,只要 -3 存在,那么3和-1一定是没有用且永无出头之日(因为-3在他们的后面,会在更晚的时间被弹出窗口),他们失去了成为最小值的潜力,直接踢出去即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
const int N=2000050;
int n,k;
int a[N];
deque<int> maxq,minq,q;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
while(minq.front()<=i-k and !minq.empty())
{
minq.pop_front();//从队头弹出,丢掉所有下标不符合条件的数
}//看看下标在不在这个窗口的范围内
while(!minq.empty() and a[minq.back()]>a[i])
{
minq.pop_back();//从队尾弹出维护次优值
}//维护一个单调增的最小值队列
minq.push_back(i);
if(i>=k)
{
cout<<a[minq.front()]<<" ";
}
}
cout<<endl;
//做题时遇到的问题:如何在窗口移动后把早出现的值踢出去?
//法1.将下标加入队列而不是将值加入队列!
//法2.用结构体两个一起维护
for(int i=1;i<=n;i++)
{
while(maxq.front()<=i-k and !maxq.empty())
{
maxq.pop_front();
}
while(!maxq.empty() and a[maxq.back()]<a[i])
{
maxq.pop_back();
}//维护一个单调减的最大值队列
maxq.push_back(i);
if(i>=k)
{
cout<<a[maxq.front()]<<" ";
}
}
return 0;
}