程序員面試題100題

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

2、鏈表。最近鏈接圧子鏈表的最右結(jié)點(diǎn)（左子樹(shù)的垠大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子璉表的垠左結(jié)點(diǎn)（右子樹(shù)的垠小結(jié)點(diǎn)）。從樹(shù)的根結(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有結(jié)點(diǎn)。思路二：我們可以中序遍歷整棵樹(shù)。按照這個(gè)方式遍歷樹(shù)，比較小的結(jié)點(diǎn)先訪(fǎng)問(wèn)。如果我們每訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)，假設(shè)之詢(xún)?cè)L問(wèn)過(guò)的結(jié)點(diǎn)已經(jīng)調(diào)樓成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)詢(xún)結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪(fǎng)問(wèn)過(guò)之后，整棵樹(shù)也就轉(zhuǎn)換成一個(gè)排序雙向璉表了。參考代碼：肖先我們定義:元査找樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：structBSTreeNode/anodeinthebinarysearchtreeintm_nValue;/valueofnodeBSTreeNode*m

3、_pLeft;/leftchildofnodeBSTreeNode*m_pRight;/rightchildofnode；思路一對(duì)應(yīng)的代碼：/Covertasubbinary-search-treeintoasorteddouble-linkedlist/Input:pNode一theheadofthesubtree/asRight一whetherpNodeistherightchildofitsparent/Output:ifasRightistruezreturntheleastnodeinthesub-tree/elsereturnthegreatestnodeinthesub-tree

4、/BSTreeNode*ConvertNode(BSTreeNode*pNodefboolasRight)if(!pNode)returnNULL;BSTreeNode*pLeft=NULL;BSTreeNode*pRight=NULL;/Converttheleftsub-treeif(pNode-m_pLeft)pLeft=ConvertNode(pNode-m_pLeftzfalse);/Connectthegreatestnodeintheleftsub-treetothecurrentnodeif(pLeft)pLeft-m_pRight=pNode;pNode-m_pLeft=pL

5、eft;/Converttherightsub-treeif(pNode-m_pRight)pRight=ConvertNode(pNode-m_pRightrtrue);/Connecttheleastnodeintherightsub-treetothecurrentnodeif(pRight)pNode-m_pRight=pRight;pRight-m_pLeft=pNode;BSTreeNode*pTemp=pNode;/Ifthecurrentnodeistherightchildofitsparent,/returntheleastnodeinthetreewhoserootist

