算法分析與設(shè)計(jì)：習(xí)題選講第七章

1、第七章1426 電話號(hào)碼前綴檢索1310 二叉查找樹(shù)，前序中序后序遍歷1210 二叉樹(shù) ，知道前序、后序求可能的方法數(shù)1090 最小生成樹(shù)1156 二叉樹(shù)的前序遍歷1252 字符串劃分前后綴1155 判斷兩個(gè)點(diǎn)是否連通，并查集1132 ROUTES 用括號(hào)序列表示樹(shù)，求兩節(jié)點(diǎn)最近公共祖先1306 排序，可用堆排序1083 最小生成樹(shù)1426 電話號(hào)碼前綴檢索給出N個(gè)電話號(hào)碼（N = 10000）,每個(gè)電話號(hào)碼的長(zhǎng)度不大于10，當(dāng)存在一個(gè)電話號(hào)碼是另外一個(gè)電話號(hào)碼的前綴時(shí)，則會(huì)發(fā)生沖突。如果不存在沖突輸出YES，否則輸出NO解題思路1. 把n個(gè)電話號(hào)碼放進(jìn)一個(gè)set內(nèi)2. 枚舉每個(gè)電話號(hào)碼的前綴

2、，查詢是否存在于set里int n;string c11000;set ss;bool isConsistent()ss.clear();for (int i = 0; i n; i+) ss.insert(ci);for (int i = 0; i n; i+) string st = ;for (int j = 0; j ci.size() - 1; j+) st += cij;if (ss.count(st) return false;return true;1310 二叉查找樹(shù)給出N個(gè)數(shù)，按照順序建立一棵二叉查找樹(shù)，然后輸出該樹(shù)的前序遍歷，中序遍歷，后序遍歷。struct Node i

3、nt val;int left, right;Node(int val = 0):val(val), left(0),right(0) ; p300000;void Add(int root, int val) while (true) if (proot.val val) if (proot.right) root = proot.right; else proot.right = +tot； ptot = Node(val); return; else if (proot.left) root = proot.left; else proot.left = +tot; ptot = Nod

4、e(val); return; inline void Preorder(int root)if (!root) return;printf( %d, proot.val);Preorder(proot.left);Preorder(proot.right);inline void Inorder(int root)if (!root) return;Inorder(proot.left);printf( %d, proot.val);Inorder(proot.right);inline void Postorder(int root)if (!root) return;Postorder(

5、proot.left);Postorder(proot.right);printf( %d, proot.val);1210 二叉樹(shù)給出一棵二叉樹(shù)前序遍歷和后序遍歷的順序，要求出總共有多少棵不同形態(tài)的二叉樹(shù)滿足這樣的遍歷順序。解題思路1. 前序遍歷第一個(gè)元素是根，后序遍歷最后一個(gè)元素是根 2. 前序遍歷第二個(gè)元素是某子樹(shù)的根，但左右不確定 3. 在后序遍歷中找到前序遍歷的第二個(gè)元素，那么以這個(gè)元素為基準(zhǔn)，可以劃分新的左右子樹(shù) 4. 當(dāng)前序遍歷的第二個(gè)元素出現(xiàn)在后序遍歷的倒數(shù)第二位，以后序遍歷倒數(shù)第三位起向左數(shù)都是子樹(shù)的元素，但是左右不確定，因此有2種情況 long long calc(stri

6、ng pre, string post) long long ans = 1;int len=pre.size();for(int i= 0; i len - 1; i+) int current = len - 1;while(prei != postcurrent) current-;if(current & prei+1 = postcurrent - 1) ans *= 2;return ans;1090 最小生成樹(shù)題目大意：給出N=500個(gè)節(jié)點(diǎn)的無(wú)向圖，每?jī)蓚€(gè)點(diǎn)之間都有一條無(wú)向邊。問(wèn)該無(wú)向圖的最小生成樹(shù)中，最長(zhǎng)的一條邊的長(zhǎng)度。解題思路求最小生成樹(shù)的算法中，有Prim算法和kruska

7、l算法。Prim算法復(fù)雜度N2（N為點(diǎn)數(shù)）, Kruskal算法MlogM（M為邊數(shù)） 因此，對(duì)于稠密圖而言，Prim算法的復(fù)雜度更高效率。int solve()for (int i = 0; i n; i+) ui = false, disti = e0i;int ans = 0, p;for (int i = 0; i n; i+) p = -1; for (int j = 0; j distj) p = j; up = true; ans = max(ans, distp); for (int j = 0; j n; j+) if (uj | distj = epj) continue;

