数据结构

1. 模拟单链表
   关键参数
   head 初始化为-1 //head本身是个“指针”，并不占于N中
   e[N],he[N]
   idx
   操作:头插入,k后插入,k后删除
2. 模拟双链
   关键参数
   head,tail 初始化为0,1 //0,1即为他们在N中的下标
   e[N],l[N],r[N]
   idx
   操作:k后插入,k删除
3. 模拟栈
   关键参数
   hh 初始化为0
   stk[N]
   操作:判断栈是否为空,压入元素，弹出元素
4. 模拟队列
   关键参数
   hh,tt 初始化为0,-1
   q[N]
   操作:判断队列是否为空,队尾压入元素,队头弹出元素

算法

1. 单调栈
   常见模型：找出每个数左边离它最近的比它大/小的数
   y总的模板：
   int tt = 0;
   for (int i = 1; i <= n; i )
   {
   while (tt && check(stk[tt], i)) tt – ;
   stk[ tt] = i;
   }
   注意这里的while,每次进行for循环开始对栈进行操作，直到栈顶元素与i之间满足某种性质才停止pop并压入新元素,
   这步是可以停下来的，最坏的情况是i把栈清空。

2. 单调队列
   常见模型：找出滑动窗口中的最大值/最小值
   y总的模板：
   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;
   }
   这里实际上是一个双端队列,与单调栈类似，不同点是q[N]中存储的不再是具体的值而是原数组中点的坐标[i],思考一下可以发现单调栈其实也可以这样，然后每次比较的时候check(stk[a[hh]],i)就可以了.相比之下,不同点在于考虑到窗口的移动,必须判断队头是否已经滑出窗口之外,否则可能在while pop tt时弹向不在窗口内的元素最终输出一个窗口之外的最小(最大)元素,这显然是错误的.

3. kmp
   s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
   y总的模板:
   求模式串的Next数组：
   for (int i = 2, j = 0; i <= m; i )
   {
   while (j && p[i] != p[j + 1]) j = ne[j];
   if (p[i] == p[j + 1]) j ;
   ne[i] = j;
   }
   for (int i = 1, j = 0; i <= n; i )
   {
   while (j && s[i] != p[j + 1]) j = ne[j];
   if (s[i] == p[j + 1]) j ;
   if (j == m)
   {
   j = ne[j];
   }
   }
   属于是讲不太明白,我再想想

小技巧与知识

• new操作巨慢,笔试如果new 10^7基本就超时了

今日模板算法默写框架

单调栈
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
}

单调队列
int hh = 0, tt = -1;
for (int i = 0; i < n; i )
{
}
kmp
s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i )
{
}
for (int i = 1, j = 0; i <= n; i ++ )
{
}