6、hecurrentnodeif(asRight)(while(pTemp-m_pLeft)pTemp=pTemp-m_pLeft;/Ifthecurrentnodeistheleftchildofitsparent,/returnthegreatestnodeinthetreewhoserootisthecurrentnodeelse(while(pTemp-m_pRight)pTemp=pTemp-m_pRight;returnpTemp;/Covertabinarysearchtreeintoasorteddouble-linkedlist/Input:theheadoftree/Outp

7、ut:theheadofsorteddouble-linkedlist/BSTreeNode*Convert(BSTreeNode*pHeadOfTree)(/Aswgwanttoreturntheheadofthesorteddouble-linkedlist,/v/esetthesecondparametertobetruereturnConvertNode(pHeadOfTree,true);思路二對(duì)應(yīng)的代碼：/Covertasubbinary-search-treeintoasorteddouble-linkedlist/Input:pNode一theheadofthesubtree/

8、pLastNodelnList一thetailofthedouble-linkedlist/voidConvertNode(ESTreeNode*pNodefESTreeNode*&pLastNodelnList)(if(pNode=NULL)return;BSTreeNode*pCurrent=pNode;/Converttheleftsub-treeif(pCurrent-m_pLeft1=NULL)ConvertNode(pCurrent-m_pLeft,pLastNodelnList);/Putthecurrentnodeintothedouble-linkedlistpCurrent

9、-m_pLeft=pLastNodelnList;if(pLastNodelnList1=NULL)pLastNodeInList-m_pRight=pCurrent;pLastNodelnList=pCurrent;/Converttherightsub-treeif(pCurrent-m_pRight!=NULL)ConvertNode(pCurrent-m_pRightrpLastNodelnList);/Covertabinarysearchtreeintoasorteddouble-linkedlist/Input:pHeadOfTree一theheadoftree/Output:t

10、heheadofsorteddouble-linkedlist/BSTreeNode*Convert_Solutionl(ESTreeNode*pHeadOfTree)BSTreeNode*pLastNodelnList=NULL;ConvertNode(pHeadOfTreefpLastNodelnList);/Gettheheadofthedouble-linkedlistBSTreeNode*pHeadOfList=pLastNodelnList;v/hile(pHeadOfList&pHeadOfList-m_pLeft)pHeadOfList=pHeadOfList-m_pLeft;

11、returnpHeadOfList;程序員面試題精選100題(02)一設(shè)計(jì)包含min函數(shù)的棧題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的垠小元索。要求函數(shù)min.push以及pop的時(shí)間復(fù)雜度都是0(1)。分析：這是去年google的一道而試題。我看到這道題目時(shí)，第一反應(yīng)就是每次push一個(gè)新元素時(shí)，將棧里所有逆序元索排序。這樣棧頂元素將是最小元索。但山于不能保證最后push進(jìn)棧的元素最先出棧，這種思路設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個(gè)棧了。在棧里添加一個(gè)成員變屋存放最小元索(或最小元索的位進(jìn))。每次push一個(gè)新兀索進(jìn)棧的時(shí)候，如果該元索比當(dāng)前的最小元索還要小，則更新垠小元素。乍一看

12、這樣思路挺好的。但仔細(xì)一想，該思路存在一個(gè)重要的問(wèn)題：如果當(dāng)前垠小元素彼pop出去，如何才能得到下一個(gè)最小元索？因此僅僅只添加一個(gè)成員變雖存放最小元索(或垠小元索的位建)是不夠的。我們需要一個(gè)輔助棧。每次push-個(gè)新元索的時(shí)候，同時(shí)將呆小元索(或最小元索的位丸。考慮到棧元索的類(lèi)型可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元索的位進(jìn)將能減少空間消耗)push到輔助棧中：每次pop一個(gè)元索出棧的時(shí)候，同時(shí)pop輔助棧。參考代碼：#inc丄ude#incJLudetemplateclassCStackwithMinpublic:CStackWithMin(void)virtualCStackWithMin(vo

13、id)T&top(void);constT&top(void)const;voidpush(constT&value);voidpop(void);constT&min(void)const;private:Tm_data;/theelementsofstack.size_tm_minlndex;/theindicesofminimumelements；/getthelastelementofmutablestacktemplateT&CStackWithMin:top()returnm_databmck();/getthelastelementofnon-mutablestacktempla

14、teconstT&CStackWithMin:top()constreturnm_databmuk();/insertaneimentattheendofstacktemplatevoidCStackWithMin:push(constT&vmJLue)/appendthedataintotheendofm_datam_datapush_back(value);/settheindexofminimumeimentinm_dataattheendofm_minlndexif(m_minlndexsize()=0)m_minlndexpush_back(0);elseif(valuem_data

15、m_minlndexbmc:k()m_minlndexpush_back(m_datasize()一1);elsem_minlndexpush_back(m_minlndexback();/ereasetheelementattheendofstacktemplatevoidCStackWithMin:pop()/popm_datam_datapop_back();/popm_minlndexm_minlndexpop_back();/gettheminimumelementofstacktemplateconstT&CStackWithMin:min()constassert(m_datas

16、ize()0);assert(mminlndexsiNG()0);returnm_datam_minlndex.back();舉個(gè)例子演示上述代碼的運(yùn)行過(guò)程:步驟數(shù)據(jù)棧輔助棧最小值1push33032push43,40,033push3,4,20,0,2小4push13,4,2J0,0,2,315pop3,4,20,0,2小6pop3,40,037push03,4,00,0,20討論：如果思路止確，編寫(xiě)上述代碼不是一件很難的事情。但如果能注意一些細(xì)節(jié)無(wú)疑能在面試中加分。比如我在上面的代碼中做了如下的工作：用模板類(lèi)實(shí)現(xiàn)。如果別人的元素類(lèi)型只是int類(lèi)型，模板將能給而試官帶來(lái)好印彖：兩個(gè)版本的to

17、p函數(shù)。在很多類(lèi)中，都需要提供const和非const版本的成員訪(fǎng)問(wèn)函數(shù)：min函數(shù)中asserte把代碼寫(xiě)的盡雖安全是每個(gè)軟件公司對(duì)程序員的要求：添加一些注釋。注釋既能提高代碼的可讀性，又能增加代碼量，何樂(lè)而不為？總之，在面試時(shí)如果時(shí)間允許，盡雖把代碼寫(xiě)的漂亮一些。說(shuō)不定代碼中的幾個(gè)小亮點(diǎn)就能讓自己輕松拿到心儀的OfferoPS：每當(dāng)push進(jìn)一個(gè)新元素，若比當(dāng)前最小元素小，則將它進(jìn)棧，并將它的index進(jìn)最小輔助棧；若大于當(dāng)前最小元素，則將它進(jìn)棧，并將當(dāng)前最小元素index進(jìn)最小輔助棧(可以重復(fù)進(jìn)棧多次)！程序員面試題精選100題(03)-求子數(shù)組的最大和題目：輸入一個(gè)整形數(shù)組，數(shù)組里有止

18、數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的繪大值。要求時(shí)間復(fù)雜度為0(n)。例如輸入的數(shù)組為1,-2,3,10,-4s7:2廠(chǎng)5,和最大的子數(shù)組為3,10,-4,7,2因此輸出為該子數(shù)組的和佩分析：本題最初為2005年浙江大學(xué)計(jì)算機(jī)系的考研題的最后一道程序設(shè)計(jì)題，在2006年里包拆google在內(nèi)的很多知名公司都把本題當(dāng)作而試題。山于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2006年程序員而試題中經(jīng)典中的經(jīng)典。如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過(guò)非常遺憾的是，山于長(zhǎng)度為n的數(shù)組有0()個(gè)子數(shù)組：而且求一個(gè)長(zhǎng)度為n的數(shù)

19、組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是0(n3)o很容易理解，當(dāng)我們加上一個(gè)止數(shù)時(shí)，和會(huì)增加：當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來(lái)的累加中應(yīng)該拋棄并垂新清零，不然的話(huà)這個(gè)負(fù)數(shù)將會(huì)減少接下來(lái)的和。基于這樣的思路，我們可以寫(xiě)出如下代碼。參考代碼：/Findthegreatestsumofallsub-arrays/Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse/boolFindGreatestSumOfSubArray(int*pDataf/anarrayunsigned

20、intnLength,/thelengthofarrayint&nGreatestSum/thegreatestsumofallsub-arrays)/iftheinputisinvalidfreturnfalseif(pData=NULL)|(nLength=0)returnfalse;intnCurSum=nGreatestSum=0;for(unsignedinti=0;inLength;+i)(nCurSum+=pDatai;/ifthecurrentsumisnegative,discarditif(nCurSumnGreatestSum)nGreatestSum=nCurSum;/

21、ifalldataarenegativeFfindthegreatestelementinthearrayif(nGreatestSum=0)nGreatestSum=pData0;for(unsignedinti=1;inGreatestSum)nGreatestSum=pDatai;returntrue;討論：上述代碼中有兩點(diǎn)值得和大家討論一下：函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回0?那這個(gè)函數(shù)的用戶(hù)怎么區(qū)分輸入無(wú)效和子數(shù)組和的垠大值剛好是0這兩中情況呢？基于這個(gè)考慮，本人認(rèn)為把子數(shù)

22、紐和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)函數(shù)是否止常執(zhí)行的標(biāo)志。輸入有一類(lèi)特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有格數(shù)都是負(fù)數(shù)時(shí)，子數(shù)組和的授大值就是數(shù)組中的報(bào)大元素。編程珠機(jī)第八章，8.4掃描算法。釆用類(lèi)似分治算法的道理：前i個(gè)元素中，最大綜合子數(shù)組要么在i-l個(gè)元素中(maxsofar),要么截止到位置i(maxendinghere)o程序員面試題精選100題(04)-在二元樹(shù)中找出和為某一值的所有路徑題目：輸入一個(gè)整數(shù)和一棵元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪(fǎng)問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如輸入整數(shù)22和如下二元樹(shù)10512則打印

23、出兩條路徑：10,12和10,5,7c元樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為:structBinaryTreeNode/anodeinthebinarytree分析：這是百度的一道筆試題，考査對(duì)樹(shù)這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。當(dāng)訪(fǎng)問(wèn)到某一結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)詢(xún)結(jié)點(diǎn)的值。如果當(dāng)詢(xún)結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來(lái)。如果當(dāng)詢(xún)結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪(fǎng)問(wèn)它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)結(jié)束后，遞歸函數(shù)將自動(dòng)回到父結(jié)點(diǎn)。因此我們?cè)诤瘮?shù)退出之詢(xún)要在路徑上刪除當(dāng)詢(xún)結(jié)點(diǎn)并減左當(dāng)詢(xún)結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路

24、徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個(gè)棧結(jié)構(gòu)，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)i致，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過(guò)程。參考代碼:/Findpathswhosesumequaltoexpectedsum/voidFindPath/anodeofbinarytree/theexpectedsum/apathfromroottocurrentnode/thesumofpathif(1pTreeNode)return;currentSum+=pTreeNode-m_nVaiue;pathpush_back(pTreeNode-m_nValue);/ifthenodeisaleaf,andthesumissameasp

