涅槃豆の博客

哈希表主要作用 把一个比较大的空间或者值域映射到比较小的空间里 存储方式1.开放寻址法只需要开一个一维数组，但数组一般来说会开到所定范围的两到三倍 假设有一个宾馆有很长都走廊，之间有足够多的房间互相连接，且每个房间只能住一人 如果想要插入一个数，就将该数插入到一个编号房间中 如果新插入的数的房间刚好有人，那就去找她下一个的房间，直到找到一个空房间 2.拉链法假设有一个很长的走道，走道之间有足够长的槽口互相连接 如果想插入一个数，就将该数插入到一个编号槽口中 如果刚好新插入的数所要插入的编号槽口中有数了，即发生冲突了，那么就用一根绳串连槽口中的两个数 顶端就是各个槽口，下方的每个数用一根根拉链串联起来 假设要存x，凹槽有1e5 + 3，那么要存的x就是将x强行放到凹槽内，他对应的凹槽编号就是（ x % （1e + 5） ） （凹槽为质数时冲突最小） 操作方式添加一个数查询一个数删除一个数 关于删除一个数 直接在这个地方打个标记，查询的时候就查不到他身上了 实现代码开放寻址法 #define _CRT_SECURE_NO_WARNINGS 1#include <iostream& ...

堆功能（操作）插入一个数求集合中的最小值删除最小值 额外的操作删除任意一个元素修改任意一个元素 堆的本质二叉树，且是完全二叉树（即除了最后一层的节点，其他层的节点的分支都有两个，最后一层的节点从左到右排列） 小根堆的特点从上往下看，每个节点的值依次增高所以根节点是最小的值再往下左边的节点比他下面的两个节点还小，右边的节点也比他下面的两个节点还小 堆的存储用一维数组存储所有的节点 对于根节点 就存储在q[1]根节点的左节点 存储在q[2],右节点存储在q[3]左节点的左节点存储在q[4], 右节点存储在q[5]右节点的左节点存储在q[6], 右节点存储在q[7] 因此可以得出一个规律,从根节点开始，节点设为x x下面的左节点就存储在q[2 * x],右节点就存储在q[2 * x + 1] down操作 简单来说就是把一个节点往下移如果一个节点的值改变了，那么他在堆里应该放在适合的位置 改变时的树 down操作的原理是如果该节点比他下面的节点大的话，那么就交换一下如果交换后还比下面的大，那么就再和下面的节点交换直到符合小根堆的性质 down操作后的树 up操作与 ...

需要掌握的前提数据结构字典树Trie 1.作用 能够两个集合合并询问两个元素是否在一个集合当中 注：集合指的是trie树那种存储字符串和数组的集合 时间复杂度，接近 O(1) 2.原理 每个集合都是一颗树，树根root的编号就是集合的编号，每个节点存储他的父节点，用p[x]表示x的父节点 2.1对于树根的判断 除了树根以外，其余的节点的父节点都不是x 那么就可以通过该行代码来判断 if(p[x] == x) 2.2如何求节点x的集合编号 对该节点沿着路径一直找到树根， while(p[x] != x) x = p[x]; 循环到最后一定是 p[x] == x 即树根 2.3如何合并集合 可以让其中一个树的树根直接插到另一个树的某一节点上，这样就实现了集合的合并 比如要将y的集合插到x里去树根编号p[x] == x,p[y] == y让p[y] = x;即y树根节点的父节点就是x的根节点 2.4对求节点x集合编号的优化（路径压缩）在第一次查询x节点的集合编号时，顺带把这条路径上的所有父节点全都指向根节点 实现代码+例题 #define _C ...

作用用来高效快速存储和查找字符串集合的一种数据结构 存储图解假设有若干个字符串 先创建了一个根结点root，代指字符串集合的开头，对第一个字符串abcdef存储就如上图所示 当存储abdef时，一直走到b都和abcdef相同，于是在b点另开一个分支存储之后的def 当存储aced时，一直走到a都和abcdef相同，于是在a点另开一个分支存储之后的ced 以此类推 … 我们就得到能够以树的形式存储一个字符串集合 并且在每个字符串的结尾的字母都标记一下，表示以该字母结尾的节点是存在一个字符串的 如果有类似abc这样的字符串，也要在c点标记一下 查找图解如果要查找一个不存在的字符串，比如abcf 沿着树枝一直走，走到c之后发现没有f对应的路径，那么就说明该字符串不存在 或者查找一个字符串，该字符串在存储里的字符串不存在，但属于某个存储的字符串的前缀 比如abcdef中的abc作为要查找的字符串 沿着树枝走，发现c点没有标记，即使有对应对应路径也不能说明该字符串存在 代码实现#define _CRT_SECURE_NO_WARNINGS 1#include <iostream> ...

KMP算法如何选择算法的关键就在于先看暴力法如何做，再去想哪种算法能够优化他 KMP是什么一种字符串匹配算法，用于查找一个模板字符串在一串长文本里每次出现的起始下标，类似于crtl+f的功能 假设有数组长文本K[N],模板P[M] 暴力法对字符串匹配：设i作为K的下标，j作为p的下标，当K[i]与 P[0]相等时，开始匹配下个字符，否则让i++，如果连续匹配到很多个字符，但突然有一个不匹配，那么i与j都会回溯，比如K[i]和P[0]相等了，一直匹配到K[i + random],P[j + random]时匹配失败，那么i，与j都会回溯，K的下标i + random回溯到i++，j + random回溯到j = 0 KMP算法就是针对这一暴力法进行优化，使得i无需回溯。通过修改j 的位置，让模式串P尽量地移动到有效的位置。 因此需要一个next数组使模式串能够快速移动，如果P[j]时失配了，那么就根据j对应的next[j] 使模式串跳跃，如果next[j] 为0 或 - 1，那么就跳到模式串开头位置，反之，则跳过next[j]个字符，继续匹配 对于如何求出next对应的值，可以 ...

栈栈的特点先进后出，和一个半封闭容器类似，放了一堆肉饼，先放的肉饼后倒出来 stk[n]数组代表栈，tt代表栈点 关于栈的插入void add(int x)//插入元素{ stk[++t] = x;} 关于栈的删除void del( )//删除元素，即弹出一个肉饼{ tt--;} 关于判断栈是否为空bool stkempty()//判断栈是否为空{ if (tt > 0) return false; else return true;} 总实现代码#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;const int N = 10010;int stk[N], tt;//stk表示栈，tt表示栈点下标void add(int x)//插入元素{ stk[++t] = x;}void del( )//删除元素，即弹出一个肉饼{ tt--;}bool stkempty()//判 ...