1、单向链表和双向链表
这里直接给出模板,可以按模板理解
https://www.acwing.com/activity/content/code/content/9345631/
https://www.acwing.com/activity/content/code/content/9347058/
2、栈与队列
数组模拟法
//************************栈
st[N]表示栈 , top表示栈顶
//插入
st[++top] = x;
//弹出
top--l
//判断栈是否为空
if ( top )
not empty()
else
empty();
//************************队列
//在队尾插入元素,在队头弹出元素
int q[N],hh,tt; = -1
//插入
q[++tt] = x;
//弹出
hh++;
//判断是否为空
if( hh <= tt )
not empty();
else
empty();
//队头元素
q[hh];
3、单调栈
常见题型
给定一个序列,对每个数左边离他最近的 , 且比他小的数在什么地方
这是基本模型,可以对应成右边或最大都可以
我们可以先把这些数存进栈,然后考虑哪些栈中的数是无用的,把没用的弹栈;
a1 , a2 , a3 , a4 , a5 , … , an;
如果a3 >= a5那么a3就是没用的,因为如果a3可以输出就一定可以输出a5,而a5肯定是离剩下元素更近的,所以a3没用
这样操作后栈就是单调上升的;
然后因为栈先进后出的特性,答案就是st[top] , 因为坐标最靠左的会最后入栈
https://www.acwing.com/activity/content/code/content/9350350/
4、单调队列
经典题目
https://www.acwing.com/problem/content/156/
这个滑动过程可以用队列维护,然后我们考虑这个数字什么时候没有用
先考虑最小值,最大值就会了
我们看一下例子
1 [ 3 -1 -3 ] 5 3 6 7
我们发现窗口里的3是没用的 , 因为只要-3在的一天,那么3就永远不会成为答案,并且-3在窗口里的时间比3长,所以3就没用了
同理-1也没有用了
操作完后明显队列是单调上升的
竟然是单调上升的并且还要求最小值那答案就是队头
https://www.acwing.com/activity/content/code/content/9350808/
5、KMP
题目
https://www.acwing.com/problem/content/833/
暴力做法就是一位一位的匹配就行,而KMP算法是会省略一些不需要再次匹配的东西;
这里用图片描述一个重要数组Next数组
https://cdn.luogu.com.cn/upload/image_hosting/zsxrwg3j.png
这里的绿线表示文本串,红线表示模式串,蓝色表示第一个匹配失败的地方
我们要求把模式串移到哪里能使紫线位置相同,并且最长
然后Next[i]表示以i点结束的字符串的最长公共前后缀
也就是说
Next[i] = j , p[1 , j] = p[i - j + 1 , i];
Next数组的求法
就是我们对模式串自己进行匹配,匹配成功的位置就是Next[i]的答案
因为把第二个模式串向右移动与第一个模式串,匹配成功的位置就是最长公共前后缀
https://www.acwing.com/activity/content/code/content/9351446/
6、Trie(字典树)
基本用法:高效存储和查找字符串集合的数据结构
假设我们要存abcdef,abdef,aced,bcdf,bcff,cdaa,bcbc这几个字符串的存的方式
https://cdn.luogu.com.cn/upload/image_hosting/vatdzy6p.png
并且每个单词结尾的字母要打上标记,因为如果一个单词包含另一个单词,如果不打标记,你就不知道有没有被包含单词
https://cdn.luogu.com.cn/upload/image_hosting/lyk0z2kg.png
查找就是如果这个字母包含在这个单词中,并且前面已经配对成功,那么就接着往下遍历
字母转数字
ASCll码’A’:65 ‘a’:97 ‘0’:48 ‘1’:49
后面的’B’ , ‘b’ , ‘2’依次递增
所以小写字母转数字就是- ‘a’
https://www.acwing.com/activity/content/code/content/9441920/
例题
https://www.acwing.com/activity/content/code/content/9442869/
7、手写堆
堆支持的
1、插入一个数
2、求最小值
3、删最小值
4、删任意数
5、改任意数
堆是完全二叉树,每个点的值小于左右儿子,根节点是最小值(这是小根堆 , 大根堆就是大于,接下来说小根堆)
存储用1维数组x的左儿子是2x,右儿子是2x+1;
核心操作:down , up
down:我改变了值,使其过大,就用他的儿子和他自己比较,把较小的和他交换,一直到合法
up:我改变了值,使其过小,如果父亲节点比他大,就交换2个节点,一直到合法
怎样实现5种操作
1、插入一个数 heap[++cnt] = x , up(cnt);
2、求最小值 heap[1];
3、删最小值 heap[1] = heap[size–] , down(1);
4、删任意数 heap[k] = heap[size–],down(k),up(k);
5、改任意数 heap[k] = x , down(k) , up(k);
这里求最小值、删任意数有技巧
因为删掉第一个不好删,我们可以删最后一个,并且把最后一个的值覆盖到1号节点 , 然后down(要删的节点)
堆排序
https://www.acwing.com/activity/content/code/content/9359848/
这里由于我们只执行down操作,那么最后一层在建树时不用管,最后一层点的个数是n / 2,其他层点的个数是n / 2;
所以有n / 2遍历到0建堆就可以
完整堆
https://www.acwing.com/activity/content/code/content/9360796/
8、hash表
hash函数:把很大的数映射变为一个从0->mod的整数
h(x) = 0 / 1 / 2 / ....... / N - 1 / N - 2 / N;
最简单的做法:x % mod;
但是他会出现冲突,比如mod = 2 , x = 4 , y = 6
虽然x != y ,但是直接mod就会认为x == y;
拉链法
用一维数组存储hash值 , 把一位数组的每个位置拉一条链
只要一个数映射下来了就在链上单开一个位置存储这个值
大致结构
0 1 2 3 4 . . . . . . . . . . . . .. . . . . . . .. . N
(11) (33) (87)
(22) (47)
这个链用邻接表存储即可(edge)
开放寻址法
首先开一个一维数组,开到数据范围的3倍
添加:从前往后找,找到第一个没有数的位置,把他加进去
查找:从前往后找,如果这个位置有数就判断是不是x,
如果没人就说明x不存在
https://www.acwing.com/activity/content/code/content/9363202/
9、并查集难题
https://www.acwing.com/activity/content/code/content/9359474/
还有递归过程图
https://cdn.acwing.com/media/article/image/2020/07/08/41774_bd485030c0-JIE.jpg
10、STL容器
vector
支持clear(),支持按字典序比较大小
clear操作不是每个STL都有的,没有的就用
st = stack < int > ();
q = queue < int > ();这样的方法清空
pair
支持以first为第一关键字,second为第二关键字比较大小
string
a.substr( idx , len );
表示截取a从idx开始长度为len的子串
a.c_str();
需要位置:printf( “%s” , a.c_str() );