25、re-definedz/thepathiswhatwewantprintthepathboolisLeaf=(ipTreeNode-m_pLeft&!pTfeeNodem_pRight);if(currentSum=expectedSum&isLeaf)(std:vector:iteratoriter=pathbegin();for(;iter!=pathend();+iter)std:cout*iterft1;std:coutstd:endl;/ifthenodeisnotaleafFgotoitschildrenif(pTreeNode-m_pLeft)FindPath(pTreeNode

26、-m_pLeftrexpectedSum,pathzcurrentsum);if(pTreeNode-m_pRight)FindPath(pTreeNode-m_pRightzexpectedSum,path,currentSum);/whenwgfinishvisitinganodeandreturntoitsparentnode,/v/eshoulddeletethisnodefromthepathand/minusthenode1svaluefromthecurrentsumcurrentSum-=pTreeNode-m_nVaiue;pathpop_back();程序員面試題精選100

27、(05)-程序員面試題精選100(05)-査找最小的k個(gè)元素題目：輸入n個(gè)整數(shù)，輸岀其中垠小的k個(gè)。例如輸入1,2,3,4,5,6,7和8這8個(gè)數(shù)字，則垠小的4個(gè)數(shù)字為仁2,3和4。分析：這道題最簡(jiǎn)單的思路莫過(guò)于把輸入的n個(gè)整數(shù)排序，這樣排在最詢(xún)而的k個(gè)數(shù)就是最小的k個(gè)數(shù)。只是這科|思路的時(shí)間復(fù)雜度為O(n/opn)。我們?cè)囍鴮ふ腋斓慕鉀Q思路。我們可以開(kāi)辟一個(gè)長(zhǎng)度為k的數(shù)組。每次從輸入的n個(gè)整數(shù)中讀入一個(gè)數(shù)。如果數(shù)組中已經(jīng)插入的元素少于k個(gè)，則將讀入的整數(shù)直接放到數(shù)組中。否則長(zhǎng)度為k的數(shù)組已經(jīng)滿(mǎn)了，不能再往數(shù)紐里插入元索，只能替換了。如果讀入的這個(gè)整數(shù)比數(shù)組中己有k個(gè)整數(shù)的最大值要小，則用讀

