链表（用数组），单链表：存储图和树
双链表：优化某些题
做法：
==演示==：
head->0->1->2->3->-1
值： 3 5 7 9
e[0]=3 e[1]=5 e[2]=7 e[3]=9
ne[0]=1 ne[1]=2 ne[2]=3 ne[3]=-1
单链表的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void init(){
head=-1;
idx=0;
}
void add_to_head(int x){
e[idx]=x,ne[idx]=head,head=idx++;
}
void add(int k,int x){
e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(int k){
ne[k]=ne[ne[k]];
}
|
双链表：
没有head，0号点指向第一个点，1号点指向最后一个点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void init(){
r[0]=1,l[1]=0;
idx=2;
}
void d_add(int x){
r[l[x]]=r[x];
l[r[x]]=l[x];
}
void IR_add(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
|
栈
栈：先进后出
队列：先进先出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| if(op=="push"){
int k;
cin>>k;
stk[++tt]=k;
}
else if(op=="pop"){
tt--; `
}
else if(op=="empty"){
if(!tt) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else{
cout<<stk[tt]<<endl;
}
|
表达式求值
如何判断某棵子树是否被遍历完？
答：看当前运算符优先级≤上一运算符优先级，表示子树遍历完了。”（“ ：无影响 “）”：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<iostream>
#include<stack>
#include<string>
#include<unordered_map>
using namespace std;
const int N=100010;
stack<int> num;
stack<char> op;
unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}};
void eval(){
int r=0;
int a=num.top();
num.pop();
int b=num.top();
num.pop();
char c=op.top();
op.pop();
if(c=='+') r=a+b;
if(c=='-') r=b-a;
if(c=='*') r=a*b;
if(c=='/') r=b/a;
num.push(r);
}
int main(){
string str;
cin>>str;
for(int i=0;i<str.size();i++){
auto c=str[i];
if(isdigit(str[i])){
int x=0,j=i;
while(j<str.size()&&isdigit(str[j])){
x=x*10+str[j]-'0';
j++;
}
i=j-1;
num.push(x);
}
else if(str[i]=='('){
op.push(str[i]);
}
else if(str[i]==')'){
while(op.top()!='(') eval();
op.pop();
}
else{
while(op.size()&&h[op.top()]>=h[str[i]]){
eval();
}
op.push(str[i]);
}
}
while(op.size()) eval();
cout<<num.top()<<endl;
return 0;
}
|
队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| if(s=="push")
{
int x;
cin>>x;
p[++tt]=x;
}
else if(s=="pop")
{
hh++;
}
else if(s=="empty")
{
if(hh<=tt) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else{
cout<<p[hh]<<endl;
}
|
单调栈
给定一个序列，求每一个数，左边最近比他小的数
若x<y,ax>ay,则ax不会被输出；
因此，最后输出的肯定是一个单调上升的序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<iostream>
using namespace std;
const int N=100010;
int s[N],tt=-1;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
while(tt!=-1&&s[tt]>=x){
tt--;
}
if(tt!=-1) cout<<s[tt]<<" ";
else cout<<"-1"<<" ";
s[++tt]=x;
}
return 0;
}
|
滑动窗口
整数数组，大小为k的滑动窗口
适用于：每次滑动的过程中，输出窗口中的最小值、最大值/找出离他最近的最大/最小的元素
思考方式：用一个队列维护窗口里面的所有值，每次把一个数查到队尾，队头去除一个数；每次求最小值的时候进行暴力枚举
时间复杂度：O（nk)
优化：在队列中，如果后面有一个元素比当前元素小，前面的元素删掉（视为冗余元素）；则可以看成从小到大递增的队列；则此时找最小值只需要O（1）；整体复杂度O（n）
- 用普通队列怎么做
- 将队列中的冗余元素删掉——具有了单调性
- 可以用O（1）时间从队头/队尾取出最值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
using namespace std;
const int N=1000010;
int a[N],q[N],hh,tt=-1;
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
if(i-k+1>q[hh]) ++hh;
while(hh<=tt&&a[q[tt]]>=a[i]) --tt;
q[++tt]=i;
if(i+1>=k) printf("%d ",a[q[hh]]);
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++) {
if(i-k+1>q[hh]) ++hh;
while(hh<=tt&&a[q[tt]]<=a[i]) --tt;
q[++tt]=i;
if(i+1>=k) printf("%d ",a[q[hh]]);
}
return 0;
}
|
KMP
暴力算法
1
2
3
4
5
6
7
8
9
10
| S[N],p[M];
for(int i=1;i<=n;i++){
bool flag=true;
for(int j=1;j<=m;j++){
if(s[i]!=p[j]){
flag=false;
break;
}
}
}
|
利用额外信息(每一个点的后缀和前缀相等的最大长度)——next[i]：以i为终点的后缀和从1开始的前缀相等，且后缀长度最长，即：p[1,j]=p[i-j+1,i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
using namespace std;
const int N=100010,M=1000010;
int n,m,i,j;
char p[N],s[M];
int ne[N];
int main(){
cin>>n>>p+1>>m>>s+1;
for(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(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){
printf("%d ",i-j);
j=ne[j];
}
}
return 0;
}
|
Trie树
基本用法：高效地存储和查找字符串集合的数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void insert(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}
|
并查集
处理：
- 将两个集合合并
- 询问两个元素是否在一个集合中
时间复杂度：近乎O(1)
基本原理：每个集合用一颗树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示x的父节点
问题1：如何判断树根 ：if(p[x]==x)
问题2：如何求x的集合编号：while(p[x]!=x) x=p[x]
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号，p[x]=y
优化（路径压缩）：一旦往上走找到了根节点，路径上所有的点直接指向根节点
做题时候，有一道题的find(int x)我用的
1
2
3
4
| int find(int x){
while(x!=p[x]) x=find(p[x]);
return x;
}
|
直接TLE
后面改成优化的代码，AC了
1
2
3
4
| int find(int x){
if(x==p[x]) return x;
return p[x]=find(p[x]);
}
|
食物链
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<iostream>
#include<algorithm>
using namespace std;
int n,m,sum;
const int N=(1e4+10)*5,M=1e5+10;
int p[N],t[N];
int find(int x){
if(p[x]!=x){
int k=find(p[x]);
t[x]=t[p[x]]+t[x];
p[x]=k;
}
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
while(m--){
int x,a,b;
cin>>x>>a>>b;
if(a>n||b>n) sum++;
else{
int pa=find(a),pb=find(b);
if(x==1){
if(pa==pb&&((t[a]-t[b])%3)) sum++;
else{
if(pa!=pb){
p[pa]=pb;
t[pa]=t[b]-t[a];
}
}
}
else{
if(pa==pb&&((t[a]-t[b]-1)%3)) sum++;
else{
if(pa!=pb){
p[pa]=pb;
t[pa]=t[b]-t[a]+1;
}
}
}
}
}
cout<<sum;
return 0;
}
|
堆排序
如何手写一个堆？
插入一个数
1
2
| heap[++size]=x;
up(size);
|
求集合当中的最小值
删除最小值
1
2
3
| heap[1]=heap[size];
size--;
down(1);
|
删除任意一个元素
1
2
3
4
| heap[k]=heap[size];
size--;
down(k);
up(k);
|
修给任意一个元素
1
2
3
| heap[k];
down(k);
up(k);
|
完全二叉树：除了最后一层其他层都是非空的，最后一层从左向右依次排布
小根堆：每一个点小于等于左右儿子
根节点：最小值
堆的存储：1号点位个节点；左儿子：2x；右儿子：2x+1（因此，堆的下标从1开始）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void down(int x){
int t=x;
if(2*x<=siz&&h[x]>h[2*x]) t=2*x;
if(2*x+1<=siz&&h[t]>h[2*x+1]) t=2*x+1;
if(x!=t) {
swap(h[x],h[t]);
down(t);
}
}
void up(int x){
while(x/2&&h[x/2]>h[x]){
heap_swap(x,x/2);
x=x/2;
}
}
|
堆排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,siz,h[N];
void down(int x){
int t=x;
if(2*x<=siz&&h[x]>h[2*x]) t=2*x;
if(2*x+1<=siz&&h[t]>h[2*x+1]) t=2*x+1;
if(x!=t) {
swap(h[x],h[t]);
down(t);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
}
siz=n;
for(int i=n/2;i;i--) down(i);
while(m--){
printf("%d ",h[1]);
h[1]=h[siz];
siz--;
down(1);
}
return 0;
}
|
模拟堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010;
int h[N],hp[N],ph[N],siz;
void heap_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int x){
int t=x;
if(2*x<=siz&&h[x]>h[2*x]) t=2*x;
if(2*x+1<=siz&&h[t]>h[2*x+1]) t=2*x+1;
if(x!=t) {
heap_swap(x,t);
down(t);
}
}
void up(int x){
while(x/2&&h[x/2]>h[x]){
heap_swap(x,x/2);
x=x/2;
}
}
int main(){
int n,m=0;
scanf("%d%d",&n);
while(n--){
char op[10];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I")){
scanf("%d",&x);
siz++;
m++;
ph[m]=siz,hp[siz]=m;
h[siz]=x;
up(siz);
}
else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
else if(!strcmp(op,"DM")){
heap_swap(1,siz);
siz--;
down(1);
}
else if(!strcmp(op,"D")){
scanf("%d",&k);
k=ph[k];
heap_swap(k,siz);
siz--;
up(k),down(k);
}
else{
scanf("%d%d",&k,&x);
k=ph[k];
h[k]=x;
down(k),up(k);
}
}
return 0;
}
|
模拟散列表（哈希表）
把较大的值域映射到较小的空间
x mod 1e5（一般取质数，一般离2的整次幂较远）- 冲突解决：开放寻址法/拉链法
- 一般只有添加和查找两个操作
存储结构
开放寻址法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<cstring>
#include<iostream>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x){
k++;
if(k==N) k=0;
}
return k;
}
int main(){
int n;
scanf("%d",&n);
memset(h,0x3f,sizeof h);
while(n--){
char op[2];
scanf("%s",op);
int x;
scanf("%d",&x);
int k=find(x);
if(*op=='I') h[k]=x;
else{
if(h[k]==x) puts("Yes");
else puts("No");
}
}
return 0;
}
|
拉链法
- 开一个一维数组存储所有的值
[0,1e5-1]
- 每一个槽上的链用来存储这条链上的数
1
2
3
4
5
6
7
8
9
10
11
| void insert(int x){
int k=(x%N+N)%N;
e[idx]=x,ne[idx]=h[k],h[k]=idx++;
}
bool find(int x){
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i]){
if(e[i]==x) retirn true;
}
return false;
}
|
字符串哈希方式
使用字符串前缀哈希法
str=”ABCABCDEYXCACWING”
h[0]=0（h为哈希值）
h[1]=”A”
h[2]=”AB”
h[3]=”ABC”
h[4]=”ABCA”
A B C D
(1 2 3 4)p
=(1p^3^+2p^2^+3p^1^+4p^0^)mod Q
tips:
- 不能映射成0，因为他们
mod Q之后都是0，会产生冲突
- 加入Rp足够好，就不存在冲突，所以不考虑冲突
- 一般来说，令p=131或13331，Q=2^64^,可以保证不会出现冲突
