程序員面試題精選100題

1、程序員面t題精選（01）一把二元查找樹轉(zhuǎn)變成排序的雙向鏈表題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。比如將二元查找樹10/614/481216轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。分析：本題是微軟的面試題。很多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。思路一：當我們到達某一結(jié)點準備調(diào)整以該結(jié)點為根結(jié)點的子樹時，先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點（左子樹的最大結(jié)點）、當前結(jié)點和右子鏈表的最左結(jié)點（右子樹

2、的最小結(jié)點）。從樹的根結(jié)點開始遞歸調(diào)整所有結(jié)點。思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結(jié)點先訪問。如果我們每訪問一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當前結(jié)點的指針將其鏈接到鏈表的末尾。當所有結(jié)點都訪問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。參考代碼：首先我們定義二元查找樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：structBSTreeNode/anodeinthebinarysearchtreeintm_nValue;/valueofnodeBSTreeNode*m_pLeft;/leftchildofnodeBSTreeNode*m_pRight;/r

3、ightchildofnode;思路一對應的代碼：/Covertasubbinary-search-treeintoasorteddouble-linkedlist/Input:pNode-theheadofthesubtree/asRight-whetherpNodeistherightchildofitsparent/Output:ifasRightistrue,returntheleastnodeinthesub-tree/elsereturnthegreatestnodeinthesub-tree/BSTreeNode*ConvertNode(BSTreeNode*pNode,bool

4、asRight)if(!pNode)returnNULL;BSTreeNode*pLeft=NULL;BSTreeNode*pRight=NULL;/Converttheleftsub-treeif(pNode->m_pLeft)pLeft=ConvertNode(pNode->m_pLeft,false);/Connectthegreatestnodeintheleftsub-treetothecurrentnodeif(pLeft)pLeft->m_pRight=pNode;pNode->m_pLeft=pLeft;/Converttherightsub-treei

5、f(pNode->m_pRight)pRight=ConvertNode(pNode->m_pRight,true);/Connecttheleastnodeintherightsub-treetothecurrentnodeif(pRight)pNode->m_pRight=pRight;pRight->m_pLeft=pNode;BSTreeNode*pTemp=pNode;/Ifthecurrentnodeistherightchildofitsparent,/returntheleastnodeinthetreewhoserootisthecurrentnode

6、if(asRight)while(pTemp->m_pLeft)pTemp=pTemp->m_pLeft;/Ifthecurrentnodeistheleftchildofitsparent,/returnthegreatestnodeinthetreewhoserootisthecurrentnodeelsewhile(pTemp->m_pRight)pTemp=pTemp->m_pRight;returnpTemp;/Covertabinarysearchtreeintoasorteddouble-linkedlist/Input:theheadoftree/Out

7、put:theheadofsorteddouble-linkedlist/BSTreeNode*Convert(BSTreeNode*pHeadOfTree)/Aswewanttoreturntheheadofthesorteddouble-linkedlist,/wesetthesecondparametertobetruereturnConvertNode(pHeadOfTree,true);思路二對應的代碼：/Covertasubbinary-search-treeintoasorteddouble-linkedlist/ Input: pNode -the head of the su

8、b tree/pLastNodeInList-thetailofthedouble-linkedlist/voidConvertNode(BSTreeNode*pNode,BSTreeNode*&pLastNodeInList)if(pNode=NULL)return;BSTreeNode*pCurrent=pNode;/Converttheleftsub-treeif(pCurrent->m_pLeft!=NULL)ConvertNode(pCurrent->m_pLeft,pLastNodeInList);/Putthecurrentnodeintothedouble-

9、linkedlistpCurrent->m_pLeft=pLastNodeInList;if(pLastNodeInList!=NULL)pLastNodeInList->m_pRight=pCurrent;pLastNodeInList=pCurrent;/Converttherightsub-treeif(pCurrent->m_pRight!=NULL)ConvertNode(pCurrent->m_pRight,pLastNodeInList);/Covertabinarysearchtreeintoasorteddouble-linkedlist/Input:

