数据结构例题选讲.ppt

1,数据结构例题选讲,L7we,二叉堆,二叉堆是一种完全二叉树，树的每个节点有一个权值，对于树的每棵子树都有：其根节点的权值不差于该子树上任何点的权值 功能：O(1)得到堆中的最优值，log(n)的维护 由于二叉堆是完全二叉树，可以像线段树一样用一维数组存储，当数组从下标1开始存储时，对于每个点（下标为i），其父亲结点的下标为i/2，左儿子结点下标为i*2，右儿子结点下标为i*2+1 基本操作：插入，删除,二叉堆,插入： void push(int x) heap+heap_size=x; int cur=heap_size; int father=cur/2; while(father=1) if(cmp(heapcur,heapfather) swap(heapcur,heapfather); cur=father; father=cur/2; else break; ,二叉堆,删除： int pop() int ans=heap1; heap1=heapheap_size-; int cur=1; int child=cur*2; while(child=heap_size) if(child+1=heap_size ,树状数组应用,树状数组功能： log(n)复杂度解决区间问题 树状数组中的每个点管辖一段区间，通过某种规则可以方便的把1n这种区间分成几块，每一块刚好是一个点的管辖区间，于是统计就方便了 每个点记录管辖区域内的和，可以log(n)复杂度求得区间和 每个点记录管辖区域内最值，可以log(n)复杂度求得区间最值 每个点记录 值落在管辖区域内 的数的个数，可以log(n)复杂度求得值在某个区间内的数的个数 等等,Enemy is week,给定n个数a1、a2、a3an，求满足i,j,k(iajak成立的i,j,k的三元组个数 (n=106,ai=106) 枚举i,j,k，复杂度n3 枚举j，对于每个j寻找满足的i,k，复杂度n2,Enemy is week,需要至少nlog(n)算法 枚举j，需要优化寻找i,k的办法 树状数组每个点记录有多少个数的值落在其管辖区域内 从前向后扫一遍数组，维护树状数组，对每个j用log(n)复杂度计算满足aiaj的i 从后向前扫一遍数组，维护树状数组，对每个j用log(n)复杂度计算满足akaj的k,Cows,给定n个二元组(a1,b1)，(a2,b2)(an,bn)，对于每个二元组(ai,bi)计算满足 aj=bi且两不等式不同时取等号 的二元组(aj,bj)的个数 把每个二元组映射为二维空间里的点，a为x坐标，b为y坐标，即是对每个点求位于其左上方，包含正上方、正左方，但不包含重叠点的 点的个数 把点按y从大到小排序，y相等时按x从小到大排序，树状数组维护x值落在管辖区域内的点的个数 注意处理重点情况,字典树,给定一些单词 apple，banana，orange，pear，strawberry 给出一些询问，每个询问为一个单词 pear，people，orange 对于每个询问，回答其是否在给定的单词中出现过,字典树,枚举复杂度n*m*L，n为给定单词数，m为询问数，L为平均单词长度，一般不可接受 假如把单词换成数字，即给定一些数，询问查询某个数是否出现过，假如数的范围不大，直接开数组记录即可，假如数比较大，需要加哈希 重点是如何记录字符串使之可以方便存取,字典树,字典树是一颗t元有序树 t元：t为字符串中可能出现的字符种类数。比如，要用字典树表示纯由小写字母组成的字符串，t为26 有序树：结点的每个儿子互不等价。比如二叉树，左儿子与右儿子有区别 每个结点代表一个字符串，其儿子所代表的字符串为该点代表的字符串后面加一个字符，加的字符与它是父亲的第几个儿子有关,字典树 t=3,字典树,如何表示一棵树 堆&线段树，由于是完全二叉树，故可以用一维数组表示 假如用一维数组表示字典树，需要空间复杂度量级在tL，一般不可取 动态分配内存，需要链表基础,字典树,typedef struct N int flag; /记录该结点表示的字符串是否存在 struct N *next26; Node; Node *Create() Node *p=(Node *)malloc(sizeof(Node); for(int i=0;inexti=NULL; p-flag=0; return 0; ,字典树,void Insert(char s) int L=strlen(s); Node *cur=root; for(int i=0;inextt=NULL) cur=cur-nextt=Create(); else cur=cur-nextt; cur-flag=1; ,字典树,int query(char s) int L=strlen(s); Node *cur=root; for(int i=0;inextt=NULL) return 0; else cur=cur-nextt; return cur-flag; ,字典树,时间复杂度：建树n*L，查询m*L,非常优越 缺点是空间耗费很大 空间不够时，这题还有另一种解法，把给定的单词按一定次序（如字典序）排序，对每个询问二分查找求解。,God Wus new game,对询问字符串建字典树，然后在矩阵中枚举起点看产生的字符串是否能在字典树中找到,lazy math instructor,给定两个表达式，判断两个表达式是否等价 如a+b-c与a-c+b等价，表达式中可能出现+,-,*,(,) 难点是如何求解表达式的值，如，怎么求7+2-3*2,lazy math instructor,假如只有+,- 维护两个栈，一个栈中存放数，一个栈中存放操作符 约定一种操作 cal:取出操作符栈栈顶的操作符，根据其意义从数字栈中取出两个数字进行操作，操作结果进入数字栈 表达式遇到数字时将数字入栈，遇到操作符时，判断操作符栈是否为空，如果不为空则执行cal操作使之为空，之后将当前操作符入操作符栈 最后假如操作符栈不为空，执行cal操作使之为空,lazy math instructor,关键是要保持操作符栈中操作符优先级的严格单调递增 每次遇到操作符时，执行cal直至操作符栈顶元素的优先级低于当前操作符,Boring God KuFeng,给定一些矩形海报及其在窗户上的张贴位置（海报都是正着贴，每条边要么是水平的要么是竖直的），每个矩形海报都有一个矩形小洞，求窗户被海报遮挡的面积之和（海报可能重叠） 海报重叠是求解中最麻烦的地方 首先考虑这样一个问题，假如矩形海报都完整，如何求解问题,Boring God KuFeng,最原始思路：穷举二维空间的每一个格子点，对于每个点判断其是否被覆盖过 改进：枚举每一行的时候，经常会出现相邻两行的统计结果一样，比如矩形(0,0)-(10,10)，枚举格子点的y值会发现对于每个y值（0=y10）统计结果都为10。 进一步思考会发现，统计结果改变的转折点是每个矩形的上