[學(xué)習(xí)]算法分析與設(shè)計(jì)課件：習(xí)題選講第七章李承乾

1、第七章,李承乾498727460@qq.com,1426 電話號碼前綴檢索1310 二叉查找樹，前序中序后序遍歷1210 二叉樹 ，知道前序、后序求可能的方法數(shù)1090 最小生成樹1156 二叉樹的前序遍歷1252 字符串劃分前后綴1155 判斷兩個(gè)點(diǎn)是否連通，并查集1132 ROUTES 用括號序列表示樹，求兩節(jié)點(diǎn)最近公共祖先1306 排序，可用堆排序1083 最小生成樹,1426 電話號碼前綴檢索,給出N個(gè)電

2、話號碼（N <= 10000）,每個(gè)電話號碼的長度不大于10，當(dāng)存在一個(gè)電話號碼是另外一個(gè)電話號碼的前綴時(shí)，則會發(fā)生沖突。如果不存在沖突輸出YES，否則輸出NO,解題思路,1. 把n個(gè)電話號碼放進(jìn)一個(gè)set內(nèi)2. 枚舉每個(gè)電話號碼的前綴，查詢是否存在于set里,int n;string c[11000];set ss;bool isConsistent(){ss.clear();for (int i = 0; i

3、< n; i++) ss.insert(c[i]);for (int i = 0; i < n; i++) {string st = "";for (int j = 0; j < c[i].size() - 1; j++) {st += c[i][j];if (ss.count(st)) return false;}}return true;},1310 二叉查找樹,給出N個(gè)數(shù)，按

4、照順序建立一棵二叉查找樹，然后輸出該樹的前序遍歷，中序遍歷，后序遍歷。,struct Node {int val;int left, right;Node(int val = 0):val(val), left(0),right(0) {};} p[300000];,void Add(int root, int val){ while (true) { if (p[root].val <

5、val) { if (p[root].right) root = p[root].right; else { p[root].right = ++tot； p[tot] = Node(val); return; } } else { if (p[root].left) root = p[ro

6、ot].left; else { p[root].left = ++tot; p[tot] = Node(val); return; } } },inline void Preorder(int root){if (!root) return;printf(" %d", p[root].val);Preord

7、er(p[root].left);Preorder(p[root].right);},inline void Inorder(int root){if (!root) return;Inorder(p[root].left);printf(" %d", p[root].val);Inorder(p[root].right);},inline void Postorder(int root){if

8、(!root) return;Postorder(p[root].left);Postorder(p[root].right);printf(" %d", p[root].val);},1210 二叉樹,給出一棵二叉樹前序遍歷和后序遍歷的順序，要求出總共有多少棵不同形態(tài)的二叉樹滿足這樣的遍歷順序。,解題思路,1. 前序遍歷第一個(gè)元素是根，后序遍歷最后一個(gè)元素是根 2. 前序遍歷第二個(gè)元素是某子樹的根，但左

9、右不確定 3. 在后序遍歷中找到前序遍歷的第二個(gè)元素，那么以這個(gè)元素為基準(zhǔn)，可以劃分新的左右子樹 4. 當(dāng)前序遍歷的第二個(gè)元素出現(xiàn)在后序遍歷的倒數(shù)第二位，以后序遍歷倒數(shù)第三位起向左數(shù)都是子樹的元素，但是左右不確定，因此有2種情況,long long calc(string pre, string post) {long long ans = 1;int len=pre.size();for(int i= 0; i <

10、 len - 1; i++) {int current = len - 1;while(pre[i] != post[current]) current--;if(current && pre[i+1] == post[current - 1]) ans *= 2;}return ans;},1090 最小生成樹,題目大意：給出N<=500個(gè)節(jié)點(diǎn)的無向圖，每兩個(gè)點(diǎn)之間都有一條無向邊。問該無向圖的最小生成

11、樹中，最長的一條邊的長度。,解題思路,求最小生成樹的算法中，有Prim算法和kruskal算法。Prim算法復(fù)雜度N^2（N為點(diǎn)數(shù)）, Kruskal算法MlogM（M為邊數(shù)） 因此，對于稠密圖而言，Prim算法的復(fù)雜度更高效率。,int solve(){for (int i = 0; i dist[j]) p = j; } u[p] = true; ans = max(ans, dist[p

12、]); for (int j = 0; j < n; j++) { if (u[j] || dist[j] <= e[p][j]) continue; dist[j] = e[p][j]; }}return ans;},1156 二叉樹的前序遍歷,給定一棵N個(gè)節(jié)點(diǎn)的二叉樹，輸出其前序遍歷的順序解題思路：1.按照題目要求把二叉樹讀入2.以前序遍歷順序輸