10、pHeadOfTree-theheadoftree/Output:theheadofsorteddouble-linkedlist/BSTreeNode*Convert_Solution1(BSTreeNode*pHeadOfTree)BSTreeNode*pLastNodeInList=NULL;ConvertNode(pHeadOfTree,pLastNodeInList);/Gettheheadofthedouble-linkedlistBSTreeNode*pHeadOfList=pLastNodeInList;while(pHeadOfList&&pHeadOfLis

11、t->m_pLeft)pHeadOfList=pHeadOfList->m_pLeft;returnpHeadOfList;程序員面t北題精選（02）設(shè)計包含min函數(shù)的棧題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時間復雜度都是O（1）。分析：這是去年google的一道面試題。我看到這道題目時，第一反應就是每次push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進棧的元素最先出棧，這種思路設(shè)計的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個棧了。在棧里添加一個成員變量存放最小元素（或最小元素的位置）

12、。每次push一個新元素進棧的時候，如果該元素比當前的最小元素還要小，則更新最小元素。乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果當前最小元素被pop出去，如何才能得到下一個最小元素？因此僅僅只添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時將最小元素（或最小元素的位置?？紤]到棧元素的類型可能是復雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能減少空間消耗）push到輔助棧中；每次pop一個元素出棧的時候，同時pop輔助棧。參考代碼：#include<deque>#include<assert.h>t

13、emplate<typenameT>classCStackWithMinpublic:CStackWithMin(void)virtualCStackWithMin(void)T&top(void);constT&top(void)const;voidpush(constT&value);voidpop(void);constT&min(void)const;private:T>m_data;/theelementsofstacksize_t>m_minIndex;/theindicesofminimumelements;/getthel

14、astelementofmutablestacktemplate<typenameT>T&CStackW讓hMin<T>二top()returnm_data.back();/getthelastelementofnon-mutablestacktemplate<typenameT>constT&CStackW讓hMin<T>二top()constreturnm_data.back();/insertanelmentattheendofstacktemplate<typenameT>voidCStackW讓hMin<

