数据结构经典例题选讲

《数据结构经典例题选讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构经典例题选讲ClassicalProblemsonDataStructure廖洪舒让爱延长…幸福能run多久?有时候一分钟就够！合并果子N种果子(N<=10000)，每种果子个数为Ai(Ai<=20000)。每次可合并任意两堆果子，消耗体力为两堆果子的数量之和，求将果子合并为一堆所需的最小体力耗费值。合并果子经典的Huffman树问题朴素的做法O(n^2)利用二叉堆可以优化到O(nlogn)此题，利用基数排序和两个队列，复杂度可降到O(n)经典问题：石子归并、环形石子归并UglyNumbers（POJ1338

2、）Uglynumbersarenumberswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,...showsthefirst10uglynumbers.Byconvention,1isincluded.Giventheintegern,writeaprogramtofindandprintthen'thuglynumber.UglyNumbers初始：把1放入堆中每次从堆中取出一个最小元素k，把2k,3k,5k放入堆中取出的第n个元素就是

3、第n大的丑数每取出一个数，插入3个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)有没有复杂度更低的算法呢？UglyNumbers任何丑数乘以2，3，5之后还是丑的。同样，维护一个线性表及三个指针，可以将复杂度降到O(n)类似题目有POJ2247HumbleNumbersPOJ2545HammingProblemLazyMathInstructor判断两个只含“+”，“-”，“*”及括号的表达式是否等价。如(a+b-c)*2等价于(a+a)+(b*2)-(3*c)+c(a-b)*(a-b)不等价于(a

4、*a)-(2*a*b)-(b*b)LazyMathInstructor转化为表达式求值问题算法（exp_parsing.htm）：TheshuntingyardalgorithmTheclassicsolutionPrecedenceclimbingTheshuntingyardalgorithm维护一个操作数栈(operandstack)维护一个运算符栈(operatorstack)核心思想：维护运算符栈，使得其运算符优先级总是从低到高（从栈底到栈顶）。从左往右扫描表达式，遇到操作数则直接压到操作数栈；遇到运算符，

5、先进行运算符栈顶优先级更高的运算，再将当前运算符压栈。每次运算会从运算符栈取出一个运算符，从操作数栈取出相应个数的操作数，进行运算，将结果压回操作数栈。stackop;stacknum;strcat(S,"#");op.push('#');boolfinished=false;char*p=S;while(!finished){if(*p==''

6、

7、*p=='t')p++;elseif((*p>='A'&&*p<='Z')

8、

9、...)num.push(toVal(*(p++)));els

10、eif(*p=='('

11、

12、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;

13、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)，可以画出其直方图，问其中面积最大的矩形是多大？如n=7,序列为2145133LargestRectangleinaHistogram朴素的做法，复杂度最坏为O（n^2）如何改进？递推，有点类似并查集路径压

14、缩的思想。h[n+1]=h[0]=-1;for(i=1;i<=n;i++)l[i]=r[i]=i;for(i=1;i<=n;i++)while(h[l[i]-1]>=h[i])l[i]=l[l[i]-1];for(i=n;i>=1;i--)while(h[r[i]+1]>=h[i])r[i]=r[r[i]+1];LargestRectangle