AcWing--数据结构1
用数组来模拟链表。这种实现链表的方式也叫静态链表。
1.单链表
写邻接表：存储图和树
我们定义：e[N]用来表示某个点的值是多少；ne[N]用来表示某个点的next指针是多少
e和ne是用下标关联起来的
如：head->3->5->7->9->空(下标从0开始，3的下标是0，以此类推，空的下标为-1）
那么e[0]=3,ne[0]=1;e[1]=5,ne[1]=2;...e[3]=9,ne[3]=-1
//单链表模板//head指头指针（头指针指向头结点），e[head]指的是头结点的值
//idx指的是下一个可存储的位置的索引，也可以说是插入的第几个数的序号，即idx=0时表示插入的第一个数,其实就是存储当前已经用到的点
int head,idx;int e[N],ne[N]; //e[N]存储的是结点的值，ne[N]存储的是结点的下一个结点的索引 //初始化
void init(){head = -1;//头指针默认赋-1 idx = 0;
}//将x点插入头结点
void insert_to_head(int x){e[idx] = x;
//将要插入的点的下一个指针指向head指向的点ne[idx] = head;
//将head指向新点，并idx指向下一个位置head = idx++;
}//将k后面的点删除
void remove(int k){ne[k] = ne[ne[k]];
}//将x点插入下标为k的点后面
void insert(int k ,int x){e[idx] = x;
//将x点指向k指向的点ne[idx] = ne[k];
//将k指向x点，并idx向后走ne[k] = idx++;
}
#include<iostream>using namespace std;const int N = 1e5+10;int head,idx;//head指头指针（头指针指向头结点），e[head]指的是头结点的值
//idx指的是下一个可存储的位置的索引，也可以说是插入的第几个数的序号，即idx=0时表示插入的第一个数int e[N],ne[N];//e[N]存储的是结点的值，ne[N]存储的是结点的下一个结点的索引 void init(){head = -1;//head的默认值赋-1 idx = 0;
}void insert_to_head(int x){e[idx] = x;ne[idx] = head;head = idx++;
}void remove(int k){ne[k] = ne[ne[k]];
}void insert(int k ,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}int main(){int m;cin>>m;init();while(m--){char op;int k,x;cin>>op;
//头结点if(op == 'H'){cin>>x;insert_to_head(x);}else if(op == 'I'){//插入cin>>k>>x;insert(k-1,x);//第k个插入的数索引为k-1，因为idx是从0开始的，第一个插入的数索引为1；}else{//删K后cin>>k;if(!k) head = ne[head];else remove(k-1);}}for(int i = head ; i != -1 ; i = ne[i]) cout<<e[i]<<" ";cout<<endl;return 0;
} 2.双链表
我们定义：e[N]：当前结点的值是多少；l[N]：当前结点左边是谁；r[N]：当前结点右边是谁
并且令下标为0的点是head，下标为1的点是最后一个点
//双链表模板 int l[N],r[N],e[N]; int idx; //初始化 void init(){//头结点指向尾结点，尾结点指向头节点，头结点指针为0，尾结点指针为1，所以头指针为1，尾指针为0r[0] = 1;l[1] = 0;idx = 2; //从2开始 } //插入，在k的右边插入x void insert(int k, int x){e[idx] = x;//赋值 //先将k的两边分别指向原来链表l[idx] = k;r[idx] = r[k]; //改变原链表的指向l[r[k]] = idx;//必须这步在前面，否则r[k]的值会被修改 r[k] = idx++; }//在K的左边插入，也可以直接调用，insert（l[k],x） //删除第k个点，k右边的左边等于K的左边，K的左边的右边等于k的右边 void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k]; }
#include <iostream>
using namespace std;const int N=100010;
int idx,e[N],l[N],r[N];void init(){//0表示左端点//1表示右端点//虚拟头和虚拟尾l[0]=-1,r[0]=1,l[1]=0,r[1]=-1;idx=2;
}
//最左端插入
void insertLeft(int x){e[idx]=x;r[idx]=r[0];l[idx]=0;l[r[0]]=idx;r[0]=idx;idx++;
}
//最右端插入
void insertRight(int x){e[idx]=x;r[idx]=1;l[idx]=l[1];r[l[1]]=idx;l[1]=idx;idx++;
}void insert_left_k(int k,int x){e[idx]=x;r[idx]=k;l[idx]=l[k];r[l[k]]=idx;l[k]=idx;idx++;
}void insert_right_k(int k,int x){e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}
//删除第k个插入点
void remove(int k){l[r[k]]=l[k];r[l[k]]=r[k];
}int main(){int m;cin>>m;init();int k,x;string s;while(m--){cin>>s;if(s[0]=='L'){cin>>x;insertLeft(x);}else if(s[0]=='R'){cin>>x;insertRight(x);}else if(s[0]=='D'){cin>>k;remove(k+1);}else if(s[0]=='I' && s[1]=='L'){cin>>k>>x;insert_left_k(k+1,x);}else{cin>>k>>x;insert_right_k(k+1,x);}}for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";cout<<endl;return 0;
}
栈和队列
栈：后进先出
队列：先进先出
AcWing 828. 模拟栈
//栈模板
// tt表示栈顶
int stk[N], tt;// 向栈顶插入一个数
stk[ ++ tt] = x;// 从栈顶弹出一个数，删除
tt -- ;// 栈顶的值
stk[tt];// 判断栈是否为空，如果 tt >= 0，则表示不为空
if (tt >= 0) not emptyelse empty
#include <iostream>
using namespace std;const int N=100010;
//tt是栈顶指针
int stk[N],tt;void push(int x){stk[tt]=x;tt++;
}void pop(){tt--;
}bool empty(){if(tt==0) return true;else return false;
}int query(){if(!empty()) return stk[tt-1];
}int main(){tt=0;int m;cin>>m;string s;int x;while(m--){cin>>s;if(s=="push"){cin>>x;push(x);}else if(s=="pop"){pop();}else if(s=="empty"){bool tmp=empty();if(tmp) cout<<"YES"<<endl;else cout<<"NO"<<endl;}else{cout<<query()<<endl;}}return 0;
}
AcWing 829. 模拟队列
//模拟普通队列模板
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;// 向队尾插入一个数
q[ ++ tt] = x;// 从队头弹出一个数
hh ++ ;// 队头的值
q[hh];// 判断队列是否为空，如果 tt >= hh，则表示不为空
if (tt >= hh) not emptyelse empty
//模拟循环队列模板
// 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];// 判断队列是否为空，如果hh != tt，则表示不为空(其实不能这样简单判断是否为空)
if (hh != tt)
{}
单调栈
一般问题：给定一个序列，求序列中的每一个数左边离它最近的且比它小的数在什么地方
//单调栈常见模型：找出每个数左边离它最近的比它大/小的数
int top = -1;
while(n--)
{
while (top >= 0 && check(stk[top], x)) top -- ;
stk[ ++ top] = x;
}
//暴力做法，两重循环
for(int i=0;i<n;i++){
for(int j=i-1;j>=0;j--){
if(a[i]>a[j]){
cout<<a[j]<<endl;
break;
}
}
}
找性质：如果栈中两个数,ai,aj存在：ai>=aj并且i<j，则ai可以删除，这样删完后栈中严格单调。
这样我们从单调栈的栈顶元素开始查找，如果栈顶元素大于等于a[i]，那么我们将其删掉，直到栈顶元素小于a[i]，我们将其作为答案输出，并把a[i]放进栈中。
#include <iostream>
using namespace std;
const int N = 100010;int stk[N];
int tt = -1;int main(){int n;cin>>n;while(n--){int x;cin>>x;while(tt >= 0 && stk[tt] >= x) tt--;//比x大的元素全弹出来 if(tt >= 0) cout<<stk[tt]<<" ";//弹完之后如果还有元素就输出栈顶元素 else cout<<-1<<" ";//无就输出-1 stk[++tt] = x;//最后要把x存入，因为x是有可能比之后的元素小的，并且x离之后的元素最近 }return 0;
}
单调队列
常见用途：求滑动窗口里的最大值或最小值
//单调队列常见模型：
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;
}
随着窗口的移动，每次在队尾插入新元素，同时在队头弹出已经不在窗口里的元素，始终保证队列的长度等于窗口里元素的个数。
暴力做法：遍历整个队列，找到最小值/最大值。o(nk)
优化（最小值举例）：
只要队列里有前面一个数比后面一个数大，那前面的那个数就完全没有用。我们把所有在前面的大的数删掉后，整个序列就是一个单调递增的序列。在单调递增的序列里找最小值只需要找最左边的端点，即队头。
最大值的做法和上面找最小值的做法类似
tips:队列中存储的是下标
#include <iostream>using namespace std;const int N = 1000010;int a[N],q[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 && q[hh] < i-k+1) hh++;//i-k+1为窗口的最左端索引//去掉比当前要进入的数更大的数 while(hh <= tt && a[q[tt]] >= a[i]) tt--;//当前操作数的索引存入数组 q[++tt] = i;// i 等于 k - 1 时，窗口的大小刚好为 k。因此，当 i 大于或等于 k - 1 时，窗口就已经包含了至少 k 个元素。if(i >= k-1) cout<<a[q[hh]]<<" ";}cout<<endl;//最大值，除a[q[tt]] <= a[i]外无变化 hh = 0, tt = -1;for(int i = 0 ; i < n; i++){if(hh <= tt && q[hh] < i-k+1) 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;
}KMP
问题：需要在一个极长的字符串中匹配一个短字符串，比如各种文本编辑器里的查找功能。
即在母串中找到第一次出现完整子串时的起始位置。
我们将母串写为S，模式串写为P
暴力做法：
我们设置一个i指针指向母串和一个j指针指向模式串
当i指针和j指针指向的字符相等时，就同时后移一位；
当i指针和j指针指向的字符不相等时，就将i指针回溯到i-j+1的位置，j指针设置为0，重复匹配的过程，直到到达模式串的末尾，我们认为匹配成功
在最坏的情况下，这个算法的时间复杂度为O(mn)，m为母串的长度，n为模式串的长度
优化：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置
当匹配失败时，我们将j指针移动到第k位，其中k的性质是：模式串P的第0位到第k-1位的串和母串T的i
指针前面的串尽可能地相等，即 T[i-k ~ i-1] == P[0 ~ k-1]
如果我们仔细观察，又能发现 P[0 ~ k-1] == P[j-k ~ j-1]，也就是前缀和后缀相同。
为了能找到j指针回退的位置，我们预处理出来一个数组，称为next数组，也被称为部分匹配表。
next数组的值就表示：当主串与模式串的某一位字符不匹配时，模式串要回退的位置。
手动模拟求next数组：
对 p = “abcab”
p a b c a b
下标 1 2 3 4 5
next[] 0 0 0 1 2
对next[ 1 ] ：前缀 = 空集—————后缀 = 空集—————next[ 1 ] = 0;
对next[ 2 ] ：前缀 = { a }—————后缀 = { b }—————next[ 2 ] = 0;
对next[ 3 ] ：前缀 = { a , ab }—————后缀 = { c , bc}—————next[ 3 ] = 0;
对next[ 4 ] ：前缀 = { a , ab , abc }—————后缀 = { a . ca , bca }—————next[ 4 ] = 1;
对next[ 5 ] ：前缀 = { a , ab , abc , abca }————后缀 = { b , ab , cab , bcab}————next[ 5 ] = 2;
// s[]是长文本，p[]是模式串，m是s的长度，n是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= n; 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 <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
//KMP算法即字符串匹配算法
#include <iostream>using namespace std;const int N = 10010, M = 100010;//p，s，ne数组索引都是从1开始的
char p[N],s[M];
int ne[N];int main(){ int n,m;cin>>n>>p+1>>m>>s+1;// //输出为空
// cout<<p<<endl;
// cout<<s<<endl;
// //输出整个p和整个s
// cout<<p+1<<endl;
// cout<<s+1<<endl;//求ne数组的过程,ne[1]为0，所以从2开始，ne[i]表示从1到i之间，前缀和后缀最长相等元素的长度//next数组的求法是模板串自己与自己进行匹配 for(int i = 2, j = 0; i <= n; i++){//如果不等就回溯while(j && p[i] != p[j+1]) j = ne[j];//如果相等，模板串下标j的元素是提前和文本串对应j的下一个元素也就是下标为i的元素比较，所以j要+1if(p[i] == p[j+1]) j++;//现在j就已经是前缀和后缀最长相等元素的长度，所以要赋给ne[i]ne[i] = j;}//kmp匹配过程，模板串与文本串进行匹配 for(int i = 1, j = 0; i <= m; i++){//如果不等就回溯while(j && s[i] != p[j+1]) j = ne[j];//如果相等，模板串下标j的元素是提前和文本串对应j的下一个元素也就是下标为i的元素比较，所以j要+1（短的为模板串）if(s[i] == p[j+1]) j++;//j == n是找到了完整的相同的字符串if(j == n){cout<<i-n<<" ";//输入匹配完全的字符串的头下标，题目下标是从0开始的，所以不用加一 j = ne[j];//继续回溯找下一个相同的字符串，不要从头开始}}return 0;
}