15、;T>二push(constT&value)/appendthedataintotheendofm_datam_data.push_back(value);/settheindexofminimumelmentinm_dataattheendofm_minIndexif(m_minIndex.size()=0)m_minlndex.push_back(0);elseif(value<m_datam_minIndex.back()m_minIndex.push_back(m_data.size()-1);elsem_minIndex.push_back(m_minIndex.

16、back();/ereasetheelementattheendofstacktemplate<typenameT>voidCStackW讓hMin<T>二pop()/popm_datam_data.pop_back();/popm_minIndexm_minIndex.pop_back();/gettheminimumelementofstacktemplate<typenameT>constT&CStackW讓hMin<T>二min()constassert(m_data.size()>0);assert(m_minIndex.

17、size()>0);returnm_datam_minIndex.back();舉個例子演示上述代碼的運行過程：步驟數(shù)據(jù)棧輔助棧最小值1.push33032.push 43,40,03.push 23,4,20,0,24.push 13,4,2,10,0,2,35.pop3,4,20,0,26.pop3,40,07.push 03,4,00,0,2321230但如果能注意一些細討論：如果思路正確，編寫上述代碼不是一件很難的事情節(jié)無疑能在面試中加分。比如我在上面的代碼中做了如下的工作:,用模板類實現(xiàn)。如果別人的元素類型只是int類型，模板將能給面試官帶來好印象； 兩個版本的top函數(shù)。在很

18、多類中，都需要提供const和非const版本的成員訪問函數(shù)； min函數(shù)中assert。把代碼寫的盡量安全是每個軟件公司對程序員的要求； 添加一些注釋。注釋既能提高代碼的可讀性，又能增加代碼量，何樂而不為？總之，在面試時如果時間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個小亮點就能讓自己輕松拿到心儀的Offer。程序員面t題精選(03)-求子數(shù)組的最大和題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。要求時間復雜度為O(n)。例如輸入的數(shù)組為1,-2,3,10,-4,7,2,-5，和最大的子數(shù)組為3,

19、10,-4,7,2,因此輸出為該子數(shù)組的和18。分析：本題最初為2005年浙江大學計算機系的考研題的最后一道程序設(shè)計題，在2006年里包括google在內(nèi)的很多知名公司都把本題當作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2006年程序員面試題中經(jīng)典中的經(jīng)典。如果不考慮時間復雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長度為n的數(shù)組有O(n2)個子數(shù)組；而且求一個長度為n的數(shù)組的和的時間復雜度為O(n)。因此這種思路的時間是O(n3)。很容易理解，當我們加上一個正數(shù)時，和會增加；當我們加上一個負數(shù)時，和會減少。如果當前得到的和是個負數(shù)，那么這個和在接下來的累加中應

20、該拋棄并重新清零，不然的話這個負數(shù)將會減少接下來的和?；谶@樣的思路，我們可以寫出如下代碼。參考代碼：/Findthegreatestsumofallsub-arrays/Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse/boolFindGreatestSumOfSubArray(int*pData,/anarrayunsignedintnLength,/thelengthofarrayint&nGreatestSum/thegreatestsumofallsub-arrays)/iftheinputisinva

21、lid,returnfalseif(pData=NULL)|(nLength=0)returnfalse;intnCurSum=nGreatestSum=0;for(unsignedinti=0;i<nLength;+i)nCurSum+=pData;/ifthecurrentsumisnegative,discarditif(nCurSum<0)nCurSum=0;/ifagreatersumisfound,updatethegreatestsumif(nCurSum>nGreatestSum)nGreatestSum=nCurSum;/ifalldataarenegati

22、ve,findthegreatestelementinthearrayif(nGreatestSum=0)nGreatestSum=pData0;for(unsignedinti=1;i<nLength;+i)if(pData>nGreatestSum)nGreatestSum=pData;returntrue;討論：上述代碼中有兩點值得和大家討論一下： 函數(shù)的返回值不是子數(shù)組和的最大值，而是一個判斷輸入是否有效的標志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當輸入一個空指針是應該返回什么呢？返回0?那這個函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個考

23、慮，本人認為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標志。 輸入有一類特殊情況需要特殊處理。當輸入數(shù)組中所有整數(shù)都是負數(shù)時，子數(shù)組和的最大值就是數(shù)組中的最大元素。程序員面t題精選(04)在二元樹中找出和為某一值的所有路徑題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如輸入整數(shù)22和如下二元樹10/51247則打印出兩條路徑：10,12和10,5,7。二元樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：structBinaryTreeNode/anodeinthebinarytreeintm

24、_nValue;/valueofnodeBinaryTreeNode*m_pLeft;/leftchildofnodeBinaryTreeNode*m_pRight;/rightchildofnode;分析：這是百度的一道筆試題，考查對樹這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。當訪問到某一結(jié)點時，把該結(jié)點添加到路徑上，并累加當前結(jié)點的值。如果當前結(jié)點為葉結(jié)點并且當前路徑的和剛好等于輸入的整數(shù)，則當前的路徑符合要求，我們把它打印出來。如果當前結(jié)點不是葉結(jié)點，則繼續(xù)訪問它的子結(jié)點。當前結(jié)點訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點。因此我們在函數(shù)退出之前要在路徑上刪除當前結(jié)點并減去當前結(jié)點的值，以確保返回父

25、結(jié)點時路徑剛好是根結(jié)點到父結(jié)點的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實際上是一個棧結(jié)構(gòu)，因為路徑要與遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個壓棧和出棧的過程。參考代碼：/Findpathswhosesumequaltoexpectedsum/voidFindPath(BinaryTreeNode*pTreeNode,/anodeofbinarytreeintexpectedSum,/theexpectedsumstd:vector<int>&path,/apathfromroottocurrentnodeint&currentSum/thesumofpath)if(

26、!pTreeNode)return;currentSum+=pTreeNode->m_nValue;path.push_back(pTreeNode->m_nValue);/ifthenodeisaleaf,andthesumissameaspre-defined,/thepathiswhatwewant.printthepathboolisLeaf=(!pTreeNode->m_pLeft&&!pTreeNode->m_pRight);if(currentSum=expectedSum&&isLeaf)std二vector<int

27、>二iterato門ter=path.begin();for(;iter!=path.end();+iter)std:cout<<*iter<<'t'std二cout<<std:endl;/ifthenodeisnotaleaf,gotoitschildrenif(pTreeNode->m_pLeft)FindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum);if(pTreeNode->m_pRight)FindPath(pTreeNode->m_pRigh

28、t,expectedSum,path,currentSum);/whenwefinishvisitinganodeandreturntoitsparentnode,/weshoulddeletethisnodefromthepathand/minusthenode'svaluefromthecurrentsumcurrentSum-=pTreeNode->m_nValue;path.pop_back();程序員面t題精選（05）查找最小的k個元素題目：輸入n個整數(shù)，輸出其中最小的k個。例如輸入1,2,3,4,5,6,7和8這8個數(shù)字，則最小的4個數(shù)字為1,2,3和4。分析：這道題

29、最簡單的思路莫過于把輸入的n個整數(shù)排序，這樣排在最前面的k個數(shù)就是最小的k個數(shù)。只是這種思路的時間復雜度為O(nlogn)。我們試著尋找更快的解決思路。我們可以開辟一個長度為k的數(shù)組。每次從輸入的n個整數(shù)中讀入一個數(shù)。如果數(shù)組中已經(jīng)插入的元素少于k個，則將讀入的整數(shù)直接放到數(shù)組中。否則長度為k的數(shù)組已經(jīng)滿了，不能再往數(shù)組里插入元素，只能替換了。如果讀入的這個整數(shù)比數(shù)組中已有k個整數(shù)的最大值要小，則用讀入的這個整數(shù)替換這個最大值；如果讀入的整數(shù)比數(shù)組中已有k個整數(shù)的最大值還要大，則讀入的這個整數(shù)不可能是最小的k個整數(shù)之一，拋棄這個整數(shù)。這種思路相當于只要排序k個整數(shù)，因此時間復雜可以降到O(n+

30、nlogk)。通常情況下k要遠小于n,所以這種辦法要優(yōu)于前面的思路。這是我能夠想出來的最快的解決方案。不過從給面試官留下更好印象的角度出發(fā)，我們可以進一步把代碼寫得更漂亮一些。從上面的分析，當長度為k的數(shù)組已經(jīng)滿了之后，如果需要替換，每次替換的都是數(shù)組中的最大值。在常用的數(shù)據(jù)結(jié)構(gòu)中，能夠在0(1)時間里得到最大值的數(shù)據(jù)結(jié)構(gòu)為最大堆。因此我們可以用堆(heap)來代替數(shù)組。另外，自己重頭開始寫一個最大堆需要一定量的代碼。我們現(xiàn)在不需要重新去發(fā)明車輪，因為前人早就發(fā)明出來了。同樣，STL中的set和multiset為我們做了很好的堆的實現(xiàn)，我們可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印

31、象，何樂而不為之？參考代碼：#include<set>#include<vector>#include<iostream>usingnamespacestd;typedefmultiset<int,greater<int>>IntHeap;/findkleastnumbersinavector/voidFindKLeastNumbers(constvector<int>&data,/avectorofdataIntHeap&leastNumbers,/kleastnumbers,outputunsigned

32、intk)leastNumbers.clear();if(k=0|data.size()<k)return;vector<int>二constjterato門ter=data.begin();for(;iter!=data.end();+iter)/iflessthanknumberswasinsertedintoleastNumbersif(leastNumbers.size()<k)leastNumbers.insert(*iter);/leastNumberscontainsknumbersandit'sfullnowelse/firstnumberinl

