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

数据结构经典例题选讲 Classical Problems on Data Structure,廖洪舒,让爱延长 幸福能run多久? 有时候一分钟就够！,合并果子,N种果子(N=10000)，每种果子个数为Ai (Ai = 20000)。每次可合并任意两堆果子，消耗体力为两堆果子的数量之和，求将果子合并为一堆所需的最小体力耗费值。,合并果子,经典的Huffman树问题 朴素的做法O(n2) 利用二叉堆可以优化到O(nlogn) 此题，利用基数排序和两个队列，复杂度可降到O(n) 经典问题：石子归并、环形石子归并,Ugly Numbers（POJ1338）,Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, . shows the first 10 ugly numbers. By convention, 1 is included. Given the integer n,write a program to find and print the nth ugly number.,Ugly Numbers,初始：把1放入堆中 每次从堆中取出一个最小元素k，把2k, 3k, 5k放入堆中 取出的第n个元素就是第n大的丑数 每取出一个数，插入3个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn) 有没有复杂度更低的算法呢？,Ugly Numbers,任何丑数乘以2，3，5之后还是丑的。 同样，维护一个线性表及三个指针，可以将复杂度降到O(n) 类似题目有 POJ2247 Humble Numbers POJ2545 Hamming Problem,Lazy Math Instructor,判断两个只含“+”，“-”，“*”及括号的表达式是否等价。 如 (a+b-c)*2 等价于 (a+a)+(b*2)-(3*c)+c (a-b)*(a-b) 不等价于 (a*a)-(2*a*b)-(b*b),Lazy Math Instructor,转化为表达式求值问题 算法（exp_parsing.htm）： The shunting yard algorithm The classic solution Precedence climbing,The shunting yard algorithm,维护一个操作数栈 (operand stack) 维护一个运算符栈 (operator stack) 核心思想：维护运算符栈，使得其运算符优先级总是从低到高（从栈底到栈顶）。 从左往右扫描表达式，遇到操作数则直接压到操作数栈；遇到运算符，先进行运算符栈顶优先级更高的运算，再将当前运算符压栈。 每次运算会从运算符栈取出一个运算符，从操作数栈取出相应个数的操作数，进行运算，将结果压回操作数栈。,stack op; stack num; strcat(S, “#“); op.push(#); bool finished = false; char *p = S; while (!finished) if (*p = | *p = t) p+; else if (*p = A ,Largest Rectangle in a Histogram（POJ2559）,给定一串长度为n(n = 100000)的序列hi(hi = 109)，可以画出其直方图，问其中面积最大的矩形是多大？ 如 n = 7, 序列为2 1 4 5 1 3 3,Largest Rectangle in a Histogram,朴素的做法，复杂度最坏为O（n2） 如何改进？ 递推，有点类似并查集路径压缩的思想。,hn + 1 = h0 = -1; for (i = 1; i = hi) li = lli - 1; for (i = n; i = 1; i-) while (hri + 1 = hi) ri = rri + 1;,Largest Rectangle in a Histogram,将高度从高到低排序，用并查集维护当前集合的宽度（节点个数），取max(当前高度 * 宽度)为答案。复杂度为O(nlogn + na(n),Largest Rectangle in a Histogram,栈扫描（单调栈？），复杂度仅为O（n） 1 1 3 4 1 6 6 1 7 4 4 7 7 7,Largest Submatrix of All 1s(POJ3494),Given a m-by-n (0,1)-matrix, of all its submatrices of all 1s which is the largest? By largest we mean that the submatrix has the most elements. (1 = n, m = 2000) 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1,Largest Submatrix of All 1s,预处理Hij表示(i, j)元素能向上延伸的最大高度 枚举行，可以转化成前面的问题，复杂度为O(nm) 如果是要求在三维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,N个平台(N=106）每个宽度Wi(Wi = 1000), 高度Hi(Hi = 106)，每分钟往最低处注入一单位水，求每个平台积水一个单位高度的时间。,Junk-Mail Filter (HDOJ 2473) 2008 Asia Regional Hangzhou,N封垃圾邮件样本，M次操作 (N = 105, M =106)，每次操作为以下之一： M X Y 表示垃圾邮件X和Y的样本特征一样。 S X表示垃圾邮件X的样本特征识别有误，需要移除X的所有关系。 最后询问有多少种不同的垃圾邮件特征？ 5 6 M 0 1 M 1 2 M 1 3 S 1 M 1 2 S 3,Sample Output : 3,Parity game (POJ1733),你的朋友写下一个由0和1组成的字符串，并告诉你一些信息，即某个连续的子串中1的个数是奇数还是偶数。 你的目标是找到尽量小的i，使得前i+1条不可能同时满足。 例如，序列长度为10，信息条数为5，5条信息分别为 1 2 even，3 4 odd，5 6 even，1 6 even，7 10 odd 正确答案是3，因为存在序列(0,0,1,0,1,1)满足前3条信息，但是不存在满足前4条的序列。,Parity game,令sumi为此01序列 前i个元素之和 区间a, b中1的个数等价于sumb suma - 1。 由sumi的奇偶性可以恢复出整个序列。 a b even 等价于 sumb, suma - 1同奇偶 a b odd 等价于 sumb, suma - 1奇偶性相反 开始每个 i 自成一集合，di表示节点i与findSet(i)的奇偶关系。di = 0表示奇偶性相同，di = 1表示奇偶性相反。 对于每次操作，若a-1, b位于同一集合，则奇偶关系已确定，需判断是否矛盾；否则合并两集合。 那在合并集合和路径压缩时怎么来维护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 = (