28、入的這個(gè)整數(shù)替換這個(gè)最大值：如果讀入的整數(shù)比數(shù)組中已有k個(gè)整數(shù)的垠大值還要大，則讀入的這個(gè)整數(shù)不可能是最小的k個(gè)整數(shù)之一，拋棄這個(gè)整數(shù)。這種思路相當(dāng)于只要排序k個(gè)榕數(shù)，因此時(shí)間復(fù)雜可以降到O(n+n/ogk)。通常悍f況下k要遠(yuǎn)小于n,所以這種辦法要優(yōu)于前面的思路。這是我能夠想出來(lái)的授快的解決方案。不過(guò)從給而試官留下更好印彖的角度出發(fā)，我們可以進(jìn)一步把代碼寫(xiě)得更漂亮一些。從上而的分析，當(dāng)長(zhǎng)度為k的數(shù)組已經(jīng)滿(mǎn)了之后，如果需要替換，每次替換的都是數(shù)組中的垠大值。在常用的數(shù)據(jù)結(jié)構(gòu)中，能夠在0(1)時(shí)間里得到最大值的數(shù)據(jù)結(jié)構(gòu)為最大堆。因此我們可以用堆(heap)來(lái)代替數(shù)組。另外，H己重頭開(kāi)始寫(xiě)一個(gè)垠大

