单链表
数组模拟链表可以加快速度,更利于优化算法
#include<iostream> using namespace std; const int N = 100010; int e[N], ne[N], head, idx; void init() { head = -1; idx = 0; } void add_head(int x) { e[idx] = x; ne[idx] = head; head = idx++; } void insert(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } void delete_link(int k) { ne[k] = ne[ne[k]]; } int main() { int n; cin >> n; init(); while (n--) { char c;int k,x; cin>>c; if (c == 'H') { scanf("%d",&x); add_head(x); } else if (c == 'I') { scanf("%d%d",&k,&x); insert(k-1, x); } else { scanf("%d",&k); if(k==0) head=ne[head];//注意这个特殊情况 else{ delete_link(k-1);} } } for (int i = head; i != -1; i = ne[i]) printf("%d ",e[i]); return 0; }
双链表
//注意事项:::切记不要把下一位看成k+1,因为这是不对的空间是不连续的 #include<iostream> using namespace std; const int N = 100010; int e[N], l[N], r[N], idx; void insert(int k,int x) { e[idx] = x; l[idx] = l[r[k]], r[idx] = r[k]; l[r[k]] = idx; r[k] = idx++; } void del(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } int main() { r[0] = 1; l[1] = 0; idx = 2;//用0表示开头,1表示结尾,不存实际值 int n; cin >> n; while (n--) { int k, x; string c; cin >> c; if (c == "R") { cin >> x; insert(l[1], x);//结尾往左边插 } else if (c == "L") { cin >> x; insert(0, x);//从0开始查 } else if (c == "D") { cin >> k; del(k + 1);//查的是下标 } else if (c == "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] << " "; } return 0; }
模拟栈
#include <iostream> using namespace std; const int N = 100010; int m; int stk[N], tt; int main() { cin >> m; while (m -- ) { string op; int x; cin >> op; if (op == "push") { cin >> x; stk[ ++ tt] = x; } else if (op == "pop") tt -- ; else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;//简化代码 else cout << stk[tt] << endl; } return 0; }
模拟队列
#include <iostream> using namespace std; const int N = 100010; int m; int 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") cout << (hh <= tt ? "NO" : "YES") << endl; else cout << q[hh] << endl; } return 0; }
单调栈
#include <iostream> using namespace std; const int N = 100010; int stk[N], tt; int main() { int n; cin >> n; while (n -- ) { int x; scanf("%d", &x); while (tt && stk[tt] >= x) tt -- ;//判断栈顶元素如果大于等于x,就弹出 if (!tt) printf("-1 ");//如果空就输出-1 else printf("%d ", stk[tt]);//没有就输出元素 stk[ ++ tt] = x;//把新的加入 } return 0; }
//自写代码较为复杂,但精细
#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int hh = -1;
int n; cin >> n;
while (n--)
{
int x; scanf("%d", &x);
if (hh == -1)
{
printf("-1 ");
a[++hh] = x;
}
else {
if (a[hh] < x) {
printf("%d ", a[hh]);
a[++hh] = x;
}
else {
while (a[hh] >= x && hh > -1) hh--;
if (a[hh] < x&&hh!=-1)cout << a[hh] << " ";//一定加上hh!=-1的条件
if(hh==-1)printf("-1 ");
a[++hh] = x;
}
}
}
return 0;
}
单调队列
#include<iostream> using namespace std; const int N = 1000010; int a[N],q[N]; int hh=0, tt=-1; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { if (hh <= tt && i - k + 1 > q[hh])hh++;//可以等于,相当于1个元素 while (a[i] < a[q[tt]] && hh <= tt)tt--; q[++tt] = i; if (i-k+1>=0)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 (a[i] >= a[q[tt]] && hh <= tt)tt--; q[++tt] = i; if (i-k+1>=0)cout << a[q[hh]] << " "; } return 0; }
标签:idx,队列,tt,cin,else,链表,int,hh,模拟 From: https://www.cnblogs.com/daimazhishen/p/17688559.html