编程之美-第3章 结构之法
3.1. 字符串移位包含問題
方法1:
分別對字符串進行循環移1位,2位,3位…,來判斷給定的字符串是否是其中一個字串.
復雜度是O(n^3)
方法2:
這也是一種利用空間換時間的方法.
代碼如下, 為了簡便實現,采用了C庫中的字符串操作函數:
#if 0 /** 3.1*/ bool isRotate(char *s1,char* s2){int len1=strlen(s1),len2=strlen(s2);char *ss=new char[2*len1+1];strncpy(ss,s1,len1);strncat(ss,s2,len1);char *p=strstr(ss,s2);bool flag;if(p==0)flag=false;elseflag=true;delete[] ss;return true; } int main(){char *s1="ABCD";char *s2="CDAB";if(isRotate(s1,s2))printf("OK");elseprintf("NO");}#endif也可以采用KMP算法進行加快查找: http://blog.csdn.net/linyunzju/article/details/7745553
3.2 電話號碼對應英語單詞問題
這個問題可以直觀的用下面的圖來表示
這樣對于一個號碼所對應的單詞, 可以使用對樹進行搜索的方式進行.
這種情況下采用的是DFS的方式.
下面的代碼中采用了兩種方式, 遞歸和非遞歸的方式. 其實這就是一個組合問題, 需要遍歷所有情況. 對于非遞歸的情況, 其實有些類似非遞歸的排列組合的方式.
#if 0 char *c[10]{"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ" }; int total[10]={0,0,3,3,3,3,3, 4,3,4}; void transform(char *number){int sz=strlen(number);int *answer=new int[sz]();while(1){for(int i=0;i<sz;i++)printf("%c",c[number[i]-'0'][answer[i]]);printf("\n");int k=sz-1;while(k>=0){if(answer[k]<total[number[k]-'0']-1){answer[k]++;break;}else{answer[k]=0;k--;}}if(k<0)break;}delete[] answer; } void dfs(char *number,int *answer,int k,int sz){if(k==sz){for(int i=0;i<sz;i++)printf("%c",c[number[i]-'0'][answer[i]]);printf("\n");}else{for(answer[k]=0;answer[k]<total[number[k]-'0'];answer[k]++)dfs(number,answer,k+1,sz);}} void transform2(char *number){int sz=strlen(number);int *answer=new int[sz]();dfs(number,answer,0,sz);delete[] answer; } int main(){char *number="2345";transform(number);transform2(number); }#endif對于問題二,可以采用下面的解法:
3.3 計算字符串相似度問題(編輯距離問題)
這個問題就是編輯距離的問題.
可以有兩種解決方式: 遞歸的方式和動態規劃的方式.
方法1: 遞歸的方式
這樣就得到了下面的遞歸程序:
#if 0 /** 3.3*/ int calc_edit_dist(char *s1,char *s2){if(*s1=='\0'||s1==0)return strlen(s2);if(*s2=='\0'||s2==0)return strlen(s1);if(*s1==*s2){return calc_edit_dist(s1+1,s2+1);}else{int ed1=calc_edit_dist(s1,s2+1);int ed2=calc_edit_dist(s1+1,s2);int ed3=calc_edit_dist(s1+1,s2+1);if(ed1<ed2)return (ed1<ed3?ed1:ed3)+1;elsereturn (ed2<ed3?ed2:ed3)+1;} } int main(){char *s1="ab";char *s2="bb";printf("%d\n",calc_edit_dist(s1,s2));}#endif但是遞歸程序計算比較慢, 因為中間存在很多的重復計算.
\
方法2: 動態規劃
這個問題其實可以歸結為尋找兩個序列的最長公共子序列問題.
參考: http://blog.csdn.net/linyunzju/article/details/7747718
3.5 最短摘要生成問題
給定一段產品的英文描述，包含M個英文字母，每個英文單詞以空格分隔，無其他標點符號；再給定N個英文單詞關鍵字，請說明思路并編程實現方法String extractSummary(String description,String[] key words)，目標是找出此產品描述中包含N個關鍵字（每個關鍵詞至少出現一次）的長度最短的子串，作為產品簡介輸出。（不限編程語言）20分。
#if 0 bool allExisted(const map<string,int>& mp){map<string,int>::const_iterator ite;for(ite=mp.begin();ite!=mp.end();++ite)if(ite->second==0)return false;return true; } void reset(map<string,int>& mp){map<string,int>::iterator ite;for(ite=mp.begin();ite!=mp.end();++ite)ite->second=0; } int find_min_len_digest(const vector<string>& vec,const vector<string>& keywords){map<string,int> mp;int len=1000000;vector<string>::const_iterator ite,pbeg,pend;for(ite=keywords.begin();ite!=keywords.end();++ite)mp[*ite]=0;pbeg=vec.begin();while(pbeg!=vec.end()){while(pbeg!=vec.end()&&mp.find(*pbeg)==mp.end())++pbeg;if(pbeg==vec.end())break;mp[*pbeg]++;pend=pbeg+1;while(pend!=vec.end()&&!allExisted(mp)){if(mp.find(*pend)==mp.end()) {++pend;}else{mp[*pend]++;++pend;}}if(allExisted(mp)){if(pend!=vec.end()){if(len>pend-pbeg){len=pend-pbeg;}for(ite=pbeg;ite!=pend;++ite)cout<<*ite<<' ';cout<<'\n';}else{if(len>vec.size()-(pbeg-vec.begin()))len=vec.size()-(pbeg-vec.begin());for(ite=pbeg;ite!=vec.end();++ite)cout<<*ite<<' ';cout<<'\n';break;}reset(mp);}pbeg=pend;}return len; } int main(){ // string str[]={"i","am","a","big","boy",".","i","is","i","boy"}; // string key[]={"i","boy"}; string key[] = { "微軟", "計算機", "亞洲"};string str[] = { "微軟","亞洲","研究院","成立","于","1998","年","，","我們","的","使命","是","使","未來","的","計算機","能夠","看","、","聽","、","學","，","能","用","自然語言","與","人類","進行","交流","。","在","此","基礎","上","，","微軟","亞洲","研究院","還","將","促進","計算機","在","亞太","地區","的","普及","，","改善","亞太","用戶","的","計算","體驗","。","”"};vector<string> keywords(key,key+sizeof(key)/sizeof(string));vector<string> vec(str,str+sizeof(str)/sizeof(string));// copy(vec.begin(),vec.end(),ostream_iterator<string>(cout," ")); // cout<<endl; find_min_len_digest(vec,keywords);}#endif3.6 判斷兩個鏈表是否相交
參考: http://blog.csdn.net/linyunzju/article/details/7753548
3.7 隊列中取最大值操作問題
參考: http://blog.csdn.net/linyunzju/article/details/7765324
解法三:
利用兩個STL中的stack適配器來實現帶有最大值操作的棧類, 然后利用兩個新實現的棧來實現帶有最大值操作的隊列.
#if 0 class Stack{public:void push(int x){sta.push(x);if(stb.empty()) {stb.push(x);}else{int t=stb.top();stb.push(t>x?t:x);}}void pop(){if(!sta.empty()){sta.pop();stb.pop();}}int top(){assert(sta.empty()==false);return sta.top();}int maxV(){assert(sta.empty()==false);return stb.top();}int size(){return sta.size();}bool empty(){return sta.empty();}private:stack<int> sta;stack<int> stb; }; class Queue{public:void push(int x){sta.push(x);}void pop(){if(stb.empty()) {while(!sta.empty()) {int t=sta.top(); sta.pop();stb.push(t);}}stb.pop();}int front(){if(stb.empty()) {while(!sta.empty()){int t=sta.top(); sta.pop();stb.push(t);}}return stb.top();}int maxV(){if(stb.empty()){return sta.maxV();}if(sta.empty()){return stb.maxV();}return max(sta.maxV(),stb.maxV());}private:Stack sta;Stack stb; }; int main(){Queue q; int a[] = {2, 3, 4, 9, 4, 5, 10, 6}; for(int i = 0; i < sizeof(a)/sizeof(int); ++i) { q.push(a[i]); } q.push(101);cout<<q.front()<<endl;cout<<"queue maxvalue = "<<q.maxV()<<endl; q.push(590);cout<<"queue maxvalue = "<<q.maxV()<<endl; int deq = q.front(); cout<<"deq = "<<deq<<endl; cout<<"queue maxvalue = "<<q.maxV()<<endl; q.pop();cout<<"queue maxvalue = "<<q.maxV()<<endl; }#endif3.8 求二叉樹中節點的最大距離
計算一個二叉樹的最大距離有兩個情況:
情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。
情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。
只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離。
//思路：注意指針聲明了一定要賦值，否則會報錯。
// 方法一：遞歸法
//距離相差最遠的兩個結點，共有以下兩種情況：
// (1)路徑經過根結點，所以兩個結點在根結點的不同分支上
// (2)路徑不經過根結點，所以兩個結點應該是次根結點中相聚最遠的兩個結點。(遞歸思想)
// 遞歸本質上還是采用了后續遍歷的方法。由于是從葉子結點開始的所以每次處理都是第一種情況。
// 方法二：非遞歸法
//采用后序遍歷二叉樹的同時對二叉樹的結點進行更新，每次更新都要更新最大距離。
struct Node{char data;Node* left;Node* right;int nMaxLeft;int nMaxRight; }; int maxLen=0; void findMaxLength(Node* root){if(root==0)return ;if(root->left==0)root->nMaxLeft=0;if(root->right==0)root->nMaxRight=0;if(root->left!=0)findMaxLength(root->left);if(root->right!=0)findMaxLength(root->right);if(root->left!=0) {root->nMaxLeft=(root->left->nMaxLeft>root->left->nMaxRight?root->left->nMaxLeft:root->left->nMaxRight)+1;}if(root->right!=0){root->nMaxRight=(root->right->nMaxLeft>root->right->nMaxRight?root->right->nMaxLeft:root->right->nMaxRight)+1;}if(root->nMaxLeft+root->nMaxRight>maxLen)maxLen=root->nMaxLeft+root->nMaxRight; } void findMaxLength2(Node* root){stack<Node*> st;Node *p=root,*visited=0;while(p!=0||!st.empty()){while(p!=0){st.push(p);p=p->left;}p=st.top();if(p->right==0||visited==p->right){if(p->left!=0) {p->nMaxLeft=(p->left->nMaxLeft>p->left->nMaxRight?p->left->nMaxLeft:p->left->nMaxRight)+1;}if(p->right!=0){p->nMaxRight=(p->right->nMaxLeft>p->right->nMaxRight?p->right->nMaxLeft:p->right->nMaxRight)+1;}if(p->nMaxLeft+p->nMaxRight>maxLen)maxLen=p->nMaxLeft+p->nMaxRight;st.pop();visited=p;p=0;}elsep=p->right;} }這段代碼有幾個缺點:
算法加入了侵入式(intrusive)的資料nMaxLeft, nMaxRight
使用了全局變量 nMaxLen。每次使用要額外初始化。而且就算是不同的獨立資料，也不能在多個線程使用這個函數
邏輯比較復雜，也有許多 NULL 相關的條件測試。
一種不改變樹本身結構的方法:
我認為這個問題的核心是，情況A 及 B 需要不同的信息: A 需要子樹的最大深度，B 需要子樹的最大距離。只要函數能在一個節點同時計算及傳回這兩個信息，代碼就可以很簡單:
struct RESULT{int nMaxDistance;int nMaxDepth; }; RESULT findMaxLength3(Node* root){if(root==0){RESULT empty={0,-1};return empty;}RESULT lhs=findMaxLength3(root->left);RESULT rhs=findMaxLength3(root->right);RESULT res;res.nMaxDepth=max(lhs.nMaxDepth,rhs.nMaxDepth)+1;res.nMaxDistance=max(max(lhs.nMaxDistance,rhs.nMaxDistance),lhs.nMaxDepth+rhs.nMaxDepth+2);return res; }void postorder(Node* root){stack<Node*> st;Node* p=root,*visited=0;while(p!=0||!st.empty()){while(p!=0){st.push(p);p=p->left;}p=st.top();if(p->right==0||visited==p->right){cout<<(int)p->data<<' ';st.pop();visited=p;p=0;}else{p=p->right;}}cout<<endl; }計算 result 的代碼很清楚；nMaxDepth 就是左子樹和右子樹的深度加1；nMaxDistance 則取 A 和 B 情況的最大值。
為了減少 NULL 的條件測試，進入函數時，如果節點為 NULL，會傳回一個 empty 變量。比較奇怪的是 empty.nMaxDepth = -1，目的是讓調用方 +1 后，把當前的不存在的 (NULL) 子樹當成最大深度為 0。
除了提高了可讀性，這個解法的另一個優點是減少了 O(節點數目) 大小的侵入式資料，而改為使用 O(樹的最大深度) 大小的棧空間。這個設計使函數完全沒有副作用(side effect)。
測試代碼如下:
Node* initTree() { Node* tree[10]; for(int i=0;i<10;i++) { tree[i]=(Node*)malloc(sizeof(Node)); tree[i]->nMaxLeft=0; tree[i]->nMaxRight=0; tree[i]->left=NULL; tree[i]->right=NULL; tree[i]->data=(char)i; } for(int i=0;i<=2;i++) { tree[i]->left=tree[2*i+1]; tree[i]->right=tree[2*i+2]; } tree[3]->left=tree[7]; tree[5]->right=tree[8]; return tree[0]; } int main(){findMaxLength(initTree()); printf("遞歸法:%d\n",maxLen); maxLen=0;findMaxLength2(initTree()); printf("非遞歸:%d\n",maxLen); maxLen=0;RESULT r=findMaxLength3(initTree());printf("new Method:%d\n",r.nMaxDistance); }參考: http://blog.csdn.net/zuiaituantuan/article/details/6210317
http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
3.9 重建二叉樹
主要是給出前序和中序或中序和后序來構造出二叉樹.
這種題一般有二種形式，共同點是都已知中序序列。如果沒有中序序列，是無法唯一確定一棵樹的，證明略。
一、已知二叉樹的前序序列和中序序列，求解樹。
1、確定樹的根節點。樹根是當前樹中所有元素在前序遍歷中最先出現的元素。
2、求解樹的子樹。找出根節點在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點左邊和右邊都為空，則根節點已經為葉子節點。
3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復1、2、3步，直到所有的節點完成定位。
二、已知二叉樹的后序序列和中序序列，求解樹。
1、確定樹的根。樹根是當前樹中所有元素在后序遍歷中最后出現的元素。
2、求解樹的子樹。找出根節點在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點左邊和右邊都為空，則根節點已經為葉子節點。
3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復1、2、3步，直到所有的節點完成定位。
舉例說明：根據已知求解二叉樹
中序序列 HLDBEKAFCG
后序序列 LHDKEBFGCA
1、在后序序列LHDKEBFGCA中最后出現的元素為A，HLDBEK|A|FCG
2、在后序序列LHDKEB中最后出現的元素為B，HLD|B|EK|A|FCG
3、在后序序列LHD中最后出現的元素為D，HL|D|B|EK|A|FCG
4、在后序序列LH中最后出現的元素為H，H|L|D|B|EK|A|FCG
5、在后序序列KE中最后出現的元素為E，H|L|D|B|E|K|A|FCG
5、在后序序列FGC中最后出現的元素為C，H|L|D|B|E|K|A|F|C|G
6、所有元素都已經定位，二叉樹求解完成。
A
/ \
B C
/ \ / \
D E F G
/ \
H K
\
L
下面的代碼中也包括了根據兩個遍歷結果輸出另一個結果.
#if 0 //查找根節點的位置 char* find_root(char *start,char *end,char c){while(start<=end){if(*start==c)return start;start++;}return NULL; } //根據前序和中序來輸出后序：核心函數 void pre_in_post_(char *pre_start,char*pre_end,char* in_start,char *in_end){if(in_start>in_end)return;if(in_start==in_end) {printf("%c",*in_start);return ;}char c=*pre_start++;char *p=find_root(in_start,in_end,c);if(p!=NULL){int len=p-in_start;pre_in_post_(pre_start,pre_start+len-1,in_start,p-1);pre_in_post_(pre_start+len,pre_end,p+1,in_end);}printf("%c",c); } //調用上面的遞歸函數 void pre_in_post(char*pre,char *in){int len1=strlen(pre);int len2=strlen(in);char *pre_end=pre+len1-1;char *in_end=in+len2-1;pre_in_post_(pre,pre_end,in,in_end); } //根據后序和中序來輸出前序 void post_in_pre_(char *post_start,char*post_end,char* in_start,char *in_end){if(in_start>in_end)return;if(in_start==in_end) {printf("%c",*in_start);return ;}char c=*post_end--;char *p=find_root(in_start,in_end,c);printf("%c",c);if(p!=NULL){int len=p-in_start;post_in_pre_(post_start,post_start+len-1,in_start,p-1);post_in_pre_(post_start+len,post_end,p+1,in_end);}} //調用上面的遞歸函數 void post_in_pre(char*post,char *in){int len1=strlen(post);int len2=strlen(in);char *post_end=post+len1-1;char *in_end=in+len2-1;post_in_pre_(post,post_end,in,in_end); } //二叉樹節點定義 struct Node{char data;Node* left;Node* right;Node(){};Node(char c,Node* l=0,Node* r=0):data(c),left(l),right(r){} }; //根據前序和中序來重建二叉樹 Node* rebuild_pre_in_post_(char *pre_start,char*pre_end,char* in_start,char *in_end){if(in_start>in_end)return 0;if(in_start==in_end)return new Node(*in_start);char c=*pre_start++;char *p=find_root(in_start,in_end,c);Node* r=new Node(c);if(p!=NULL){int len=p-in_start;r->left=rebuild_pre_in_post_(pre_start,pre_start+len-1,in_start,p-1);r->right=rebuild_pre_in_post_(pre_start+len,pre_end,p+1,in_end);}return r; } // Node* rebuild_pre_in_post(char*pre,char *in){int len1=strlen(pre);int len2=strlen(in);char *pre_end=pre+len1-1;char *in_end=in+len2-1;Node* root=rebuild_pre_in_post_(pre,pre_end,in,in_end);return root; } //根據后序和中序來重建二叉樹 Node* rebuild_post_in_pre_(char *post_start,char*post_end,char* in_start,char *in_end){if(in_start>in_end)return 0;if(in_start==in_end)return new Node(*in_start);char c=*post_end--;char *p=find_root(in_start,in_end,c);Node* r=new Node(c);if(p!=NULL){int len=p-in_start;r->left=rebuild_post_in_pre_(post_start,post_start+len-1,in_start,p-1);r->right=rebuild_post_in_pre_(post_start+len,post_end,p+1,in_end);}return r; } // Node* rebuild_post_in_pre(char*post,char *in){int len1=strlen(post);int len2=strlen(in);char *post_end=post+len1-1;char *in_end=in+len2-1;Node* root=rebuild_post_in_pre_(post,post_end,in,in_end);return root; } //前序遍歷函數 void PreOrder(Node* root){if(root!=0) {printf("%c ",root->data);PreOrder(root->left);PreOrder(root->right);} } //后序變量函數 void PostOrder(Node* root){if(root!=0) {PostOrder(root->left);PostOrder(root->right);printf("%c ",root->data);} } int main(){char *pre="ACBGEDF";char *in="GBCEADF";char *post="GBECFDA";pre_in_post(pre,in);printf("\n");post_in_pre(post,in);printf("\n");PreOrder(rebuild_pre_in_post(pre,in));printf("\n");PostOrder(rebuild_post_in_pre(post,in)); }#endif參考: http://www.cnblogs.com/bmrs/archive/2010/08/19/SloveTree.html
轉載于:https://www.cnblogs.com/xkfz007/archive/2012/11/07/2758363.html
總結
以上是生活随笔為你收集整理的编程之美-第3章 结构之法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 地址运算符：
- 下一篇： 【转】[教程] CSS入门3：如何插入C