29、堆需要一定雖的代碼。我們現(xiàn)在不需要垂新去發(fā)明車(chē)輪，因?yàn)樵?xún)?nèi)嗽缇桶l(fā)明出來(lái)了。同樣,STL中的set和multiset為我們做了很好的堆的實(shí)現(xiàn),我們可以拿過(guò)來(lái)用。既偷了懶，又給而試官留下熟悉STL的好印彖，何樂(lè)而不為之？參考代碼：#incJLude#ino丄ude#incJLudeusingnamespacestd;typedefmultisetintzgreaterIntHeap;/findkleastnumbersinavector/voidFindKLeastNumbers(constvector&data,/avectorofdataIntHeap&丄eastNumbeirs,/k.lea

30、stnumbersfoutputunsignedintk)leastNumberscJLGEf();if(k=0|datasi.NG()k)return;vector:const_iteratoriter=databegin();for(;iter!=dataend();+iter)/iflessthankntimberswasinsertedintoleastNumbersif(leastNumberssi.NG()k)leastNumbersinsert(*iter);/leastNumberscontainsknumbersandit1sfullnowelse/firstnumberin

31、leastNumbersisthegreatestoneHntHeap:iteratoriterFirst=leastNumbers.begin。;/ifislessthanthepreviousgreatestnumberif(*iter*(leastNumbersbegin()/replacethepreviousgreatestnumberleastNumberserase(iterFirst);leastNumbersinseirt(itef);程序員面試題精選100題(06)判斷整數(shù)序列是不是二兀査找樹(shù)的后序遍歷結(jié)果題目：輸入一個(gè)整數(shù)數(shù)組，判I析該數(shù)組是不是某二元査找樹(shù)的后序遍歷的結(jié)

32、果。如果是返回true,否則返回false。例如輸入5、7、6、9、門(mén)、10、8,山于這一整數(shù)序列是如下樹(shù)的后序遍歷結(jié)果：8/610/57911因此返回true。如果輸入7、4、6、5,沒(méi)有哪棵樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。分析：這是一道trilogy的筆試題，主要考査對(duì)二元査找樹(shù)的理解。在后續(xù)遍歷得到的序列中，垠后一個(gè)元素為樹(shù)的根結(jié)點(diǎn)。從頭開(kāi)始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元索都應(yīng)該位于序列的左半部分：從第一個(gè)大于跟結(jié)點(diǎn)開(kāi)始到跟結(jié)點(diǎn)前而的一個(gè)元索為止，所有元索都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹(shù)的右子樹(shù)。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的莊、右

33、兩部分是不是都是二元査找樹(shù)。參考代碼:usingnamespacestd;/Verifywhetherasquenceofintegersarethepostordertraversal/ofabinarysearchtree(BST)/Input:squence一thesquenceofintegers/length一thelengthofsquence/Return:returntureifthesquenceistraversalresultofaESTZ/otherwise,returnfalse/boolverifySquenceOfBST(intsquencerintlength)

34、(if(squence=NULL|length=0)returnfalse;/rootofaBSTisattheendofpostordertraversalsquenceintroot=squencelength一1;/thenodesinleftsub-treearelessthantherootinti=0;for(;iroot)break;/thenodesintherightsub-treearegreaterthantherootintj=i;for(;jlength一1;+j)(if(squencej0)left=verifySquenceOfBST(squence,i);/ve

35、rifywhethertherightsub-treeisaBSTboolright=true;if(ilength-1)right=verifySquenceOfBST(squence+izlength-i-1);return(left&right);程序員面試題精選100題(07)-翻轉(zhuǎn)句子中單詞的順序題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開(kāi)。為簡(jiǎn)單起見(jiàn)，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。例如輸入“Iamastudent.M,則輸出“student,aamI”分析：山于編寫(xiě)字符串相關(guān)代碼能夠反映程序員的編程能力和編程習(xí)慣，與字符串相關(guān)的問(wèn)題一直

36、是程序員筆試、而試題的熱門(mén)題目。本題也曾多次受到包括微軟在內(nèi)的大雖公司的青睞。山于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所有字符。這時(shí)，不但翻轉(zhuǎn)了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉(zhuǎn)了。我們?cè)兕嵉姑總€(gè)單詞內(nèi)的字符。山于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時(shí)的順序保持一致。還是以上而的輸入為例子。翻轉(zhuǎn)“Iamastudent.中所有字符得到“.tnedutsamaI”,再翻轉(zhuǎn)每個(gè)單詞中字符的順序得到“students,aami”，止是符合要求的輸出。參考代碼：/Reverseastringbetweentwopointers/Input:pBegin一thebeginpointGfina

37、string/pEnd一theendpointerinastring/voidReverse(char*pEeginfchar*pEnd)if(pBegin=NULL|pEnd=NULL)return;while(pBeginSum(n-1)+n;；intsolution2_Sum(intn)Aa;Bb;Array0=&m;Array1=&b;intvalue=Array1-Sum(n);returnvalue;這種方法是用虛函數(shù)來(lái)實(shí)現(xiàn)函數(shù)的選擇。當(dāng)n不為零時(shí)，執(zhí)彳亍函數(shù)E:Sum當(dāng)n為0時(shí)，執(zhí)彳亍A:Sum。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：typedefint(*fun)

38、(int);intsolution3_f1(inti)return0;intsolution3_f2(inti)funf2=solution3_fsolution3_f2;returni+f!i(i-1);另外我們還可以讓編譯器幫我們來(lái)完成類(lèi)似于遞歸的運(yùn)算，比如如下代碼：templatestructsoiution4_SumenumValueN=solution4_Sum:N+n;；templatestructsolution4_SumenumValueN=1;；soiution4_Sum:N就是1+2+.+100的結(jié)果。當(dāng)編譯器看到solution4_SumB|,就是為模板類(lèi)solution

39、4_Sum以參數(shù)100生成該類(lèi)型的代碼。但以100為參數(shù)的類(lèi)型需要得到以99為參數(shù)的類(lèi)型，因?yàn)閟olution4_Suin:N=solution4_Sum:N+100o這個(gè)過(guò)程會(huì)遞歸一直到參數(shù)為1的類(lèi)型，山于該類(lèi)型已經(jīng)顯式定義，編譯器無(wú)需生成，遞歸編譯到此結(jié)束。山于這個(gè)過(guò)程是在編譯過(guò)程中完成的，因此要求輸入n必須是在編譯期間就能確定，不能動(dòng)態(tài)輸入。這是該方法最大的缺點(diǎn)。而且編譯器對(duì)遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。大家還有更多、更巧妙的思路嗎？歡迎討論a_aPS:遞歸解決intfunc(intn)inti=l;(nl)&(i=func(n-l)+n);returni;程序

40、員面試題精選100題（09）-査找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下：structListNodeintm_nKey;ListNode*m_pNext;；分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再?gòu)奈捕嘶厮輐步?？墒禽斎氲氖菃蜗蜴湵恚挥袕那巴蟮闹羔樁鴽](méi)有從后往前的指針。因此我們需要打開(kāi)我們的思路。既然不能從尾結(jié)點(diǎn)開(kāi)始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來(lái)。假設(shè)整個(gè)鏈表有n個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開(kāi)始的第n-k-1個(gè)結(jié)點(diǎn)（從0開(kāi)始計(jì)數(shù)）。如果我們能夠得到鏈表中結(jié)點(diǎn)的

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

42、遍歷時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開(kāi)始遍歷，在第k-1步之詢(xún)，第二個(gè)指針保持不動(dòng)：在第k-1步開(kāi)始，第個(gè)指針也開(kāi)始從璉表的頭指針開(kāi)始遍歷。山于兩個(gè)指針的距離保持在k-1,當(dāng)?shù)谝粋€(gè)（走在詢(xún)而的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針（走在后而的）指針止好是倒數(shù)第k個(gè)結(jié)點(diǎn)。這種思路只需要遍歷璉農(nóng)一次。對(duì)于很長(zhǎng)的璉表，只需要把每個(gè)結(jié)點(diǎn)從硬盤(pán)導(dǎo)入到內(nèi)存一次。因此這一方法的時(shí)間效率詢(xún)而的方法要高。思路一的參考代碼:/Findthekthnodefromthetailofalist/Input:pListHead一theheadoflist/k一thedistancetothetail/Output

