做百度联盟怎么才能创建多个网站,公司网站开源源码,wordpress 主题预览插件,大型网站响应式算法学习06#xff1a;数组模拟#xff1a;单/双链表#xff0c;栈和队列#xff0c;单调栈/队列 文章目录 算法学习06#xff1a;数组模拟#xff1a;单/双链表#xff0c;栈和队列#xff0c;单调栈/队列前言一、链表1.单链表2.双链表 二、栈和队列1.普通栈、队列2.单…算法学习06数组模拟单/双链表栈和队列单调栈/队列 文章目录 算法学习06数组模拟单/双链表栈和队列单调栈/队列前言一、链表1.单链表2.双链表 二、栈和队列1.普通栈、队列2.单调栈3.单调队列 三、 拓展ios::sync_with_stdio(false) 和 cin.tie(0) 对cincout速率的影响总结 前言 提示以下是本篇文章正文内容
一、链表 1.单链表 #include iostreamusing namespace std;const int N 100000 10;//head表示头结点的下标
//e[i]表示结点i的值
//ne[i]表示结点i的next指针是多少
//idx存储当前已经用到了那个点从0开始
int head, e[N], ne[N], idx;//初始化
void init()
{head -1;idx 0;} //将x插入到头结点
void add_to_head(int x)
{e[idx] x;ne[idx] head;head idx;idx ;} // 将x插入到下标是k的点后面void add(int k, int x){e[idx] x;ne[idx] ne[k];ne[k] idx;idx ;} // 将下标是k的点后面的点删除
void remove(int k)
{ne[k] ne[ne[k]];} int main()
{int m;cin m;init();while(m --){char op;int x, k;cin op;if(ip H){cin x;add_to_head(x);}else if(ip D){cin k;if(!k) head ne[head];//注意1删除头结点 remove(k - 1);}else{cin k x;add(k - 1, x);}}for(int i - head; i ! -1; i ne[i]) cout e[i] ;cout endl;return 0;
}2.双链表 #include iostreamusing namespace std;const int N 100000 10;int m;
int e[N], l[N], r[N], idx;//初始化
void init()
{//0表示左端点1表示右端点r[0] 1, l[1] 0;idx 2; } //在下标是k的结点后插入x
void add(int k, int x)
{e[idx] x;r[idx] r[k];//idx的右边 l[idx] k;//idx的左边 l[r[k]] idx;//k右边结点的左边 r[k] idx;//k的右边
}//删除第k个点
void remove(int k)
{r[l[k]] r[k];//k左边节点的右边连接k的右边的结点 l[r[k]] l[k];//k右边结点的左边连接k的左边的结点 } 二、栈和队列
1.普通栈、队列 #include iostreamusing namespace std;const int N 100000 10;// ***************************栈int stk[N], tt;//stk栈 tt栈顶//插入
stk[ tt] x;//从 1 开始//弹出
tt --;// 判断栈是否为空(伪代码)
if(tt 0) not empty;
else empty;// 栈顶
stk[tt];// ***************************队列
int q[N], hh, tt -1;//hh对头 tt对尾// 插入
q[ tt] x; // 弹出
hh ;// 判断队列是否为空
if(hh tt) not empty;
else empty;// 取出对头元素
q[hh]; 2.单调栈 例题给一个长度为N的整数序列输出每个数昨天第一个比他小的数如果不存在就输出-1。 //例题给一个长度为N的整数序列输出每个数昨天第一个比他小的数
//如果不存在就输出-1。
#include iostreamusing namespace std;const int N 100000 10;int n;
int stk[N], tt;int main()
{cin n;for(int i 0; i n; i ){int x;cin x;//单调栈 //在我们维护的栈中移去比当前数“x”大的数 while(tt stk[tt] x) tt--;//此时栈顶元素就是 最近的 小于x的数if(tt) cout stk[tt] endl;else cout -1 end;stk[ tt] x;//将x进栈仍然可以维护 单调栈。 }return 0;
}3.单调队列 题目给定一个大小为n10^6的数组有一个大小为k的滑动窗口它从数组的最左边移动感到最右边你只能找窗口中看到k个数字。 你的任务是确定滑动窗口位于每个位置是窗口中的最小值和最大值。 //题目给定一个大小为n10^6的数组有一个大小为k的滑动窗口
//它从数组的最左边移动感到最右边你只能找窗口中看到k个数字。
//你的任务是确定滑动窗口位于每个位置是窗口中的最大值和最小值。#include iostreamusing namespace std;const int N 100000 10;int n, k;
int a[N], q[N];//q队列队列存储的是 下标 int main()
{scanf(%d%d, n, k);for(int i 0; i n; i ) scnaf(%d, %a[i]);//窗口中的最小值int hh 0, tt -1;for(int i 0; i n; i ) {//判断对头是否已经 划出窗口//使用if每次移动一格。 if(hh tt i - k 1 q[hh]) hh ; //将窗口内大于的元素 出队列为什么从后面出队列分析题目所得。while(hh tt a[q[tt] a[i]]) tt --;q[ tt] i;//要先加入i对应的值可能是最小的 if(i k - 1) printf(%d, a[q[hh]]); } put( ); //窗口中的最大值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;//i对应的值可能是最大的 if(i k - 1) printf(%d, a[q[hh]]); } put( ); return 0;} 三、 拓展ios::sync_with_stdio(false) 和 cin.tie(0) 对cincout速率的影响 拓展关于输入的速率问题 1cincout (1394ms) 2scanfprintf (133ms) 3ios::sync_with_stdio(false); cin (1182ms) 4cin.tie(0); (141ms) 应用别人的博客来解释cincout的速率问题 总结
提示这里对文章进行总结
