基础课第二单元学习笔记

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

基础课第二单元学习笔记

作者：

c-y-m , 2025-04-13 10:36:42 · 黑龙江 , 所有人可见 , 阅读 2

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];

////************************循环队列

int q[N], hh = 0, tt = 0;

q[tt ++ ] = i; // 插入
if (tt == N) tt = 0;
hh ++;          // 弹出
if (hh == N) hh = 0;
if (hh == tt) 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值，把一位数组的每个位置拉一条链
只要一个数映射下来了就在链上单开一个位置存储这个值