算法基础 第3章 数据结构

1.单调栈1.什么是单调栈单调栈即具有单调性的栈。实现#includeiostream#includestackusingnamespacestd;constintN3e610;inta[N],n;voidtest1(){stackintst;// 维护⼀个单调递增的栈for(inti1;in;i){// 栈⾥⾯⼤于等于 a[i] 的元素全部出栈while(st.size()st.top()a[i])st.pop();st.push(a[i]);}}2.单调栈解决的问题寻找当前元素左侧离它最近且比它大的元素在哪寻找当前元素左侧离它最近且比它小的元素在哪寻找当前元素右侧离它最近且比它大的元素在哪寻找当前元素右侧离它最近且比它小的元素在哪虽然是四个问题但是原理是⼀致的。因此只要解决⼀个举⼀反三就可以解决剩下的几个。3.寻找当前元素左侧离它最近并且比它大的元素在哪从左往右遍历元素构造⼀个单调递减的栈。插入当前位置的元素的时• 如果栈为空则左侧不存在比当前元素大的元素• 如果栈非空若栈顶元素比当前位置大则栈顶元素为目标元素若栈顶元素比当前元素小出栈维护单调递减栈。注意因为我们要找的是最终结果的位置。因此栈里面存的是每个元素的下标。1.1【模板】单调栈P5788 【模板】单调栈2.单调队列1.什么是单调队列单调队列即存储的元素要么单调递增要么单调递减的队列这里的队列是个双端队列。2.单调队列解决的问题一般用于解决滑动窗口内最大值最小值问题以及优化动态规划。2.1 滑动窗口 /【模板】单调队列P1886 滑动窗口 /【模板】单调队列#define_CRT_SECURE_NO_WARNINGS#includeiostream#includedeque//https://www.luogu.com.cn/problem/P1886usingnamespacestd;constintN1e610;intn,k;inta[N];//单调队列intmain(){cinnk;for(inti1;in;i)cina[i];//存储下标的双端队列dequeintq;//找窗口内最小值for(inti1;in;i){//单调递增的队列while(q.size()a[i]a[q.back()])q.pop_back();q.push_back(i);//判断是否在窗口内并更新队列if(q.size()i-q.front()k)q.pop_front();//当窗口大小达到k时取出窗口内的最值if(ik)couta[q.front()] ;}coutendl;q.clear();//找窗口内最大值for(inti1;in;i){//单调递减的队列while(q.size()a[i]a[q.back()])q.pop_back();q.push_back(i);//判断是否在窗口内并更新队列if(q.size()i-q.front()k)q.pop_front();//当窗口大小达到k时取出窗口内的最值if(ik)couta[q.front()] ;}coutendl;return0;}3.并查集3.1并查集的概念及实现3.1.2并查集的概念并查集(Union Find是一种用于维护元素所属集合的数据结构实现为一个森林其中每棵树表示一个集合树中的节点表示对应集合中的元素根节点来代表整个集合。实现并查集的时我们⼀般让根节点自己指向自己。我们需要维护若干个集合查询操作查找x属于哪一个集合合并操作将x所在集合和y所在集合合并成一个集合判断操作判断x和y是否在同一个集合3.1.2并查集的实现1.初始化让元素自己指向自己for(inti1;in;i)fa[i]i;2.查询// 返回父亲节点intfind(intx){if(fa[x]x)returnx;// 路径压缩 把被查询的节点到根节点的路径上的所有节点的⽗节点设置为根节点returnfa[x]find(fa[x]);// ⼀⾏实现returnfa[x]x?x:fa[x]find(fa[x]);}3.合并将元素 x 所在的集合与元素 y 所在的集合合并成⼀个集合让元素 x 所在树的根节点指向元素 y 所在树的根节点。// 合并操作voidun(intx,inty)// 注意函数名字不能⽤ union因为它是 C 的关键字{intfxfind(x);intfyfind(y);// 让元素 x 所在树的根节点指向元素 y 所在树的根节点。fa[fx]fy;}4.判断判断元素 x 和元素 y 是否在同⼀集合看看两者所在树的根节点是否相同。// 合并操作// 判断是否在同⼀集合boolissame(intx,inty){returnfind(x)find(y);}3.2普通并查集P3367 【模板】并查集3.3拓展并查集普通的并查集只能解决各元素之间仅存在⼀种相互关系比如《亲戚》题目中• a 和 b 是亲戚关系 b 和 c 是亲戚关系这时就可以查找出 a 和 c 也存在亲戚关系。但如果存在各元素之间存在多种相互关系普通并查集就无法解决。比如下面的案例• a和 b是敌⼈关系 b和 c是敌人关系但是 a和 c其实不是敌人关系而是另⼀种朋友关系。此时就不仅仅是简单的敌⼈关系还是出现⼀种朋友关系。解决这类问题就需要对并查集进行扩展将每个元素拆分成多个域每个域代表⼀种状态或者关系。通过维护这些域之间的关系来处理复杂的约束条件。下例中若1与2是敌人且2与3是敌人那么1和3就在同一个集合中则1与3是朋友以下题为例实现关键在于将敌人的敌人合并P1892 [BalticOI 2003] 团伙#define_CRT_SECURE_NO_WARNINGS#includeiostream//https://www.luogu.com.cn/problem/P1892usingnamespacestd;constintN1e310;// 拓展并查集intn,m,p,q;charopt;intfa[N*2];intfind(intx){if(fa[x]x)returnx;returnfa[x]find(fa[x]);}// 使朋友域元素为父节点voidun(intx,inty){intfxfind(x),fyfind(y);fa[fy]fx;}intmain(){cinnm;for(inti1;i2*n;i)fa[i]i;while(m--){cinoptpq;if(optF){un(p,q);}else{//敌人的敌人是朋友un(p,qn);un(q,pn);}}intres0;for(inti1;in;i){if(fa[i]i)res;}coutresendl;return0;}3.4带权并查集1.带权并查集的概念带权并查集在普通并查集的基础上为每个结点增加了⼀个权值。这个权值可以表示当前结点与父结点之间的关系、距离或其他信息注意由于我们有路径压缩操作所以最终这个权值表示的是当前结点相对于根结点的信息。有了这样⼀个权值就可以推断出集合中各个元素之间的相互关系。2.带权并查集的实现实现⼀个能够查询任意两点之间距离的并查集。实现带权并查集的核心是在进行Find和Union操作时不仅要维护集合的结构还要维护结点的权值。基本操作constintN1e510,INF0x3f3f3f3f;intn;intfa[N],d[N];// 初始化voidinit(){for(inti1;in;i){fa[i]i;d[i]0;// 根据题⽬要求来初始化这里表示到父节点距离}}// 查询操作intfind(intx){if(fa[x]x)returnx;inttfind(fa[x]);// 这句代码⼀定要先执⾏先缩短路径// 更新到根节点的距离d[x]d[fa[x]];// 会根据权值的意义有所改变returnfa[x]t;}// 合并操作// x 所在集合与 y 所在集合合并x 与 y 之间的权值是 wvoidun(intx,inty,intw){intfxfind(x),fyfind(y);if(fx!fy)// 不在同⼀个集合中{fa[fx]fy;// 更新到根节点的距离d[fx]d[y]w-d[x];// 会根据权值的意义有所改变}}4.字符串哈希什么是字符串哈希定义⼀个把字符串映射到整数的函数 这就是字符串哈希。即将⼀个字符串用一个整数表示。字符串哈希中的哈希函数在字符串哈希中有⼀种冲突概率较小的哈希函数将字符串映射成 p 进制数字h a s h ( s ) ∑ i 0 n − 1 s [ i ] × p n − i − 1 ( m o d M ) hash(s) \sum_{i0}^{n-1} s[i] \times p^{n-i-1} \pmod{M}hash(s)i0∑n−1​s[i]×pn−i−1(modM)前缀哈希数组一般使用前缀和存储每个前缀的哈希值这样的话每次就能快速求出子串的哈希了。// 处理前缀哈希数组以及 p 的 i 次⽅数组voidinit_hash(){f[0]0;p[0]1;for(inti1;ilen;i){f[i]f[i-1]*Ps[i];p[i]p[i-1]*P;}}// 快速求得任意区间的哈希值ULLget_hash(intl,intr){returnf[r]-f[l-1]*p[r-l1];}将f[i]映射成p进制数则f[i] f[i - 1] * P s[i];若要求出中间某一段的哈希值将目标字符串、f[r]、f[l-1]表示出来找出他们之间的关系表示如下例子P3370 【模板】字符串哈希5.Trie树Trie 树又叫字典树或前缀树是⼀种能够快速插入和查询字符串的数据结构。它利用字符串的公共前缀将字符串组织成⼀棵树形结构。我们可以把字典树想象成⼀棵多叉树每一条边代表⼀个字符从根节点到某个节点的路径就代表了一个字符串。例如要存储 “abc” 、 “abd” 、 “acde” 以及 “cd” 时构建的字典树如下字典树的作用查询某个单词是否出现过并且出现几次查询有多少个单词是以某个字符串为前缀查询所有以某个前缀开头的单词这个作用可以用到输入法中输入拼音的时候可以提示可能的单词字典树的实现实现一个能够查询单词出现次数以及查询有多少个单词是以某个字符串为前缀的字典树默认全是小写字母。// 字典树 经过这个节点的字符串inttr[N][62],p[N];// 新插入节点的编号intidx;intt,n,q;// 查询是哪个字符intget_num(charch){if(chachz)returnch-a;elseif(chAchZ)returnch-A26;elsereturnch-052;}// 插入字典树voidinsert(strings){intcur0;// 从根结点开始p[cur];// 这个格⼦经过⼀次for(autoch:s){intpathget_num(ch);if(tr[cur][path]0)tr[cur][path]idx;// 迭代到下一个路径curtr[cur][path];p[cur];}e[cur];}// 查询特定前缀字符串个数intfind_pre(strings){intcur0;for(autoch:s){intpathget_num(ch);if(tr[cur][path]0)return0;curtr[cur][path];}// 查询从这个格子经过的所有字符串returnp[cur];}// 查询字符串出现次数intfind(strings){intcur0;for(autoch:s){intpathch-a;if(tree[cur][path]0)return0;curtree[cur][path];}returne[cur];}例子P8306 【模板】字典树