43、:thekthnodefromthetailofalist/ListNode*FindKthToTail_Solutionl(ListNode*pListHeadrunsignedintk)if(pListHead=NULL)returnNULL;/countthenodesnumberinthelistListNode*pCur=pListHead;unsignedintnNum=0;v/hile(pCur-m_pNext!=NULL)pCur=pCur-m_pNext;nNum+;/ifthenumberofnodesinthelistislessthank/donothingif(nNu

44、mk)returnNULL;/thekthnodefromthetailofalist/isthe(n一k)thnodefromtheheadpCur=pListHead;for(unsignedinti=0;im_pNext;returnpCur;思路二的參考代碼：/Findthekthnodefromthetailofalist/Input:pListHead一theheadoflist/k-thedistancetothetail/Output:thekthnodefromthetailofalist/ListNode*FindKthToTail_Solution2(ListNode*p

45、ListHeadrunsignedintk)if(pListHead=NULL)returnNULL;ListNode*pAhead=pListHead;ListNode*pEehind=NULL;for(unsignedinti=0;im_pNext!=NULL)pAhead=pAhead-m_pNext;else/ifthenumberofnodesinthelistislessthan/donothingreturnNULL;pBehind=pListHead;/thedistancebetweenpAheadandpEehindisk/whenpAheadarrivesatthetai

46、l,p/Behindisatthekthnodefromthetailv/hile(pAhead-m_pNext1=NULL)pAhead=pAhead-m_pNext;pBehind=pBehind-m_pNext;returnpBehind;討論：這道題的代碼有大量的指針操作。在軟件開(kāi)發(fā)中，錯(cuò)謀的指針操作是大部分問(wèn)題的根源。因此每個(gè)公司都希望程序員在操作指針時(shí)有良好的習(xí)慣，比如使用指針之詢(xún)判I析是不是空指針。這些都是編程的細(xì)節(jié)，但如果這些細(xì)節(jié)把握得不好，很有可能就會(huì)和心儀的公司失之交臂。另外，這兩種思路對(duì)應(yīng)的代碼都禽有循環(huán)。倉(cāng)有循環(huán)的代碼經(jīng)常出的問(wèn)題是在循環(huán)結(jié)束條件的判斷。是該用小于還是小

47、于籌于？是該用k還是該用k-1?山于題匸I要求的是從0開(kāi)始計(jì)數(shù)，而我們的習(xí)慣思維是從1開(kāi)始計(jì)數(shù)，因此首先要想好這些邊界條件再開(kāi)始編寫(xiě)代碼，再者要在編寫(xiě)完代碼之后再用邊界值、邊界值減1、邊界值加1都運(yùn)彳亍一次(在紙上寫(xiě)代碼就只能在心里運(yùn)行了。擴(kuò)展：和這道題類(lèi)似的題目還有：輸入一個(gè)單向鏈表。如果該鏈表的結(jié)點(diǎn)數(shù)為奇數(shù)，輸出中間的結(jié)點(diǎn)：如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，輸出中間兩個(gè)結(jié)點(diǎn)前而的一個(gè)。如果各位感興趣，請(qǐng)自己分析并編寫(xiě)代碼。解擴(kuò)展題的思路和思路二類(lèi)似吧，也用到兩個(gè)指針。節(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，兩個(gè)指針初始都指向頭結(jié)點(diǎn)，然后一個(gè)每次跳兩個(gè)節(jié)點(diǎn)，一個(gè)每次跳一個(gè)節(jié)點(diǎn)。當(dāng)?shù)谝粋€(gè)指針到達(dá)尾端時(shí)后一個(gè)指針指向需要的節(jié)點(diǎn)。節(jié)

48、點(diǎn)數(shù)為偶數(shù)時(shí)情況基本一樣，只是兩個(gè)指針初始一個(gè)指向頭結(jié)點(diǎn)，一個(gè)指向1號(hào)節(jié)點(diǎn)。后一個(gè)指針每次跳兩個(gè)節(jié)點(diǎn)，前一個(gè)每次只跳一個(gè)節(jié)點(diǎn)。程序員面試題精選100題(10)-在排序數(shù)組中査找和為給定值的兩個(gè)數(shù)字題目：輸入一個(gè)己經(jīng)按升序排序過(guò)的數(shù)紐和一個(gè)數(shù)字，在數(shù)組中査找兩個(gè)數(shù)，使得它們的和止好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。例如輸入數(shù)組1、2、4、1、1k15和數(shù)字15。由于4+11=15,因此輸出4和門(mén)。分析：如果我們不考慮時(shí)間復(fù)雜度，垠簡(jiǎn)單想法的莫過(guò)去先在數(shù)組中固定一個(gè)數(shù)字，再依次判I析數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字。

49、可惜這種思路需要的時(shí)間復(fù)雜度是0(用)。我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個(gè)數(shù)字：如果小于輸入的數(shù)字呢？我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。山于數(shù)組己經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后而移動(dòng)一個(gè)數(shù)字？因?yàn)榕旁诤竺娴臄?shù)字要大一些，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了：同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候，我們把較大的數(shù)字往詢(xún)移動(dòng)，因?yàn)榕旁跀?shù)組前而的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。我們把詢(xún)面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往詢(xún)移動(dòng)

