• 链表与邻接表
  • 栈与队列
  • kmp

用数组来模拟

好处：速度快（快很多）

单链表

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
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
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++;
}
//将x插入到下标为k的点后面
void add(int k, int x)
{
    e[idx]=x, ne[idx]=ne[k], ne[k]=idx++;
}  
//将下标为k的点的后面的一个点移除
void  remove(int k)
{
    ne[k]=ne[ne[k]];
}
int main()
{
 	int m;
    cin>>m;
    init();
    while(m--)
    {
        int k,x;
        char op;
        cin>>op;
        if(op=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if (op=='D')
        {
            cin>>k;
            //特判 
            if(k==0)
            {
            	//如果 k为0 那么移除头结点 
            	head=ne[head];
            	continue;
			}
            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;
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int e[N],l[N],r[N],idx;
//初始化
void init()
{
    r[0]=1, l[1]=0;
   	idx=2;
}
//在下标为k的点的右边插入x
void add(int k, int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
}
//在k左边插入一个点，就调用add(l[k],x)

//删除第k个点
void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

栈与队列

栈——先进后出 队列——先进先出

  • 数组模拟栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using naemspace std;
const int N =100010;
int stk[N], tt;
//插入
stk[++tt]=x;

//弹出
tt--;

//判断栈是否为空
if(tt>0)	not empty
else	empty
    
//栈顶
stk[tt];
  • 数组模拟队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using naemspace std;
const int N =100010;
//在队尾插入元素，在队头弹出元素
int q[N], hh, tt=-1;

//插入
q[++tt]=x;

//弹出
hh++;

//判断队列是否为空
if(hh<=tt)	not empty
else	empty

//取出队头元素
q[hh]
//尾
q[tt]

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
	int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;	cin>>x;
        while(tt && stk[i] >=x)	tt--;
        if(tt)	cout<<stk[tt]<<" ";
        else	cout<<-1<<" ";
        
        stk[++tt]=x;
    }
    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
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k;
int a[N], q[N];
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++)	scanf("%d", &a[i]);
    
    //最小
    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;
        if(i>=k-1)	printf("%d ", a[q[hh]]);
    }
    puts("");
    
    //最大
    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;
        if(i>=k-1)	printf("%d ", a[q[hh]]);
    }
    puts("");
    
    return 0;
}

KMP

如何获取一个char数组的长度，用strlen()，但用它之前要确保在数组末尾添加null（’\0’）终止符

示例Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cstring>

int main()
{
    const int MAX_SIZE = 10;
    char x[MAX_SIZE + 1]; // 增加一个额外的位置，用于存储null终止符
    std::cin >> x + 1; // 将输入存储到x+1位置上
    x[MAX_SIZE] = '\0'; // 确保最后一个字符为null终止符
    std::cout << strlen(x + 1) << std::endl;

    return 0;
}

KMP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n,m;
char p[N], s[M];
int ne[N];

int main()
{
    cin>>n>>p+1>>m>>s+1;
    
    //求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;       
    }
    
    //kmp匹配过程
    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)
        {
            printf("%d ", i-n);
            j=ne[j];
        }
    }
    
 	return 0;   
}