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

数据结构经典例题选讲Classical Problems on Data Structure 廖洪舒 合并果子 N种果子(N=10000)，每种果子个数为Ai (Ai = 20000)。每次可合并任意两堆果子，消耗体力为两堆果子的数量之和，求将果子合并为一堆所需的最小体力耗费值。 合并果子 经典的Huffman树问题 朴素的做法O(n^2) 利用二叉堆可以优化到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) 核心思想：维护运算符栈，使得其运算符优先级总是从低到高（从栈底到栈顶）。 从左往右扫描表达式，遇到操作数则直接压到操作数栈；遇到运算符，先进行运算符栈顶优先级更高的运算，再将当前运算符压栈。 每次运算会从运算符栈取出一个运算符，从操作数栈取出相应个数的操作数，进行运算，将结果压回操作数栈。 stackchar op; stackdouble num; strcat(S, #); op.push(#); bool finished = false; char *p = S; while (!finished) { if (*p == || *p == \t) p++; else if ((*p = A *p = Z) || ...) num.push(toVal(*(p++))); else if (*p == ( || getP(*p) getP(op.top())) op.push(*(p++)); else if (*p == ) op.top() == () p++, op.pop(); else if (*p == # op.top() == #) finished = true; 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） 给定一串长度为n(n = 100000)的序列hi(hi = 10^9)，可以画出其直方图，问其中面积最大的矩形是多大？ 如 n = 7, 序列为2 1 4 5