單連結清單
題目描述
實作一個單連結清單，連結清單初始為空，支援三種操作：
(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
所有操作保證合法。
輸入樣例：
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 = 1e5 + 6 ;
int head,e[N],ne[N],idx;
void start(){
head = - 1 , idx = 0 ;
}
//在表頭插入一個元素x
void insert_head(int x){
e[idx] = x , ne[idx] = head , head = idx ++ ;
}
//将X插到下标是K的後面
void insert(int k,int x){
e[idx] = x ,ne[idx] = ne[k] ,ne[k] = idx ++ ;
}
//删除第k個輸入的數後面的數
void remove(int x){
ne[x] = ne[ne[x]];
}
int main(){
start();
int m;
scanf("%d",&m);
while(m--){
char op;
int x,k;
cin>>op;
if(op == 'H') cin>>x,insert_head(x);
else if(op == 'D'){
cin>>k;
if(!k) head = ne[head];
else remove(k-1);
}
else cin>>k>>x,insert(k-1,x);
}
for(int i = head; i != - 1; i = ne[i]) cout<<e[i]<<" ";
cout<<endl;
return 0;
} 雙連結清單
實作一個雙連結清單，雙連結清單初始為空，支援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
所有操作保證合法。
輸入樣例：
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 = 1e5 + 6 ;
int head,l[N],r[N],e[N],idx;
void start(){
//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] ;
}
int main(){
start();
int m;
scanf("%d",&m);
while(m--){
int k,x;
string oper;
cin>>oper;
if(oper == "L") cin>>x,insert(0,x);
else if(oper == "R") cin>>x,insert(l[1],x);
else if(oper == "D") cin>>k,remove(k+1);
else if(oper == "IL") cin>>k>>x,insert(l[k+1],x);
else if(oper == "IR") cin>>k>>x,insert(k+1,x);
}
for(int i = r[0] ; i != 1; i = r[i]) cout<<e[i]<<" ";
cout<<endl;
return 0;
} 模拟棧
實作一個棧，棧初始為空，支援四種操作：
(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≤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;
const int N=1e5+6;
int m,st[N],tt;
int main(){
cin>>m;
while(m--){
string op;
int x;
cin>>op;
if(op=="push"){
cin>>x;
st[++tt]=x;
}
else if(op=="pop") tt--;
else if(op=="empty"){
if(tt) puts("NO");
else puts("YES");
}
else cout<<st[tt]<<endl;
}
return 0;
}
模拟隊列
實作一個隊列，隊列初始為空，支援四種操作：
(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≤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;
const int N=1e5+10;
int m,q[N],hh,tt=-1;
int main(){
cin>>m;
while(m--){
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;
} 單調棧
給定一個長度為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;
const int N=1e5+100;
int st[N],tt;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
while(tt&&st[tt]>=x) tt--;
if(!tt) cout<<"-1 ";
else printf("%d ",st[tt]);
st[++tt]=x;
}
return 0;
} 滑動視窗
給定一個大小為n≤106的數組。
有一個大小為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個整數，代表數組的具體數值。
同行資料之間用空格隔開。
輸出格式
輸出包含兩個。
第一行輸出，從左至右，每個位置滑動視窗中的最小值。
第二行輸出，從左至右，每個位置滑動視窗中的最大值。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int a[N],q[N];
int main(){
int n,k;
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) printf("%d ",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) printf("%d ",a[q[hh]]);
}
cout<<endl;
return 0;
}
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)