写在前面
目录
一、栈
二、队列
三、链表与邻接表
四、Hash
五、字符串
六、Trie
七、二叉堆
题目完成进度
5/10
一、栈
栈是一种“先进后出”的线性数据结构。栈只有一端能够进出元素,我们一般称之为栈顶,另一端为栈底。添加或删除栈中元素时,我们只能将其插入到栈顶(进栈),或者把栈顶元素从栈中取出(出栈)。
先来两道例题——
CH128 Editor
CH130 火车进出栈问题
栈的一大用处是做算数表达式的计算,算数表达式通常有前缀、中缀、后缀三种表示方法。
1.中缀表达式:就是最常见的表达式,如:$3*(2-1)$
2.前缀表达式:又称波兰式,形如“$op\ A\ B$”,其中“op”是一个运算符,如:$*\ 3\ -\ 2\ 1$
3.后缀表达式:又称逆波兰式,形如“$A\ B\ op$”,如:$2\ 1\ -\ 3\ *$
前缀和后缀表达式的值的定义是,先递归求出$A,B$的值,二者再做$op$运算的结果。这两种表达式不需要括号,其运算方式是唯一确定的。对于计算机来说,最容易计算的是后缀表达式,可以使用栈$O(N)$求值。
接下来详细说一下三种表达式在计算机中的求值方法:
首先是最容易求值的后缀表达式
后缀表达式求值
1.建立一个用于存数的栈,逐个扫描该后缀表达式中的元素。
(1)如果遇到一个数,则把这个数入栈
(2)如果遇到运算符,就取出栈顶的两个数进行计算,把结果入栈
2.扫描完成后,栈中恰好剩下一个数,就是该后缀表达式的结果。
如果要用计算机计算中缀表达式的结果,最快的办法是把中缀表达式转化成后缀表达式,再使用上述方法求值,这个转化过程同样可以使用栈来$O(N)$地完成。
中缀表达式转后缀表达式
1.建立一个用于存运算符的栈,逐个扫描该中缀表达式中的元素。
(1)如果遇到一个数,输出该数
(2)如果遇到左括号,把左括号入栈
(3)如果遇到右括号,不断取出栈顶并输出,直到栈顶为左括号,然后把左括号出栈
(4)如果遇到运算符,只要栈顶符号的优先级不低于新符号,就不断取出栈顶并输出,最后把新符号进栈
2.依次取出并输出栈中的所有剩余符号,最终输出的一个序列就是一个与原中缀表达式等价的后缀表达式。
当然,我们也可以不转化成后缀表达式,而是使用递归法直接求解中缀表达式的值,时间复杂度为$O(N)$。
中缀表达式的递归法求值
目标:求解中缀表达式$S[1~N]$的值。
子问题:求解中缀表达式$S$的子区间表达式$S[L~R]$的值。
1.在$L~R$中考虑没有被任何括号包含的运算符:
(1)若存在加减号,选其中最后一个,分成左右两半递归,结果相加减,返回
(2)若存在乘除号,选其中最后一个,分成左右两半递归,结果相乘除,返回
2.若不存在没有被任何括号包含的运算符:
(1)若首尾字符是括号,递归求解$S[L+1~R-1]$,把结果返回
(2)否则,说明区间$S[L~R]$是一个数,直接返回数值
之前单独写过专题笔记,直接走链接吧,搬运一下例题——
poj2559 Largest Rectangle in a Histogram
借助单调性处理问题的思想在于及时排除不可能的选项,保持策略集合的高度有效性和秩序性,从而为我们作出决策提供更多的条件和可能方法。
go back
二、队列
队列是一种“先进先出”的线性数据结构。一般来讲,元素从右端进入队列(入队),从左端离开队列(出队)。于是我们称队列的左端为队头,右端为队尾。
元素进行多次入队、出队后,用于实现队列结构的数组的开头空间部分就会被严重浪费,所以我们经常将其优化为“循环队列”,也就是把队列看作一个首尾相接的环,只要队列中的元素个数在任意时刻都不超过环长,那么随着入队和出队操作的进行,存储元素的那一段位置就像沿着环不停地移动,重复利用空间。C++STL中的$queue$就是一个循环队列。
队列还有很多变体,如两端都能插入或取出元素的双端队列$deque$,等价于一个二叉堆的优先队列$priority_queue$,队列也是实现BFS的基本结构。
上例题——
poj2259 Team Queue
CH134 双端队列
先来一道例题——
CH135 最大子序和
单调队列算法因为每个元素至多入队一次、出队一次,所以整个算法的时间复杂度为$O(N)$。算法的思想也是在决策集合(队列)中及时排除一定不是最优解的选择,单调队列也是优化DP的一个重要手段。
go back
三、链表与邻接表
go back
四、Hash
$Hash$表又称为散列表,一般由$Hash$函数和链表共同实现。与离散化思想类似,当我们要对若干复杂信息进行统计时,可以用$Hash$函数把这些复杂信息映射到一个容易维护的值域内。因为值域变简单、范围变小,有可能造成两个不同的原始信息被$Hash$函数映射为相同的值,下面讲一讲如何处理这种冲突情况。
有一种被称为“开散列”的解决方案是,建立一个邻接表结构,以$Hash$函数的值域作为表头数组$head$,映射后的值相同的原始信息被分到同一类,构成一个链表接在对应的表头之后,链表的节点上可以保存原始信息和一些统计数据。
$Hash$表主要包括两个基本操作:
1.计算$Hash$函数的值
2.定位到对应链表中依次遍历、比较
无论是检查任意一个给定的原始信息在$Hash$表中是否存在,还是更新它在$Hash$表中的统计数据,都需要基于这两个基本操作进行。
当$Hash$函数设计得较好时,原始信息会被比较均匀地分配到各个表头之后,从而使每次查找、统计的时间降低到“原始信息总数除以表头数组长度”。若原始信息总数与表头数组长度都是$O(N)$级别且$Hash$函数分散均匀,几乎不产生冲突,那么每次查找、统计的期望复杂度为$O(1)$
举个栗子,我们要在一个长度为$N$的随机整数序列$A$中统计每个数出现了多少次。当数列$A$中的数都比较小时,我们可以直接用数组计数。当数列$A$中的值很大时,我们可以把$A$排序后扫描统计,也可以用$Hash$表来做。
设计$Hash$函数为$Hash(x)=(x\ mod\ p)+1$,其中$p$是一个大质数,但不超过$N$。显然,这个$Hash$函数把数列$A$分成$p$类,我们可以依次考虑数列中的每个数$A[i]$,定位到$head[Hash(a[i])]$这个表头所指向的链表。如果该链表中不包含$A[i]$,我们就在表头后插入一个新节点$A[i]$,并在该节点上记录$A[i]$出现了1次,否则我们找到已经存在的$A[i]$节点将其出现次数加1。因为整数序列$A[i]$是随机的,所以最终所有的$A[i]$会比较均匀地分布在各个表头之后,整个算法的时间复杂度可以近似达到$O(N)$。
例题——
poj3349 Snowflake Snow Snowflakes
字符串$Hash$函数可以把一个任意长度的字符串映射成一个非负整数,并且冲突概率几乎为0。
取一固定值$p$,把字符串看作$p$进制数,并分配一个大于零的数值,代表每种字符。取一固定值$M$,求出该$p$进制数对$M$的余数,作为该字符串的$Hash$值。
一般取$p=131$或$p=13331$,此时$Hash$值产生冲突的概率极低,只要$Hash$值相等,我们就可以认为原字符串是相等的。通常我们取$m=2^{64}$,即直接使用$unsigned\ long\ long$类型存储这个$Hash$值,在计算时不处理算数溢出问题,产生溢出时相当于自动对$2^{64}$取膜,这样可以避免低效的取膜($mod$)运算。同时注意如果用了$unsigned\ long\ long$就不要再加膜运算了!
已知字符串$S$的$Hash$值为$H(S)$,则在$S$后添加一个字符$c$构成的新字符串的$Hash$值为$H(S+c)=(H(S)*p+w[c])\mod M$,其中$w[c]$为代表字符$c$的数值。
已知字符串$S$的$Hash$值$H(S)$和字符串$S+T$的$Hash$值$H(S+T)$,则可求出字符串$T$的$Hash$值$H(T)=(H(S+T)-H(S)*p^{length(T)})mod\ M$。
通过这两种操作,我们可以用$O(N)$的时间预处理字符串所有前缀$Hash$值,并在$O(1)$的时间内查询其任意字串的$Hash$值。
例题——
兔子与兔子
poj3974 Palindrome
后缀数组
go back
五、字符串
go back
六、Trie
go back
七、二叉堆
go back
转载于:https://www.cnblogs.com/THWZF/p/11319450.html
相关资源:JAVA上百实例源码以及开源项目