50、；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng)：當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。問(wèn)題是這樣的思路是不是止確的呢？這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以Fl彳亍證明一下。參考代碼：/Findtwonumberswithasuminasortedarray/Output:tureisfoundsuchtwonumbersfotherwisefalse/boolFindTwoNumbersWithSum(intdatar/asortedarrayunsignedintlength,/thelengthofthesortedarrayintsum,/thesumin

51、t&numl,/thefirstnumberzoutputint&num2/thesecondnumber,outputboolfound=false;if(lengthbehind)longlongcurSum=dataahead+databehind;/ifthesumoftwonumbersisequaltotheinput/wghavefoundthemif(curSum=sum)numl=databehind;num?=dataahead;found=true;break;/ifthesumoftwonumbersisgreaterthantheinput/decreasethegr

52、eaternumberelseif(curSumsum)ahead;/ifthesumoftwonumbersislessthantheinput/increasethelessnumberelsebehind+;returnfound;擴(kuò)展：如果輸入的數(shù)紐是沒(méi)有排序的，但知道里而數(shù)字的范困，其他條件不變，如和在0(n)時(shí)間里找到這兩個(gè)數(shù)字？擴(kuò)展問(wèn)題是不是先記數(shù)排序再用原來(lái)的方法？如果是這樣的話(huà)，設(shè)數(shù)字范圍是d,則時(shí)間復(fù)雜度應(yīng)該是0(max(d,n)是這個(gè)思路。如果記最小值為min,最大值為max。新建一個(gè)長(zhǎng)度為max-min+1的數(shù)組。初始化這個(gè)數(shù)組的每個(gè)元素為0。掃描原數(shù)組每個(gè)元素k,在新

53、數(shù)組中下標(biāo)為k-min的位置加1,這樣在0(n)的時(shí)間內(nèi)把原數(shù)組轉(zhuǎn)換為一個(gè)排好序的數(shù)組。接下來(lái)的做法一樣。當(dāng)然，時(shí)間復(fù)雜度標(biāo)記為0(max(d,n)更準(zhǔn)確一些。謝謝指出。程序員面試題精選100題(11)-求二元査找樹(shù)的鏡像題目：輸入一顆二元査找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元査找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。例如輸入：8/610AA57911輸出：8/106AA11975定義元査找樹(shù)的結(jié)點(diǎn)為:structBSTreeNode/anodeinthebinarysearchtree(BST)intm_nVaiue;/valueofnodeBS

54、TreeNode*m_pLeft;/leftchildofnodeBSTreeNode*m_pRight;/rightchildofnode；分析：盡管我們可能一下子不能理解鏡像是什么意思，但上而的例子給我們的直觀感覺(jué)，就是交換結(jié)點(diǎn)的左右子樹(shù)。我們?cè)囍诒闅v例子中的二元査找樹(shù)的同時(shí)來(lái)交換每個(gè)結(jié)點(diǎn)的圧右子樹(shù)。遍歷時(shí)育先訪(fǎng)問(wèn)頭結(jié)點(diǎn)8,我們交換它的圧右子樹(shù)得到：8/106AA91157我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn)6和10的左右子樹(shù)仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們?cè)僭囍粨Q他們的左右子樹(shù)，得到：8/106AA11975剛好就是要求的輸出。上面的分析印證了我們的直覺(jué)：在遍歷元查找樹(shù)時(shí)每訪(fǎng)問(wèn)到一個(gè)結(jié)點(diǎn)，交換它的圧右子樹(shù)。這種思路用遞歸不難實(shí)現(xiàn)，將遍歷二元査找樹(shù)的代碼稍作修改就可以了。參考代碼如下：/MirroraBST(swaptheleftrightchildofeachnode)recursively/theheadofBSTininitialcall/voidMirrorRecursively(BSTreeNode*pNode)(if(!pNode)return;/swaptherightandleftchildsub-treeBSTreeNode*pTemp=pNode-m_pLeft;pNode-m_pLeft=pNode-m_pRight;pNod