13、出（可參考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_root[m] = !is_root[m]; is_root[l] = !is_root[l]; is_root[

14、r] = !is_root[r]; p[m].Left = l; p[m].Right = r; p[m].ch = c;}for (int i = 1; i <= 1000; i++) if (is_root[i]) root = i;},void Preorder(int root){if (!root) return;cout << p[root].ch;Preorde

15、r(p[root].Left);Preorder(p[root].Right);},1252 字符串劃分前后綴,給一個(gè)單詞word將一個(gè)前綴換成解釋,,1252 字符串劃分前后綴,將一個(gè)后綴換成解釋,1252 字符串劃分前后綴,單詞的后綴與單詞更緊密例如：unvaporizenot vaporizenot change into vapor,解題思路,先處理前綴strstr函數(shù)判斷單詞是否有前綴去掉前綴遞歸處理

16、后綴反轉(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){

17、 suffixe(r+2); printf(" again\n");}...else{ suffixe(r); puts("");},int n=strlen(r);reverse(r,r+n);if(strstr(r,"re")==r){ reverse(r,r+n); r[n-2]=0; printf(&qu

18、ot;one who %ss",r);}else if(strstr(r,"gni")==r){ reverse(r,r+n); r[n-3]=0; printf("to actively %s",r);}else{ reverse(r,r+n); printf("%s",r);},1155 判斷兩個(gè)點(diǎn)是否連通，并

19、查集,一個(gè)有向圖有N個(gè)點(diǎn)(<=200)問能否從點(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;i<n;i++)#define PB push_backconst int oo=0x3fffffff;rep(i,n){ rep(j,n) r[i][j]=oo

20、; r[i][i]=0;},rep(i,m){ scanf("%d%d",&a,&b); r[a][b]=0;}rep(b,n)rep(a,n)rep(c,n) r[a][c]=min(r[a][c],r[a][b]+r[b][c]);,1132 ROUTES 用括號序列表示樹，求兩節(jié)點(diǎn)最近公共祖先,給出一棵樹求從一個(gè)葉節(jié)點(diǎn)到另一個(gè)葉節(jié)點(diǎn)的路徑樹的表

21、達(dá)式：T(B(FHM(RJK))WD(L)E),T(B(FHM(RJK))WD(L)E),,解題思路,用stack處理樹表達(dá)式計(jì)算出每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)求出從開始節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑A求出從結(jié)束節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑B刪除AB路徑末尾相同的元素順序輸出路徑A倒序輸出路徑B,rep(i,27) f[i]=0;stack S; S.push(0);for(i=0;rs[i];i++)if(rs[i]==')&

22、#39;) S.pop();else if(rs[i]!=')'){ f[rs[i]-'A'+1]=S.top(); if(rs[i+1]=='(') S.push(rs[i]-'A'+1);}puts(rs);,while(gets(rs)!=0 && rs[0]){ sscanf(rs,"%

23、s%s",s1,s2); An=0; for(x=s1[0]-'A'+1;x;x=f[x]) A[An++]=x; Bn=0; for(x=s2[0]-'A'+1;x;x=f[x]) B[Bn++]=x; while(An && Bn && A[An-1]==B[Bn-1]) { An

24、--; Bn--; }},rep(i,An) { if(i) printf("->"); putchar(A[i]+'A'-1); } for(i=Bn;i>=0;i--) printf("->%c",B[i]+'A'-1);

25、puts("");,1306 排序，可用堆排序,給一個(gè)數(shù)組從小到大排序每隔m個(gè)位置輸出數(shù)組里的元素,解題思路,堆排序make_heap(a,a+n,cmp);a[0];a[n++]=key; push_heap(a,a+n,cmp);pop_heap(a,a+n,cmp);用sort排序，直接輸出即可,rep(i,n) scanf("%d",&r[i]);sor

26、t(r,r+n);for(i=0;i<n;i+=m){ if(i) putchar(' '); printf("%d",r[i]);}puts("");,1083 最小生成樹,一個(gè)無向圖求最小生成樹,解題思路,kruskal算法按邊的長度排序從小到大遍歷邊(a,b)用并查集判斷ab兩點(diǎn)是否屬于聯(lián)通集合如果ab不聯(lián)通合并ab所

27、在的集合答案累加邊(a,b),int F(int x){ if(x==f[x]) return x; return f[x]=F(f[x]);}bool cmp(int a,int b){ return C[a]<C[b];}rep(i,m){ scanf("%d%d%d",&A[i],&B[i],&C[i]);

28、id[i]=i;}sort(id,id+m,cmp);,ans=0;rep(i,m){ a=A[id[i]]; b=B[id[i]]; a=F(a); b=F(b); if(a!=b) { f[a]=b; ans+=C[id[i]]; }},期末考試紙質(zhì)資料可以任意帶，帶一旅行箱都可以，電子資料不可以帶復(fù)習(xí)內(nèi)容只涉及上機(jī)考試，不涉及理論考