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

数据结构经典例题选讲

ClassicalProblemsonDataStructure廖洪舒让爱延长…幸福能run多久?有时候一分钟就够！合并果子N种果子(N=10000)，每种果子个数为Ai(Ai=20000)。每次可合并任意两堆果子，消耗体力为两堆果子的数量之和，求将果子合并为一堆所需的最小体力耗费值。经典的Huffman树问题朴素的做法O(n^2)利用二叉堆可以优化到O(nlogn)此题，利用基数排序和两个队列，复杂度可降到O(n)经典问题：石子归并、环形石子归并合并果子UglyNumbers（POJ1338）Uglynumbersarenumberswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,...showsthefirst10uglynumbers.Byconvention,1isincluded.Giventheintegern,writeaprogramtofindandprintthenthuglynumber.初始：把1放入堆中有没有复杂度更低的算法呢？每次从堆中取出一个最小元素k，把2k,3k,5k放入堆中每取出一个数，插入3个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)取出的第n个元素就是第n大的丑数UglyNumbers任何丑数乘以2，3，5之后还是丑的。同样，维护一个线性表及三个指针，可以将复杂度降到O(n)类似题目有POJ2247HumbleNumbersPOJ2545HammingProblemUglyNumbersLazyMathInstructor判断两个只含“+”，“-”，“*”及括号的表达式是否等价。如(a+b-c)*2等价于(a+a)+(b*2)-(3*c)+c(a-b)*(a-b)不等价于(a*a)-(2*a*b)-(b*b)01030204LazyMathInstructor转化为表达式求值问题算法（exp_parsing.htm）：TheshuntingyardalgorithmTheclassicsolutionPrecedenceclimbingTheshuntingyardalgorithm维护一个操作数栈(operandstack)维护一个运算符栈(operatorstack)核心思想：维护运算符栈，使得其运算符优先级总是从低到高（从栈底到栈顶）。从左往右扫描表达式，遇到操作数则直接压到操作数栈；遇到运算符，先进行运算符栈顶优先级更高的运算，再将当前运算符压栈。每次运算会从运算符栈取出一个运算符，从操作数栈取出相应个数的操作数，进行运算，将结果压回操作数栈。stackcharop;stackdoublenum;strcat(S,#);op.push(#);boolfinished=false;char*p=S;while(!finished){ if(*p==||*p==\t)p++; elseif((*p=A*p=Z)||...) num.push(toVal(*(p++))); elseif(*p==(||getP(*p)getP(op.top())) op.push(*(p++)); elseif(*p==)op.top()==()p++,op.pop(); elseif(*p==#op.top()==#)finished=true; else { charopt=op.top();op.pop(); intb=num.top();num.pop(); inta=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; } }}LargestRectangleinaHistogram（POJ2559）给定一串长度为n(n=100000)的序列hi(hi=10^9)，可以画出其直方图，问其中面