《算法设计手册》面试题解答 第三章：数据结构
3-18.
你查字典時(shí)用的是什么方法？
解析：
既然要和算法相關(guān)，除了隨機(jī)嘗試，明顯應(yīng)該用二分查找。
不要嫌它簡(jiǎn)單，其實(shí)這是道MS和Google用過的面試題。
?
3-19.
假設(shè)你有一個(gè)裝滿T恤衫的衣柜，如何組織這些T恤衫以便以后取衣服？
解析：
由于衣柜是線性存儲(chǔ)，肯定要用到排序從而應(yīng)用二分查找。具體到T恤衫，可以按顏色排序。
當(dāng)然，如果這是個(gè)商場(chǎng)中的衣柜，那么還應(yīng)該在同樣式內(nèi)部按尺碼排序。
?
3-20.
寫一個(gè)函數(shù)，找出單鏈表的中間結(jié)點(diǎn)。
解析：
比較常見，最簡(jiǎn)單的解法是用兩個(gè)指針，一個(gè)每次后移1個(gè)，另一個(gè)每次后移2個(gè)，速度快的達(dá)到末尾時(shí)，慢的正好在中間。實(shí)際編寫的時(shí)候注意邊界條件（最好把NULL做第0個(gè)結(jié)點(diǎn)，考慮結(jié)點(diǎn)數(shù)奇偶性不要把快的指針移動(dòng)出界），略。
?
3-21.
寫一個(gè)函數(shù)判斷兩個(gè)二叉樹是否全等。樹全等包括結(jié)構(gòu)相同和對(duì)應(yīng)結(jié)點(diǎn)數(shù)據(jù)相同。
解析：
二叉樹遍歷的變形，只是寫函數(shù)返回值時(shí)可能迷惑。可以這樣寫：
int compare(struct node* a, struct node* b) {// 1. both empty -> trueif (a==NULL && b==NULL) return(true); // 2. both non-empty -> compare themelse if (a!=NULL && b!=NULL) {return(a->data == b->data &&compare(a->left, b->left) &&compare(a->right, b->right));}// 3. one empty, one not -> falseelse return 0; }?
3-22.
寫一個(gè)把二叉搜索樹轉(zhuǎn)化為鏈表的程序。
解析：
如果允許使用額外的輔助數(shù)據(jù)結(jié)構(gòu)，可以遍歷樹時(shí)構(gòu)造鏈表，也可以遍歷樹時(shí)把結(jié)點(diǎn)壓入隊(duì)列最后出隊(duì)構(gòu)造。
如果不允許使用額外的存儲(chǔ)空間，把二叉搜索樹原地轉(zhuǎn)化為雙鏈表，思想還是樹的遞歸遍歷：把根的左子樹和右子樹分別轉(zhuǎn)化為雙鏈表，再與根相連接。只不過連接時(shí)右子樹，要注意是把原先的根作為雙鏈表末尾來連接。下面貼的代碼來自于何海濤《劍指Offer》面試題27：二叉搜索樹與雙向鏈表：
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree) {BinaryTreeNode *pLastNodeInList = NULL;ConvertNode(pRootOfTree, &pLastNodeInList);// pLastNodeInList指向雙向鏈表的尾結(jié)點(diǎn)，// 我們需要返回頭結(jié)點(diǎn)BinaryTreeNode *pHeadOfList = pLastNodeInList;while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)pHeadOfList = pHeadOfList->m_pLeft;return pHeadOfList; }void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList) {if(pNode == NULL)return;BinaryTreeNode *pCurrent = pNode;if (pCurrent->m_pLeft != NULL)ConvertNode(pCurrent->m_pLeft, pLastNodeInList);pCurrent->m_pLeft = *pLastNodeInList; if(*pLastNodeInList != NULL)(*pLastNodeInList)->m_pRight = pCurrent;*pLastNodeInList = pCurrent;if (pCurrent->m_pRight != NULL)ConvertNode(pCurrent->m_pRight, pLastNodeInList); } ConvertBinarySearchTree既然來自于《劍指Offer》，這里也附注下好了，設(shè)計(jì)的測(cè)試用例為：
- 功能測(cè)試：完全二叉樹、所有節(jié)點(diǎn)都沒有左/右子樹、只有一個(gè)結(jié)點(diǎn)的二叉樹。
- 特殊輸入測(cè)試：指向根節(jié)點(diǎn)指針為NULL。
?
3-23.
寫一個(gè)逆置鏈表的函數(shù)。再寫一個(gè)非遞歸實(shí)現(xiàn)。
解析：
遞歸實(shí)現(xiàn)只要將當(dāng)前結(jié)點(diǎn)作為已處理部分的最后一個(gè)結(jié)點(diǎn)附加上去即可。
//http://nbl.cewit.stonybrook.edu:60128/mediawiki/index.php/TADM2E_3.23 Node* Reverse(Node*head) {Node* temp=NULL;if(head==NULL){return NULL;}if(head->next==NULL)return head;temp=Reverse(head->next);head->next->next=head;head->next=NULL;return temp; } 遞歸實(shí)現(xiàn)非遞歸實(shí)現(xiàn)需要保存當(dāng)前操縱結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)以免斷鏈，一次遍歷即可。下面的代碼來自于何海濤《劍指Offer》面試題16：反轉(zhuǎn)鏈表：
ListNode* ReverseList(ListNode* pHead) {ListNode* pReversedHead = NULL;ListNode* pNode = pHead;ListNode* pPrev = NULL;while(pNode != NULL){ListNode* pNext = pNode->m_pNext;if(pNext == NULL)pReversedHead = pNode;pNode->m_pNext = pPrev;pPrev = pNode;pNode = pNext;}return pReversedHead; } 非遞歸實(shí)現(xiàn)測(cè)試用例：
- 鏈表頭指針是NULL。
- 輸入鏈表只有一個(gè)頭結(jié)點(diǎn)。
- 輸入鏈表有多個(gè)結(jié)點(diǎn)。
?
3-24.
為網(wǎng)頁爬蟲設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，來判斷URL是否被訪問過。要求時(shí)間空間都最優(yōu)。
解析：
我一開始想到的是URL分段進(jìn)行hash，有人說用前綴樹完成匹配，http://nbl.cewit.stonybrook.edu:60128/mediawiki/index.php/TADM2E_3.24提到使用布隆過濾器。簡(jiǎn)單了解下吧，看上去和分段hash的思路很類似。
布隆過濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過K個(gè)Hash函數(shù)將這個(gè)元素映射成一個(gè)位陣列（Bit array）中的K個(gè)點(diǎn)，把它們置為1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢索元素一定不在；如果都是1，則被檢索元素很可能在。這就是布隆過濾器的基本思想。
優(yōu)點(diǎn)
相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢(shì)。布隆過濾器存儲(chǔ)空間和插入/查詢時(shí)間都是常數(shù)（）。另外, Hash函數(shù)相互之間沒有關(guān)系，方便由硬件并行實(shí)現(xiàn)。布隆過濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)。
布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；
和相同，使用同一組Hash函數(shù)的兩個(gè)布隆過濾器的交并差運(yùn)算可以使用位操作進(jìn)行。
缺點(diǎn)
但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯。誤算率是其中之一。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加。但是如果元素?cái)?shù)量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位列陣變成整數(shù)數(shù)組，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了。然而要保證安全地刪除元素并非如此簡(jiǎn)單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點(diǎn)單憑這個(gè)過濾器是無法保證的。另外計(jì)數(shù)器回繞也會(huì)造成問題。
在降低誤算率方面，有不少工作，使得出現(xiàn)了很多布隆過濾器的變種。
?
3.25
給定一個(gè)字符串和一本雜志，需要你從雜志上剪下來字母從而拼成這個(gè)字符串。給出高效率的算法來判斷這本雜志是否能拼成這個(gè)字符串。
解析：
對(duì)雜志逐個(gè)字母進(jìn)行統(tǒng)計(jì)，當(dāng)種類和個(gè)數(shù)都達(dá)到給定字符串中對(duì)應(yīng)字母的個(gè)數(shù)時(shí)結(jié)束，否則判斷不能拼成。即將字符串按字母序hash，其值是在字符串的出現(xiàn)次數(shù)；檢索雜志時(shí)，每個(gè)字母與hash表進(jìn)行判斷。如果值非0，則減1。
為加速確定是否結(jié)束，還可以存儲(chǔ)字符串內(nèi)各不相同的字母數(shù)，每當(dāng)hash表中某項(xiàng)由1變0，則計(jì)數(shù)減1，減到0時(shí)表示可以拼成。遍歷結(jié)束時(shí)計(jì)數(shù)仍為正數(shù)則表示不能拼成。
?
3.26
翻轉(zhuǎn)句子。"My name is Chris" 變成"Chris is name My"。要求最優(yōu)化時(shí)間和空間復(fù)雜度。
解析：
常見的序列旋轉(zhuǎn)問題。可以參考：http://www.cnblogs.com/wuyuegb2312/p/3139925.html#title013
?
3.27
判斷一個(gè)鏈表是否有環(huán)，并找出環(huán)的入口。要求不使用額外存儲(chǔ)空間。
解析：
鏈表找環(huán)問題。解法和原理請(qǐng)見：http://www.cnblogs.com/wuyuegb2312/p/3183214.html
?
3.28
給定一個(gè)n元數(shù)組X，求出n元數(shù)組M，滿足M[i] = X[1]*X[2]* ... *X[i-1]*X[i+1]*...*X[n]。不允許用除法，可以用額外的存儲(chǔ)空間。（提示：可以快于O(n^2)）
解析：
很常見的題目，《編程之美》2.13"子數(shù)組最大乘積"利用到了這個(gè)算法。
求M[i]需要左右兩段X[1...i-1]和X[i+1...n]的積，那么分別構(gòu)造數(shù)組保存即可。即L[i] =?X[1]*X[2]* ... *X[i]，R[i] =?X[i]*...*X[n]。
構(gòu)造L時(shí)從1開始構(gòu)造，總時(shí)間O(n)；R從n開始倒序構(gòu)造，同樣是O(n)。構(gòu)造X[i]只需L[i-1]和R[i+1]的乘積即可（為便于計(jì)算令L[0]=R[n+1]=1），也只需O(n)。算法整體復(fù)雜度是O(n)。
?
3.29
寫出算法來獲取一個(gè)頁面上出現(xiàn)頻率最高的英文詞組（僅限兩個(gè)單詞組成的詞組，如New York）。使用什么數(shù)據(jù)結(jié)構(gòu)？要求時(shí)間和空間最優(yōu)。
解析：
在《程序設(shè)計(jì)實(shí)踐》（Practise of Programming）上有一段二元馬爾科夫鏈文本生成器做了類似的工作：讀入所有詞對(duì)構(gòu)成哈希表。解決這個(gè)問題也是一樣：從頭至尾讀入每個(gè)詞對(duì)（一次后移一個(gè)單詞）并放入hash表，記錄詞對(duì)出現(xiàn)的次數(shù)，然后求得值最大的詞對(duì)。
本文轉(zhuǎn)自五岳博客園博客，原文鏈接：http://www.cnblogs.com/wuyuegb2312/p/3260011.html，如需轉(zhuǎn)載請(qǐng)自行聯(lián)系原作者
總結(jié)
以上是生活随笔為你收集整理的《算法设计手册》面试题解答 第三章：数据结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Kurento架构
- 下一篇： 二进制日志和数据更新的关系