8、 distj = epj; return ans;1156 二叉樹(shù)的前序遍歷給定一棵N個(gè)節(jié)點(diǎn)的二叉樹(shù)，輸出其前序遍歷的順序解題思路：1.按照題目要求把二叉樹(shù)讀入2.以前序遍歷順序輸出（可參考1310）void Read_Tree()memset(is_root, 0, sizeof(is_root);char c;int l, r, m; for (int i = 0; i m c l r; is_rootm = !is_rootm; is_rootl = !is_rootl; is_rootr = !is_rootr; pm.Left = l; pm.Right = r; pm.ch = c

9、;for (int i = 1; i = 1000; i+) if (is_rooti) root = i;void Preorder(int root)if (!root) return;cout proot.ch;Preorder(proot.Left);Preorder(proot.Right);1252 字符串劃分前后綴給一個(gè)單詞word將一個(gè)前綴換成解釋1252 字符串劃分前后綴將一個(gè)后綴換成解釋1252 字符串劃分前后綴單詞的后綴與單詞更緊密例如：unvaporizenot vaporizenot change into vapor 解題思路先處理前綴strstr函數(shù)判斷單詞是否有

10、前綴去掉前綴遞歸處理后綴反轉(zhuǎn)字符串strstr函數(shù)判斷單詞是否有后綴的反轉(zhuǎn)去掉后綴反轉(zhuǎn)字符scanf(%s,r);if(strstr(r,anti)=r) printf(against ); suffixe(r+4); puts();else if(strstr(r,re)=r) suffixe(r+2); printf( againn);.else suffixe(r); puts();int n=strlen(r);reverse(r,r+n);if(strstr(r,re)=r) reverse(r,r+n); rn-2=0; printf(one who %ss,r);else if(

11、strstr(r,gni)=r) reverse(r,r+n); rn-3=0; printf(to actively %s,r);else reverse(r,r+n); printf(%s,r);1155 判斷兩個(gè)點(diǎn)是否連通，并查集一個(gè)有向圖有N個(gè)點(diǎn)(=200)問(wèn)能否從點(diǎn)0到點(diǎn)N-1解題思路DFSBFS用floyed算法求出任意兩點(diǎn)是否可達(dá)n=200最后判斷0到n-1是否可達(dá)#define rep(i,n) for(i=0;in;i+)#define PB push_backconst int oo=0 x3fffffff;rep(i,n) rep(j,n) rij=oo; rii=0;r

12、ep(i,m) scanf(%d%d,&a,&b); rab=0;rep(b,n)rep(a,n)rep(c,n) rac=min(rac,rab+rbc);1132 ROUTES 用括號(hào)序列表示樹(shù)，求兩節(jié)點(diǎn)最近公共祖先給出一棵樹(shù)求從一個(gè)葉節(jié)點(diǎn)到另一個(gè)葉節(jié)點(diǎn)的路徑樹(shù)的表達(dá)式：T(B(FHM(RJK)WD(L)E)T(B(FHM(RJK)WD(L)E)解題思路用stack處理樹(shù)表達(dá)式計(jì)算出每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)求出從開(kāi)始節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑A求出從結(jié)束節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑B刪除AB路徑末尾相同的元素順序輸出路徑A倒序輸出路徑Brep(i,27) fi=0;stack S; S.push(0);for(i

13、=0;rsi;i+)if(rsi=) S.pop();else if(rsi!=) frsi-A+1=S.top(); if(rsi+1=() S.push(rsi-A+1);puts(rs);while(gets(rs)!=0 & rs0) sscanf(rs,%s%s,s1,s2); An=0; for(x=s10-A+1;x;x=fx) AAn+=x; Bn=0; for(x=s20-A+1;x;x=fx) BBn+=x; while(An & Bn & AAn-1=BBn-1) An-; Bn-; rep(i,An) if(i) printf(-); putchar(Ai+A-1);

14、for(i=Bn;i=0;i-) printf(-%c,Bi+A-1); puts();1306 排序，可用堆排序給一個(gè)數(shù)組從小到大排序每隔m個(gè)位置輸出數(shù)組里的元素解題思路堆排序make_heap(a,a+n,cmp);a0;an+=key; push_heap(a,a+n,cmp);pop_heap(a,a+n,cmp);用sort排序，直接輸出即可rep(i,n) scanf(%d,&ri);sort(r,r+n);for(i=0;in;i+=m) if(i) putchar( ); printf(%d,ri);puts();1083 最小生成樹(shù)一個(gè)無(wú)向圖求最小生成樹(shù)解題思路kruskal算法按邊的長(zhǎng)度排序從小到大遍歷邊(a,b)用并查集判斷ab兩點(diǎn)是否屬于聯(lián)通集合如果ab不聯(lián)通合并ab所在的集合答案累加邊(a,b)int F(int x) if(x=fx) return x; return fx=F(fx);bool cmp(int a,int b) return CaCb;rep(i,m) scanf(%d%d%d,&Ai,&Bi,&Ci); idi=i;sort(id,id+m,cmp);ans=0;rep(i,m) a=Aidi; b