33、eastNumbersisthegreatestoneIntHeap二iterato門terFirst=leastNumbers.begin();/ifislessthanthepreviousgreatestnumberif(*iter<*(leastNumbers.begin()/replacethepreviousgreatestnumberleastNumbers.erase(iterFirst);leastNumbers.insert(*iter);程序員面t題精選（06）-判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷

34、的結(jié)果。如果是返回true,否則返回false。例如輸入5、7、6、9、11、10、8,由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：8/610/57911因此返回true。如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。分析：這是一道trilogy的筆試題，主要考查對二元查找樹的理解。在后續(xù)遍歷得到的序列中，最后一個元素為樹的根結(jié)點。從頭開始掃描這個序列，比根結(jié)點小的元素都應該位于序列的左半部分；從第一個大于跟結(jié)點開始到跟結(jié)點前面的一個元素為止，所有元素都應該大于跟結(jié)點，因為這部分元素對應的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認序列的

35、左、右兩部分是不是都是二元查找樹。參考代碼：usingnamespacestd;/Verifywhetherasquenceofintegersarethepostordertraversal/ofabinarysearchtree(BST)/Input:squence-thesquenceofintegers/length-thelengthofsquence/Return:returntureifthesquenceistraversalresultofaBST,/otherwise,returnfalse/boolverifySquenceOfBST(intsquence口，intlen

36、gth)if(squence=NULL|length<=0)returnfalse;/rootofaBSTisattheendofpostordertraversalsquenceintroot=squencelength-1;/thenodesinleftsub-treearelessthantherootinti=0;for(;i<length-1;+i)if(squence>root)break;/thenodesintherightsub-treearegreaterthantherootintj=i;for(;j<length-1;+j)if(squencej

37、<root)returnfalse;/verifywhethertheleftsub-treeisaBSTboolleft=true;if(i>0)left=verifySquenceOfBST(squence,i);/verifywhethertherightsub-treeisaBSTboolright=true;if(i<length-1)right=verifySquenceOfBST(squence+i,length-i-1);return(left&&right);程序員面t題精選（07）翻轉(zhuǎn)句子中單詞的順序題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的

38、順序，但單詞內(nèi)字符的順序不變句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理例如輸入“Iamastudent.”,則輸出“student.aamI”。分析：由于編寫字符串相關(guān)代碼能夠反映程序員的編程能力和編程習慣，與字符用相關(guān)的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。由于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所有字符。這時，不但翻轉(zhuǎn)了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉(zhuǎn)了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時的順序保持一致。還是以上面的輸入為例子。翻轉(zhuǎn)“Iamastudent.”中所有字符得到

39、".tnedutsamaI”，再翻轉(zhuǎn)每個單詞中字符的順序得到“students.aamI"，正是符合要求的輸出。參考代碼：/Reverseastringbetweentwopointers/Input:pBegin-thebeginpointerinastring/pEnd-theendpointerinastring/voidReverse(char*pBegin,char*pEnd)if(pBegin=NULL|pEnd=NULL)return;while(pBegin<pEnd)chartemp=*pBegin;*pBegin=*pEnd;*pEnd=temp;

40、pBegin+,pEnd-;/Reversethewordorderinasentence,butmaintainthecharacter/orderinsideaword/Input:pData-thesentencetobereversed/char*ReverseSentence(char*pData)if(pData=NULL)returnNULL;char*pBegin=pData;char*pEnd=pData;while(*pEnd!='0')pEnd+;pEnd-;/ReversethewholesentenceReverse(pBegin,pEnd);/Rev

41、erseeverywordinthesentencepBegin=pEnd=pData;while(*pBegin!='0')if(*pBegin='')pBegin+;pEnd+;continue;/AwordisbetweenwithpBeginandpEnd,reverseitelseif(*pEnd=''|*pEnd='0')Reverse(pBegin,-pEnd);pBegin=+pEnd;elsepEnd+;returnpData;程序員面試題精選（08）求1+2+.+n題目：求1+2+口，要求不能使用乘除法、for

42、、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。分析：這道題沒有多少實際意義，因為在軟件開發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關(guān)技術(shù)理解的深刻程度。通常求1+2+n除了用公式n（n+1）/2之外，無外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語句了。我們?nèi)匀粐@循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達到這

43、個效果。比如定義一個類，我們new一含有n個這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個思路：classTemppublic:Temp()+N;Sum+=N;staticvoidReset()N=0;Sum=0;staticintGetSum()returnSum;private:staticintN;staticintSum;intTemp二N=0;intTemp二Sum=0;intsolution1_Sum(intn)Temp二Reset();Temp*a=newTempn;deletea;a=0;returnTem

44、p:GetSum();我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我們不妨定義兩個函數(shù)。一個函數(shù)充當遞歸函數(shù)的角色，另一個函數(shù)處理終止遞歸的情況，我們需要做的就是在兩個函數(shù)里二選一。從二選一我們很自然的想到布爾變量，比如ture(1)的時候調(diào)用第一個函數(shù)，false(0)的時候調(diào)用第二個函數(shù)。那現(xiàn)在的問題是如和把數(shù)值變量n轉(zhuǎn)換成布爾值。如果對n連續(xù)做兩次反運算，即!n,那么非零的n轉(zhuǎn)換為true,0轉(zhuǎn)換為false。有了上述分析，我們再來看下面的代碼：classA;A*Array2;classApublic:virtualintSum(intn)return0;classB:

45、publicApublic:virtualintSum(intn)returnArray!n->Sum(n-1)+n;intsolution2_Sum(intn)Aa;Bb;Array0=&a;Array1=&b;intvalue=Array1->Sum(n);returnvalue;這種方法是用虛函數(shù)來實現(xiàn)函數(shù)的選擇。當n不為零時，執(zhí)行函數(shù)B:Sum；當n為0時，執(zhí)行A:Sum。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：typedefint(*fun)(int);intsolution3_f1(inti)return0;intsolution3_f2(i

46、nti)funf2=solution3_f1,solution3_f2;returni+f!i(i-1);另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：template<intn>structsolution4_SumenumValueN=solution4_Sum<n-1>二N+n;template<>structsolution4_Sum<1>enumValueN=1;solution4_Sum<100>:N就是1+2+100的結(jié)果。當編譯器看到solution4_Sum<100>時，就是為模板類s

47、olution4_Sum以參數(shù)100生成該類型的代碼。但以100為參數(shù)的類型需要得到以99為參數(shù)的類型，因為solution4_Sum<100k：N=solution4_Sum<99>二N+100。這個過程會遞歸一直到參數(shù)為1的類型，由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸編譯到此結(jié)束。由于這個過程是在編譯過程中完成的，因此要求輸入n必須是在編譯期間就能確定，不能動態(tài)輸入。這是該方法最大的缺點。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。大家還有更多、更巧妙的思路嗎？歡迎討論A_A程序員面t題精選（09）-查找鏈表中倒數(shù)第k個結(jié)點題目：輸入一個單向

48、鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下：structListNodeintm_nKey;ListNode*m_pNext;；分析：為了得到倒數(shù)第k個結(jié)點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步?？墒禽斎氲氖菃蜗蜴湵?，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。既然不能從尾結(jié)點開始遍歷這個鏈表，我們還是把思路回到頭結(jié)點上來。假設(shè)整個鏈表有n個結(jié)點，那么倒數(shù)第k個結(jié)點是從頭結(jié)點開始的第n-k-1個結(jié)點（從0開始計數(shù)）。如果我們能夠得到鏈表中結(jié)點的個數(shù)n,那我們只要從頭結(jié)點開始往后走n-k-1步就可以了。如何得到結(jié)點數(shù)

49、n?這個不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個結(jié)點，計數(shù)器加一就行了。這種思路的時間復雜度是O（n）,但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點個數(shù)n,第二次得到從頭結(jié)點開始的第n-k-1個結(jié)點即倒數(shù)第k個結(jié)點。如果鏈表的結(jié)點數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點個數(shù)很多，有可能不能一次性把整個鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個結(jié)點需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1?如果可以，將能有效地提高代碼執(zhí)行的時間效率。如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第k-1步之前

50、，第二個指針保持不動；在第k-1步開始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1,當?shù)谝粋€(走在前面的)指針到達鏈表的尾結(jié)點時，第二個指針(走在后面的)指針正好是倒數(shù)第k個結(jié)點。這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結(jié)點從硬盤導入到內(nèi)存一次。因此這一方法的時間效率前面的方法要高。思路一的參考代碼：/Findthekthnodefromthetailofalist/Input:pListHead-theheadoflist/k-thedistancetothetail/Output:thekthnodefromthetailofalist/List

51、Node*FindKthToTail_Solution1(ListNode*pListHead,unsignedintk)if(pListHead=NULL)returnNULL;/countthenodesnumberinthelistListNode*pCur=pListHead;unsignedintnNum=0;while(pCur->m_pNext!=NULL)pCur=pCur->m_pNext;nNum+;/ifthenumberofnodesinthelistislessthank/donothingif(nNum<k)returnNULL;thekthnodefromthetailofalist/isthe(n-k)thnodefromtheheadpCur=pListHead;for(unsignedinti=0;i<nNum-k;+i)pCur=pCur->m_pNext;returnpCur;思路二的參考代碼：/Findthekthnodefromth