数据结构经典例题选讲.ppt

数据结构经典例题选讲数据结构经典例题选讲 Classical Problems on Data StructureClassical Problems on Data Structure 廖洪舒 合并果子 lN种果子(N op; stack num; strcat(S, “#“); op.push(#); bool finished = false; char *p = S; while (!finished) if (*p = | *p = t) p+; else if (*p = A else if (*p = ) else if (*p = # else char opt = op.top(); op.pop(); int b = num.top(); num.pop(); int a = num.top(); num.pop(); switch (opt) case +: num.push(a + b); break; case -: num.push(a - b); break; case *: num.push(a * b); break; case /: num.push(a / b); break; Largest Rectangle in a Histogram（ POJ2559） l给定一串长度为n(n = hi) li = lli - 1; for (i = n; i = 1; i-) while (hri + 1 = hi) ri = rri + 1; Largest Rectangle in a Histogram l将高度从高到低排序，用并查集维护当前集合的 宽度（节点个数），取max(当前高度 * 宽度)为 答案。复杂度为O(nlogn + na(n) Largest Rectangle in a Histogram l栈扫描（单调栈？），复杂度仅为O（n） l1 1 3 4 1 6 6 l1 7 4 4 7 7 7 Largest Submatrix of All 1s(POJ3494) Largest Submatrix of All 1s l预处理Hij表示(i, j)元素能向上延伸的最大高度 l枚举行，可以转化成前面的问题，复杂度为O(nm) l如果是要求在三维01长方体里的最大全1长方体呢 ？ Artificial Lake (POJ3658) WATER WATER OVERFLOWS | | * | * * | * * * * V * * V * * * * * * * * * * * * : * * * * * * : * * * * * * * * * * * * * * * * * * * * After 4 mins After 26 mins After 50 mins Lvl 1 submerged Lvl 3 submerged Lvl 2 submerged lN个平台(N=106）每个宽度Wi(Wi = 1000), 高 度Hi(Hi = 106)，每分钟往最低处注入一单位水，求 每个平台积水一个单位高度的时间。 Junk-Mail Filter (HDOJ 2473) 2008 Asia Regional Hangzhou lN封垃圾邮件样本，M次操作 (N = 105, M =106)，每次操 作为以下之一： lM X Y 表示垃圾邮件X和Y的样本特征一样。 lS X表示垃圾邮件X的样本特征识别有误，需要移除X的所有关系。 l最后询问有多少种不同的垃圾邮件特征？ 5 6 M 0 1 M 1 2 M 1 3 S 1 M 1 2 S 3 Sample Output : 3 Parity game (POJ1733) l 你的朋友写下一个由0和1组成的字符串，并告诉你一些信息 ，即某个连续的子串中1的个数是奇数还是偶数。 l你的目标是找到尽量小的i，使得前i+1条不可能同时满足。 l例如，序列长度为10，信息条数为5，5条信息分别为 1 2 even，3 4 odd，5 6 even，1 6 even，7 10 odd l正确答案是3，因为存在序列(0,0,1,0,1,1)满足前3条信息， 但是不存在满足前4条的序列。 Parity game l 令sumi为此01序列 前i个元素之和 l区间a, b中1的个数等价于sumb suma - 1。 l由sumi的奇偶性可以恢复出整个序列。 a b even 等价于 sumb, suma - 1同奇偶 a b odd 等价于 sumb, suma - 1奇偶性相反 l开始每个 i 自成一集合，di表示节点i与findSet(i)的奇偶关 系。di = 0表示奇偶性相同，di = 1表示奇偶性相反。 l对于每次操作，若a-1, b位于同一集合，则奇偶关系已确定， 需判断是否矛盾；否则合并两集合。 l那在合并集合和路径压缩时怎么来维护d数组呢？ Parity game bool unionSet(int x, int y, int nd) int fx = findSet(x)； int fy = findSet(y); if (fx = fy) if (dx dy) != nd) return true; else return false; else setfy = fx; dfy = (dx dy nd); return false; dfy fy y x fx dy nd dx f y x dy nd dx Parity game int findSet(int x) if (x = setx) return x;