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

数据结构经典例题选讲Classical￿Problems￿on￿Data￿Structure廖洪舒合并果子lN种果子(N<=10000)，每种果子个数为Ai￿(Ai￿<=￿20000)每次可合并任意两堆果子，消耗体力为两堆果子的数量之和，求将果子合并为一堆所需的最小体力耗费值合并果子l经典的Huffman树问题l朴素的做法O(n^2)l利用二叉堆可以优化到O(nlogn)l此题，利用基数排序和两个队列，复杂度可降到O(n)l经典问题：石子归并、环形石子归并Ugly Numbers（（POJ1338））lUgly￿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.￿lGiven￿the￿integer￿n,write￿a￿program￿to￿find￿and￿print￿the￿n'th￿ugly￿number.Ugly Numbersl初始：把1放入堆中l每次从堆中取出一个最小元素k，把2k,￿3k,￿5k放入堆中l取出的第n个元素就是第n大的丑数l每取出一个数，插入3个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)l有没有复杂度更低的算法呢？Ugly Numbersl任何丑数乘以2，3，5之后还是丑的。

l同样，维护一个线性表及三个指针，可以将复杂度降到O(n)l类似题目有￿￿POJ2247￿Humble￿Numbers￿￿POJ2545￿Hamming￿ProblemLazy Math Instructorl判断两个只含“+”，“-”，“*”及括号的表达式是否等价l如l(a+b-c)*2￿等价于￿(a+a)+(b*2)-(3*c)+cl(a-b)*(a-b)￿不等价于￿(a*a)-(2*a*b)-(b*b)Lazy Math Instructorl转化为表达式求值问题l算法（exp_parsing.htm）：•The￿shunting￿yard￿algorithm•The￿classic￿solution•Precedence￿climbingThe shunting yard algorithml维护一个操作数栈￿(operand￿stack)￿￿￿维护一个运算符栈￿(operator￿stack)l核心思想：维护运算符栈，使得其运算符优先级总是从低到高（从栈底到栈顶）l从左往右扫描表达式，遇到操作数则直接压到操作数栈；遇到运算符，先进行运算符栈顶优先级更高的运算，再将当前运算符压栈。

l每次运算会从运算符栈取出一个运算符，从操作数栈取出相应个数的操作数，进行运算，将结果压回操作数栈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' && *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））l给定一串长度为n(n￿<=￿100000)的序列hi(hi￿<=￿10^9)，可以画出其直方图，问其中面积最大的矩形是多大？l如￿n￿=￿7,￿序列为2￿1￿4￿5￿1￿3￿3Largest Rectangle in a Histograml朴素的做法，复杂度最坏为O（n^2）l如何改进？l递推，有点类似并查集路径压缩的思想。

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];Largest Rectangle in a Histograml将高度从高到低排序，用并查集维护当前集合的宽度（节点个数），取max(当前高度￿*￿宽度)为答案复杂度为O(nlogn￿+￿na(n))Largest Rectangle in a Histograml栈扫描（单调栈？），复杂度仅为O（n）l1￿1￿3￿4￿1￿6￿6l1￿7￿4￿4￿7￿7￿7Largest Submatrix of All 1's(POJ3494)lGiven￿a￿m-by-n￿(0,1)-matrix,￿of￿all￿its￿submatrices￿of￿all￿1’s￿which￿is￿the￿largest?￿By￿largest￿we￿mean￿that￿the￿submatrix￿has￿the￿most￿elements.￿(1￿<=￿n,￿m￿<=￿2000)0 1 0 00 1 1 00 1 1 01 0 0 1Largest Submatrix of All 1'sl预处理H[i][j]表示(i,￿j)元素能向上延伸的最大高度l枚举行，可以转化成前面的问题，复杂度为O(nm)l如果是要求在三维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 submergedlN个平台(N<=10^6）每个宽度Wi(Wi￿<=￿1000),￿高度Hi(Hi￿<=￿10^6)，每分钟往最低处注入一单位水，求每个平台积水一个单位高度的时间。

Junk-Mail Filter (HDOJ 2473)2008 Asia Regional Hangzhou lN封垃圾邮件样本，M次操作￿(N￿<=￿10^5,￿M￿<=10^6)，每次操作为以下之一：lM￿X￿Y￿表示垃圾邮件X和Y的样本特征一样lS￿X表示垃圾邮件X的样本特征识别有误，需要移除X的所有关系l最后询问有多少种不同的垃圾邮件特征？•5￿6•M￿0￿1•M￿1￿2•M￿1￿3•S￿1•M￿1￿2•S￿3•Sample￿Output￿:￿3Parity game (POJ1733)l￿你的朋友写下一个由0和1组成的字符串，并告诉你一些信息，即某个连续的子串中1的个数是奇数还是偶数l你的目标是找到尽量小的i，使得前i+1条不可能同时满足l例如，序列长度为10，信息条数为5，5条信息分别为￿￿1￿2￿even，3￿4￿odd，5￿6￿even，1￿6￿even，7￿10￿oddl正确答案是3，因为存在序列(0,0,1,0,1,1)满足前3条信息，但是不存在满足前4条的序列Parity game l￿令sum[i]为此01序列￿前i个元素之和l区间[a,￿b]中1的个数等价于sum[b]￿–￿sum[a￿-￿1]。

l由sum[i]的奇偶性可以恢复出整个序列•a￿b￿even￿等价于￿sum[b],￿sum[a￿-￿1]同奇偶•a￿b￿odd￿等价于￿sum[b],￿sum[a￿-￿1]奇偶性相反l开始每个￿i￿自成一集合，d[i]表示节点i与findSet(i)的奇偶关系d[i]￿=￿0表示奇偶性相同，d[i]￿=￿1表示奇偶性相反l对于每次操作，若a-1,￿b位于同一集合，则奇偶关系已确定，需判断是否矛盾；否则合并两集合l那在合并集合和路径压缩时怎么来维护d数组呢？Parity gamebool unionSet(int x, int y, int nd){int fx = findSet(x)；int fy = findSet(y);if (fx == fy){if ((d[x] ^ d[y]) != nd)return true;elsereturn false;}else{set[fy] = fx;d[fy] = (d[x] ^ d[y] ^ nd);return false;}}d[fy]fyyx fxd[y]ndd[x] fyxd[y]ndd[x]Parity gameint findSet(int x){if (x == set[x]) return x;else{int fx = findSet(set[x]);d[x] = (d[x] ^ d[set[x]]);return set[x] = fx;}} set[x]d[x] xd[set[x]]fx新的新的d[x]l类似题目：POJ2827,￿2492，1984,￿1182,2912￿。