第二讲 数据结构
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
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
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 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
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
所有操作保证合法。
输入样例：
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
输出样例：
5
5
YES
4
NO
#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)
输出样例：
8
#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,
所有操作保证合法。
输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例：
NO
6
YES
4
#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
输入样例：
5
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; }
