精美ppt课件poj数据结构典型例题讲解课件

精美ppt课件poj数据结构典型例题讲解课件

ID:21271838

大小:609.00 KB

页数:23页

时间:2018-10-20

精美ppt课件poj数据结构典型例题讲解课件_第1页
精美ppt课件poj数据结构典型例题讲解课件_第2页
精美ppt课件poj数据结构典型例题讲解课件_第3页
精美ppt课件poj数据结构典型例题讲解课件_第4页
精美ppt课件poj数据结构典型例题讲解课件_第5页
资源描述:

《精美ppt课件poj数据结构典型例题讲解课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

2、berswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,...showsthefirst10uglynumbers.Byconvention,1isincluded.Giventheintegern,writeaprogramtofindandprintthen'thuglynumber.UglyNumbers初始:把1放入堆中每次从堆中取出一个最小元素k,把2k,3k,5k放入堆中取出的第n个元素就是第n大的丑数每取出一个数,插入3个数,因此任何堆里的元素是O(n)的,时

3、间复杂度为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*a)-(2*a*b)-(b*b)LazyMathInstructor转化为表达式求值问题算法(exp_pa

4、rsing.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++)));elseif(*p=='('

10、

11、getP(*p)>getP(op.top()))op.push(*(p++));elseif(*p==')'&&op.top()=='(')p++,op.

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

13、stogram(POJ2559)给定一串长度为n(n<=100000)的序列hi(hi<=10^9),可以画出其直方图,问其中面积最大的矩形是多大?如n=7,序列为2145133LargestRectangleinaHistogram朴素的做法,复杂度最坏为O(n^2)如何改进?递推,有点类似并查集路径压缩的思想。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(

14、h[r[i]+1]>=h[i])r[i]=r[r[i]+1];LargestRectangle

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。