2020年度程序員面試題100題

程序員面試題精選100題完整版

資料僅供參考

程序員面試題精選100題

前言

隨著高校的持續(xù)擴(kuò)張，每年應(yīng)屆畢業(yè)生的數(shù)

目都在不斷增長，伴隨而來的是應(yīng)屆畢業(yè)生的就

業(yè)壓力也越來越大。

在這樣的背景下，就業(yè)變成一個買方市場的

趨勢越來越明顯。為了找到一個稱心的工作，絕

大多數(shù)應(yīng)屆畢業(yè)生都必須重復(fù)經(jīng)歷簡歷篩選、電

話面試、筆試、面試等環(huán)節(jié)。在這些環(huán)節(jié)中，面

試無疑起到最為重要的作用，因?yàn)榻?jīng)過面試公司

能夠最直觀的了解學(xué)生的能力。

為了有效地準(zhǔn)備面試，面經(jīng)這個新興概念應(yīng)

運(yùn)而生。筆者在當(dāng)初找工作階段也從面經(jīng)中獲益

匪淺并最終找到滿意的工作。為了方便后來者，

筆者花費(fèi)大量時間收集并整理散落在茫茫網(wǎng)絡(luò)

中的面經(jīng)。不同行業(yè)的面經(jīng)全然不同，筆者從自

身專業(yè)出發(fā)，著重關(guān)注程序員面試的面經(jīng)，并從

精選出若干具有代表性的技術(shù)類的面試題展開

討論，希望能給讀者帶來一些啟發(fā)。

資料僅供參考

由于筆者水平有限，給各面試題提供的思路

和代碼難免會有錯誤,還請讀者批評指正。另外,

熱忱歡迎讀者能夠提供更多、更好的面試題，本

人將感激不盡。

(01)把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：輸入一棵二元查找樹，將該二元查找

樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)立任

何新的結(jié)點(diǎn)，只調(diào)整指針的指向。

比如將二元查找樹

10

/\

614

/\/\

481216

轉(zhuǎn)換成雙向鏈表

4=6=8=10=12=14=16o

分析：本題是微軟的面試題。很多與樹相關(guān)

的題目都是用遞歸的思路來解決，本題也不例

外。下面我們用兩種不同的遞歸思路來分析。

思路一：當(dāng)我們到達(dá)某一結(jié)點(diǎn)準(zhǔn)備調(diào)整以該

資料僅供參考

結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹時，先調(diào)整其左子樹將左子

樹轉(zhuǎn)換成一個排好序的左子鏈表，再調(diào)整其右子

樹轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點(diǎn)

（左子樹的最大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子鏈表的

最左結(jié)點(diǎn)（右子樹的最小結(jié)點(diǎn)）。從樹的根結(jié)點(diǎn)

開始遞歸調(diào)整所有結(jié)點(diǎn)。

思路二：我們能夠中序遍歷整棵樹。按照這

個方式遍歷樹，比較小的結(jié)點(diǎn)先訪問。如果我們

每訪問一個結(jié)點(diǎn)，假設(shè)之前訪問過的結(jié)點(diǎn)已經(jīng)調(diào)

整成一個排序雙向鏈表，我們再把調(diào)整當(dāng)前結(jié)點(diǎn)

的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪

問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表

To

參考代碼：

首先我們定義二元查找樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

structBSTreeNode//anodeinthebinarysearchtree

（

intm_nValue;//valueofnode

BSTreeNode*m__pLeft;//leftchildofnode

BSTreeNode*m_pRight;//rightchildofnode

｝；

思路一對應(yīng)的代碼：

/////////////////////////////////////////////////////////////////////

//

//Covertasubbinary-search-treeintoasorteddouble-linkedlist

//Input:pNode-theheadofthesubtree

//asRight-whetherpNodeistherightchildofitsparent

//Output:ifasRightistrue,returntheleastnodeinthesub-tree

資料僅供參考

//elsereturnthegreatestnodeinthesub-tree

/////////////////////////////////////////////////////////////////////

//

BSTreeNode*ConvertNode(BSTreeNode*pNodezboolasRight)

(

if(!pNode)

returnNULL;

BSTreeNode*pLeft=NULL;

BSTreeNode*pRight=NULL;

//Converttheleftsub-tree

if(pNode->m__pLeft)

pLeft=ConvertNode(pNode->m__pLeftzfalse);

//Connectthegreatestnodeintheleftsub-treetothecurrentnode

if(pLeft)

{

pLeft->m_jpRight=pNode;

pNode->m_pLeft=pLeft;

}

//Converttherightsub-tree

if(pNode->m_pRight)

pRight=ConvertNode(pNode->m_pRightztrue);

//Connecttheleastnodeintherightsub-treetothecurrentnode

if(pRight)

{

pNode->m__pRight=pRight;

pRight->m_pLeft=pNode;

}

BSTreeNode*pTemp=pNode;

//Ifthecurrentnodeistherightchildofitsparentz

//returntheleastnodeinthetreewhoserootisthecurrentnode

if(asRight)

{

while(pTemp->m__pLeft)

pTemp=pTemp->m_pLeft;

}

//Ifthecurrentnodeistheleftchildofitsparent,

//returnthegreatestnodeinthetreewhoserootisthecurrentnode

資料僅供參考

else

{

while(pTemp->m_j>Right)

pTemp=pTemp->m_pRight;

}

returnpTemp;

}

/////////////////////////////////////////////////////////////////////

//

//Covertabinarysearchtreeintoasorteddouble-linkedlist

//Input:theheadoftree

//Output:theheadofsorteddouble-linkedlist

/////////////////////////////////////////////////////////////////////

//

BSTreeNode*Convert(BSTreeNode*pHeadOfTree)

(

//Aswewanttoreturntheheadofthesorteddouble-linkedlist,

//wesetthesecondparametertobetrue

returnConvertNode(pHeadOfTree,true);

}

思路二對應(yīng)的代碼：

/////////////////////////////////////////////////////////////////////

//

//Covertasubbinary-search-treeintoasorteddouble-linkedlist

//Input:pNode-theheadofthesubtree

//pLastNodelnList-thetailofthedouble-linkedlist

/////////////////////////////////////////////////////////////////////

//

voidConvertNode(BSTreeNode*pNode,BSTreeNode*&pLastNodelnList)

(

if(pNode==NULL)

return;

BSTreeNode*pCurrent=pNode;

//Converttheleftsub-tree

if(pCurrent->m__pLeft!=NULL)

ConvertNode(pCurrent->m_pLeftApLastNodelnList);

//Putthecurrentnodeintothedouble-linkedlist

pCurrent->m_j>Left=pLastNodelnList;

資料僅供參考

if(pLastNodelnList!=NULL)

pLastNodeInList->m_j>Right=pCurrent;

pLastNodelnList=pCurrent;

//Converttherightsub-tree

if(pCurrent->m_pRight!=NULL)

ConvertNode(pCurrent->m__pRight,pLastNodelnList);

}

/////////////////////////////////////////////////////////////////////

//

//Covertabinarysearchtreeintoasorteddouble-linkedlist

//Input:pHeadOfTree-theheadoftree

//Output:theheadofsorteddouble-linkedlist

/////////////////////////////////////////////////////////////////////

//

BSTreeNode*Convert_Solutionl(BSTreeNode*pHeadOfTree)

{

BSTreeNode*pLastNodeInList=NULL;

ConvertNode(pHeadOfTreezpLastNodelnList);

//Gettheheadofthedouble-linkedlist

BSTreeNode*pHeadOfList=pLastNodelnList;

while(pHeadOfList&&pHeadOfList->m_j>Left)

pHeadOfList=pHeadOfList->m__pLeft;

returnpHeadOfList;

)

(02)設(shè)計(jì)包含min函數(shù)的棧

題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min

函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、

push以及pop的時間復(fù)雜度都是0(1)。

分析：這是去年google的一道面試題。

資料僅供參考

我看到這道題目時，第一反應(yīng)就是每次push一

個新元素時，將棧里所有逆序元素排序。這樣棧

頂元素將是最小元素。但由于不能保證最后

push進(jìn)棧的元素最先出棧，這種思路設(shè)計(jì)的數(shù)

據(jù)結(jié)構(gòu)已經(jīng)不是一個棧了。

在棧里添加一個成員變量存放最小元素（或最小

元素的位置）。每次push一個新元素進(jìn)棧的時

候，如果該元素比當(dāng)前的最小元素還要小，則更

新最小元素。

乍一看這樣思路挺好的。但仔細(xì)一想，該思路存

在一個重要的問題：如果當(dāng)前最小元素被pop

出去，如何才能得到下一個最小元素？

因此僅僅只添加一個成員變量存放最小元素（或

最小元素的位置）是不夠的。我們需要一個輔助

棧。每次push一個新元素的時候，同時將最小

元素（或最小元素的位置?？紤]到棧元素的類型

可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能

減少空間消耗）push到輔助棧中；每次pop一

個元素出棧的時候，同時pop輔助棧。

參考代碼：

#include<deque>

#include<assert.h>

template<typenameT>classCStackWithMin

資料僅供參考

public:

CStackWithMin(void){}

virtual^CStackWithMin(void){}

T&top(void);

constT&top(void)const;

voidpush(constT&value);

voidpop(void);

constT&min(void)const;

private:

T>m_data;//theelementsofstack

size__t>m_minlndex;//theindicesofminimumelements

}；

//getthelastelementofmutablestack

template<typenameT>T&CStackWithMin<T>::top()

(

returnm_data.back();

}

//getthelastelementofnon-mutablestack

template<typenameT>constT&CStackWithMin<T>::top()const

(

returnm_data.back();

)

//insertanelmentattheendofstack

template<typenameT>voidCStackWithMin<T>::push(constT&value)

(

//appendthedataintotheendofm_data

m_data.push_back(value);

//settheindexofminimumelmentinm_dataattheendofm_jninIndex

if(m__minlndex.size()==0)

m_minlndex.push_back(0);

else

{

if(value<m_data[m__minlndex.back()])

m_minlndex.push_back(m_data.size()-1);

else

資料僅供參考

m_minlndex.push_back(mjminlndex.back());

}

}

//ereasetheelementattheendofstack

template<typenameT>voidCStackWithMin<T>::pop()

(

//popm_data

m_data.pop__back();

//popm_minlndex

m_jninIndex.pop__back();

}

//gettheminimumelementofstack

template<typenameT>constT&CStackWithMin<T>::min()const

(

assert(m__data.size()>0);

assert(m_minlndex.size()>0);

returnm_data[m_jninlndex.back()];

}

舉個例子演示上述代碼的運(yùn)行過程：

步驟數(shù)據(jù)棧輔助

棧最小值

1.push

3303

2.push

43,40,03

3.push

23,4,20,0,22

4.push

13,4,2,10,0,2,31

資料僅供參考

5.pop3,4,20,0,2

2

6.pop3r40,0

3

7.push

03,4,00,0,20

討論：如果思路正確，編寫上述代碼不是一件很

難的事情。但如果能注意一些細(xì)節(jié)無疑能在面試

中加分。比如我在上面的代碼中做了如下的工

作：

?用模板類實(shí)現(xiàn)。如果別人的元素類型只是

int類型，模板將能給面試官帶來好印象；

?兩個版本的top函數(shù)。在很多類中，都需

要提供const和非const版本的成員訪問函數(shù);

?min函數(shù)中assert。把代碼寫的盡量安全

是每個軟件公司對程序員的要求；

?添加一些注釋。注釋既能提高代碼的可讀

性，又能增加代碼量，何樂而不為？

總之，在面試時如果時間允許，盡量把代碼寫的

漂亮一些。說不定代碼中的幾個小亮點(diǎn)就能讓自

己輕松拿到心儀的Offero

資料僅供參考

(03)一求子數(shù)組的最大和

題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)

數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)

組，每個子數(shù)組都有一個和。求所有子數(shù)組的和

的最大值。要求時間復(fù)雜度為O(n)。

例如輸入的數(shù)組為1,-2,3,10,?4,7,2,-5,和最

大的子數(shù)組為3,10,?4,7,2,因此輸出為該子數(shù)

組的和18。

分析：本題最初為浙江大學(xué)計(jì)算機(jī)系的考研題

的最后一道程序設(shè)計(jì)題，在里包括google在

內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本

題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為程序員

面試題中經(jīng)典中的經(jīng)典。

如果不考慮時間復(fù)雜度，我們能夠枚舉出所有子

數(shù)組并求出她們的和。不過非常遺憾的是，由于

長度為n的數(shù)組有0(M)個子數(shù)組；而且求一個

長度為n的數(shù)組的和的時間復(fù)雜度為0(n)。因

此這種思路的時間是0(2)。

很容易理解，當(dāng)我們加上一個正數(shù)時，和會增加;

當(dāng)我們加上一個負(fù)數(shù)時，和會減少。如果當(dāng)前得

到的和是個負(fù)數(shù)，那么這個和在接下來的累加中

資料僅供參考

應(yīng)該拋棄并重新清零，不然的話這個負(fù)數(shù)將會減

少接下來的和。基于這樣的思路，我們能夠?qū)懗?/p>

如下代碼。

參考代碼：

/////////////////////////////////////////////////////////////////////

////////

//Findthegreatestsumofallsub-arrays

//Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse

111111111111111111111111111111111111111111111111111111111111111111111

////////

boolFindGreatestSumOfSubArray

(

int*pDatar//anarray

unsignedintnLength,//thelengthofarray

int&nGreatestSum//thegreatestsumofallsub-arrays

)

(

//iftheinputisinvalid,returnfalse

if((pData==NULL)||(nLength==0))

returnfalse;

intnCurSum=nGreatestSum=0;

for(unsignedinti=0;i<nLength;++i)

{

nCurSum+=pData[i];

//ifthecurrentsumisnegative,discardit

if(nCurSum<0)

nCurSum=0;

//ifagreatersumisfound,updatethegreatestsum

if(nCurSum>nGreatestSum)

nGreatestSum=nCurSum;

}

//ifalldataarenegative,findthegreatestelementinthearray

if(nGreatestSum==0)

{

nGreatestSum=pData[0];

for(unsignedinti=1;i<nLength;++i)

資料僅供參考

if(pData[i]>nGreatestSum)

nGreatestSum=pData[i];

}

}

returntrue;

}

討論：上述代碼中有兩點(diǎn)值得和大家討論一下：

?函數(shù)的返回值不是子數(shù)組和的最大值，而

是一個判斷輸入是否有效的標(biāo)志。如果函數(shù)返回

值的是子數(shù)組和的最大值，那么當(dāng)輸入一個空指

針是應(yīng)該返回什么呢？返回0?那這個函數(shù)的用

戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好

是。這兩中情況呢？基于這個考慮，本人認(rèn)為把

子數(shù)組和的最大值以引用的方式放到參數(shù)列表

中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標(biāo)

O

?輸入有一類特殊情況需要特殊處理。當(dāng)輸

入數(shù)組中所有整數(shù)都是負(fù)數(shù)時，子數(shù)組和的最大

值就是數(shù)組中的最大元素。

(04)一在二元樹中找出和為某一值的所有路徑

題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)

點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)

點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所

資料僅供參考

有路徑。

例如輸入整數(shù)22和如下二元樹

10

/\

512

/\

47

則打印出兩條路徑：10,12和10,5,7。

二元樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：

structBinaryTreeNode//anodeinthebinarytree

(

intm_nValue;//valueofnode

BinaryTreeNode*m__pLeft;//leftchildofnode

BinaryTreeNode*m_pRight;//rightchildofnode

｝；

分析：這是百度的一道筆試題，考查對樹這種基

本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。

當(dāng)訪問到某一結(jié)點(diǎn)時，把該結(jié)點(diǎn)添加到路徑上，

并累加當(dāng)前結(jié)點(diǎn)的值。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)而

且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的

路徑符合要求，我們把它打印出來。如果當(dāng)前結(jié)

點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問它的子結(jié)點(diǎn)。當(dāng)前結(jié)

點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點(diǎn)。因

此我們在函數(shù)退出之前要在路徑上刪除當(dāng)前結(jié)

點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時路

資料僅供參考

徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出

保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個棧結(jié)構(gòu)，因?yàn)?/p>

路徑要與遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就

是一個壓棧和出棧的過程。

參考代碼：

/////////////////////////////////////////////////////////////////////

//

//Findpathswhosesumequaltoexpectedsum

/////////////////////////////////////////////////////////////////////

//

voidFindPath

(

BinaryTreeNode*pTreeNode,//anodeofbinarytree

intexpectedSum,//theexpectedsum

std::vector<int>&path,//apathfromroottocurrentnode

int¤tSum//thesumofpath

)

{

if(!pTreeNode)

return;

currentSum+=pTreeNode->m_nValue;

path.push__back(pTreeNode->m__nValue);

//ifthenodeisaleaf,andthesumissameaspre-defined,

//thepathiswhatwewant,printthepath

boolisLeaf=(!pTreeNode->m_pLeft&&!pTreeNode->m__pRight);

if(currentSum==expectedSum&&isLeaf)

{

std::vector<int>::iteratoriter=path.begin();

for(;iter!=path.end();++iter)

std::cout?*iter?'\t*;

std::cout?std::endl;

)

//ifthenodeisnotaleaf,gotoitschildren

if(pTreeNode->m__pLeft)

FindPath(pTreeNode->m_j>Left,expectedSum,path,currentSum);

if(pTreeNode->m__pRight)

資料僅供參考

FindPath(pTreeNode->m_pRight,expectedSum,path,currentSum);

//whenwefinishvisitinganodeandreturntoitsparentnode,

〃weshoulddeletethisnodefromthepathand

//minusthenode'svaluefromthecurrentsum

currentSum-=pTreeNode->m_nValue;//?!Ithinkhereisnouse

path.pop__back();

)

(05)查找最小的k個元素

題目：輸入n個整數(shù)，輸出其中最小的k個。

例如輸入1,2,3,4,5,6,7和8這8個數(shù)

字，則最小的4個數(shù)字為1,2,3和4。

分析:這道題最簡單的思路莫過于把輸入的n個

整數(shù)排序，這樣排在最前面的k個數(shù)就是最小的

k個數(shù)。只是這種思路的時間復(fù)雜度為

O(n/ogn)o我們試著尋找更快的解決思路。

我們能夠開辟一個長度為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ù)。這種思路相當(dāng)于只要排序k個整數(shù)，

因此時間復(fù)雜能夠降到O(n+n/ogk)。一般情況下k要

遠(yuǎn)小于n,因此這種辦法要優(yōu)于前面的思路。

這是我能夠想出來的最快的解決方案。不過從給

面試官留下更好印象的角度出發(fā)，我們能夠進(jìn)一

步把代碼寫得更漂亮一些。從上面的分析，當(dāng)長

度為k的數(shù)組已經(jīng)滿了之后，如果需要替換，每

次替換的都是數(shù)組中的最大值。在常見的數(shù)據(jù)結(jié)

構(gòu)中，能夠在0(1)時間里得到最大值的數(shù)據(jù)結(jié)

構(gòu)為最大堆。因此我們能夠用堆(he叩)來代

替數(shù)組。

另外，自己重頭開始寫一個最大堆需要一定量的

代碼。我們現(xiàn)在不需要重新去創(chuàng)造車輪，因?yàn)榍?/p>

人早就創(chuàng)造出來了。同樣，STL中的set和

multiset為我們做了很好的堆的實(shí)現(xiàn)，我們能夠

拿過來用。既偷了懶，又給面試官留下熟悉STL

的好印象，何樂而不為之？

參考代碼：

#include<set>

#include<vector>

#include<iostream>

usingnamespacestd;

typedefmultiset<int,greater<int>>IntHeap;

/////////////////////////////////////////////////////////////////////

資料僅供參考

//

//findkleastnumbersinavector

/////////////////////////////////////////////////////////////////////

//

voidFindKLeastNumbers

(

constvector<int>&data,//avectorofdata

IntHeap&leastNuinbers,//kleastnumberszoutput

unsignedintk

)

(

leastNumbers.clear();

if(k==0||data.size()<k)

return;

vector<int>::const_iteratoriter=data.begin();

for(;iter!=data.end();++iter)

{

//iflessthanknumberswasinsertedintoleastNuinbers

if((leastNuinbers.size())<k)

leastNumbers.insert(*iter);

//leastNuinberscontainsknumbersandit*sfullnow

else

(

//firstnumberinleastNumbersisthegreatestone

IntHeap::iteratoriterFirst=leastNuinbers.begin();

//ifislessthanthepreviousgreatestnumber

if(*iter<*(leastNuinbers.begin()))

{

//replacethepreviousgreatestnumber

leastNuinbers.erase(iterFirst);

leastNuinbers.insert(*iter);

}

)

}

}

(06)判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果

資料僅供參考

題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某

二元查找樹的后序遍歷的結(jié)果。如果是返回

true,否則返回falseo

例如輸入5、7、6、9、11、10、8,由于這一

整數(shù)序列是如下樹的后序遍歷結(jié)果：

8

/\

610

/\/\

57911

因此返回trueo

如果輸入7、4、6、5,沒有哪棵樹的后序遍歷

的結(jié)果是這個序列，因此返回false。

分析：這是一道trilogy的筆試題，主要考查對

二元查找樹的理解。

在后續(xù)遍歷得到的序列中，最后一個元素為樹的

根結(jié)點(diǎn)。從頭開始掃描這個序列，比根結(jié)點(diǎn)小的

元素都應(yīng)該位于序列的左半部分；從第一個大于

跟結(jié)點(diǎn)開始到跟結(jié)點(diǎn)前面的一個元素為止，所有

元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對應(yīng)的

是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為

左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部

資料僅供參考

分是不是都是二元查找樹。

參考代碼：

usingnamespacestd;

/////////////////////////////////////////////////////////////////////

//

//Verifywhetherasquenceofintegersarethepostordertraversal

//ofabinarysearchtree(BST)

//Input:squence-thesquenceofintegers

//length-thelengthofsquence

//Return:returntureifthesquenceistraversalresultofaBSTA

//otherwise,returnfalse

/////////////////////////////////////////////////////////////////////

//

boolverifySquenceOfBST(intsquence[],intlength)

(

if(squence==NULL||length<=0)

returnfalse;

//rootofaBSTisattheendofpostordertraversalsquence

introot=squence[length-1];

//thenodesinleftsub-treearelessthantheroot

inti=0;

for(;i<length-1;++i)

{

if(squence[i]>root)

break;

)

//thenodesintherightsub-treearegreaterthantheroot

intj=i;

for(;j<length-1;++j)

{

if(squence[j]<root)

returnfalse;

)

//verifywhethertheleftsub-treeisaBST

boolleft=true;

if(i>0)

left=verifySquenceOfBST(squence,i);

資料僅供參考

//verifywhethertherightsub-treeisaBST

boolright=true;

if(i<length-1)

right=verifySquenceOfBST(squence+i,length-i-1);

return(left&&right);

}

(07)一翻轉(zhuǎn)句子中單詞的順序

題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順

序，但單詞內(nèi)字符的順序不變。句子中單詞以空

格符隔開。為簡單起見，標(biāo)點(diǎn)符號和普通字母一

樣處理。

例如輸入“Iamastudent.”，貝(I輸出astudent,

aamI”。

分析：由于編寫字符串相關(guān)代碼能夠反映程序員

的編程能力和編程習(xí)慣，與字符串相關(guān)的問題一

直是程序員筆試、面試題的熱門題目。本題也曾

多次受到包括微軟在內(nèi)的大量公司的青睞。

由于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所

有字符。這時，不但翻轉(zhuǎn)了句子中單詞的順序，

而且單詞內(nèi)字符也被翻轉(zhuǎn)了。我們再顛倒每個單

詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因

此順序依然和輸入時的順序保持一致。

還是以上面的輸入為例子。翻轉(zhuǎn)“Iama

資料僅供參考

student.”中所有字符得到“.tnedutsamaI”，

再翻轉(zhuǎn)每個單詞中字符的順序得到"students,

aami",正是符合要求的輸出。

參考代碼：

/////////////////////////////////////////////////////////////////////

//

//Reverseastringbetweentwopointers

//Input:pBegin-thebeginpointerinastring

//pEnd-theendpointerinastring

/////////////////////////////////////////////////////////////////////

//

voidReverse(char*pBeginzchar*pEnd)

(

if(pBegin==NULL||pEnd==NULL)

return;

while(pBegin<pEnd)

{

chartemp=*pBegin;

*pBegin=*pEnd;

*pEnd=temp;

pBegin++,pEnd——;

}

)

/////////////////////////////////////////////////////////////////////

//

//Reversethewordorderinasentence,butmaintainthecharacter

//orderinsideaword

//Input:pData-thesentencetobereversed

/////////////////////////////////////////////////////////////////////

//

char*Reversesentence(char*pData)

{

if(pData==NULL)

returnNULL;

char*pBegin=pData;

char*pEnd=pData;

資料僅供參考

while(*pEnd!='\01)

pEnd++;

pEnd--;

//Reversethewholesentence

Reverse(pBegin,pEnd);

//Reverseeverywordinthesentence

pBegin=pEnd=pData;

while(*pBegin!='\01)

{

if(*pBegin=11)

(

pBegin++;

pEnd++;

continue;

}

//AwordisbetweenwithpBeginandpEnd,reverseit

elseif(*pEnd==11||*pEnd==*\01)

(

Reverse(pBegin,--pEnd);

pBegin=++pEnd;

}

else

(

pEnd++;

}

}

returnpData;

}

(08)—求1+2+...+n

題目：求1+2+…+n,要求不能使用乘除法、for、

while、if、else>switch>case等關(guān)鍵字以及條件

判斷語句(A?B:C)o

分析：這道題沒有多少實(shí)際意義，因?yàn)樵谲浖_

資料僅供參考

發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效

地考查發(fā)散思維能力，而發(fā)散思維能力能反映出

對編程相關(guān)技術(shù)理解的深刻程度。

一般求1+2+…+n除了用公式n(n+l)/2之外，無

外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制

for和while的使用，循環(huán)已經(jīng)不能再用了。同

樣,遞歸函數(shù)也需要用if語句或者條件判斷語句

來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題

目已經(jīng)不允許使用這兩種語句了。

我們依然圍繞循環(huán)做文章。循環(huán)只是讓相同的代

碼執(zhí)行n遍而已，我們完全能夠不用for和while

達(dá)到這個效果。比如定義一個類，我們new一

含有n個這種類型元素的數(shù)組，那么該類的構(gòu)造

函數(shù)將確定會被調(diào)用n次。我們能夠?qū)⑿枰獔?zhí)行

的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個

思路：

classTemp

(

public:

Temp(){++N;Sum+=N;}

staticvoidReset(){N=0;Sum=0;}

staticintGetSumf){returnSum;}

private:

staticintN;

staticintSum;

}；

資料僅供參考

intTemp::N=0;

intTemp::Sum=0;

intsolutionl_Sum(intn)

{

Temp::Reset();

Temp*a=newTemp[n];

delete[]a;

a=0;

returnTemp::GetSum();

}

我們同樣也能夠圍繞遞歸做文章。既然不能判斷

是不是應(yīng)該終止遞歸，我們不妨定義兩個函數(shù)。

一個函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個函數(shù)處理

終止遞歸的情況，我們需要做的就是在兩個函數(shù)

里二選一。從二選一我們很自然的想到布爾變

量，比如ture(l)的時候調(diào)用第一個函數(shù)，false

(0)的時候調(diào)用第二個函數(shù)。那現(xiàn)在的問題是

如和把數(shù)值變量n轉(zhuǎn)換成布爾值。如果對n連續(xù)

做兩次反運(yùn)算,即!!H,那么非零的n轉(zhuǎn)換為true,

0轉(zhuǎn)換為false。有了上述分析，我們再來看下面

的代碼：

classA;

A*Array[2];

classA

(

public:

virtualintSum(intn){return0;}

}；

資料僅供參考

classB:publicA

(

public:

virtualintSum(intn){returnArray[!!n]->Sum(n-l)+n;}

}；

intsolution2_Sum(intn)

(

Aa;

Bb;

Array[0]=&a;

Array[1]=&b;

intvalue=Array[1]->Sum(n);

returnvalue;

}

這種方法是用虛函數(shù)來實(shí)現(xiàn)函數(shù)的選擇。當(dāng)n不

為零時，執(zhí)行函數(shù)日.；當(dāng)n為0時，執(zhí)行A：：sun。

我們也能夠直接用函數(shù)指針數(shù)組，這樣可能還更

直接一些：

typedefint(*fun)(int);

intsolution3_f1(inti)

(

return0;

}

intsolution3_f2(inti)

(

funf[2]={solution3_f1zsolution3_f2};

returni+f[!!i](i-1)；

}

另外我們還能夠讓編譯器幫我們來完成類似于遞歸的運(yùn)算，比如如下代碼：

template<intn>structsolution4__Sum

(

enumValue{N=solution4_Sxim<n-1>::N+n);

}；

template<>structsolution4Sum<l>

資料僅供參考

enumValue{N=1};

)；

solution4_Sum<100>::N就是1+2+...+100的結(jié)果。當(dāng)編譯

器看到solution4_Sum<100>時，就是為模板類solution4_Sum

以參數(shù)100生成該類型的代碼。但以100為參數(shù)

的類型需要得到以99為參數(shù)的類型，因?yàn)?/p>

solution4_Sum<100>::N=solution4_Sum<99>::N+100o這個過程會遞

歸一直到參數(shù)為1的類型，由于該類型已經(jīng)顯式

定義，編譯器無需生成，遞歸編譯到此結(jié)束。由

于這個過程是在編譯過程中完成的，因此要求輸

入n必須是在編譯期間就能確定，不能動態(tài)輸

入。這是該方法最大的缺點(diǎn)。而且編譯器對遞歸

編譯代碼的遞歸深度是有限制的，也就是要求n

不能太大。

大家還有更多、更巧妙的思路嗎？歡迎討論人)

(09)一查找鏈表中倒數(shù)第k個結(jié)點(diǎn)

題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第

k個結(jié)點(diǎn)。鏈表的倒數(shù)第0個結(jié)點(diǎn)為鏈表的尾指

針。鏈表結(jié)點(diǎn)定義如下：

structListNode

{

intm__nKey;

ListNode*m_j>Next;

}；

資料僅供參考

分析：為了得到倒數(shù)第k個結(jié)點(diǎn)，很自然的想法

是先走到鏈表的尾端，再從尾端回溯k步?？墒?/p>

輸入的是單向鏈表，只有從前往后的指針而沒有

從后往前的指針。因此我們需要打開我們的思

路。

既然不能從尾結(jié)點(diǎn)開始遍歷這個鏈表，我們還是

把思路回到頭結(jié)點(diǎn)上來。假設(shè)整個鏈表有n個結(jié)

點(diǎn)，那么倒數(shù)第k個結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第

n-k-1個結(jié)點(diǎn)(從0開始計(jì)數(shù))。如果我們能夠

得到鏈表中結(jié)點(diǎn)的個數(shù)n,那我們只要從頭結(jié)點(diǎn)

開始往后走n?k-1步就能夠了。如何得到結(jié)點(diǎn)數(shù)

n?這個不難，只需要從頭開始遍歷鏈表，每經(jīng)

過一個結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。

這種思路的時間復(fù)雜度是0(n),但需要遍歷鏈

表兩次。第一次得到鏈表中結(jié)點(diǎn)個數(shù)n,第二次

得到從頭結(jié)點(diǎn)開始的第n-k-1個結(jié)點(diǎn)即倒數(shù)第k

個結(jié)點(diǎn)。

如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。

但如果輸入的鏈表的結(jié)點(diǎn)個數(shù)很多，有可能不能

一次性把整個鏈表都從硬盤讀入物理內(nèi)存，那么

遍歷兩遍意味著一個結(jié)點(diǎn)需要兩次從硬盤讀入

到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存

資料僅供參考

是非常耗時間的操作。我們能不能把鏈表遍歷的

次數(shù)減少到1?如果能夠，將能有效地提高代碼

執(zhí)行的時間效率。

如果我們在遍歷時維持兩個指針，第一個指針從

鏈表的頭指針開始遍歷，在第k?1步之前，第二

個指針保持不動；在第k?1步開始，第二個指針

也開始從鏈表的頭指針開始遍歷。由于兩個指針

的距離保持在k1,當(dāng)?shù)谝粋€(走在前面的)指

針到達(dá)鏈表的尾結(jié)點(diǎn)時，第二個指針(走在后面

的)指針正好是倒數(shù)第k個結(jié)點(diǎn)。

這種思路只需要遍歷鏈表一次。對于很長的鏈

表，只需要把每個結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。

因此這一方法的時間效率前面的方法要高。

思路一的參考代碼：

/////////////////////////////////////////////////////////////////////

//

//Findthekthnodefromthetailofalist

//Input:pListHead-theheadoflist

//k-thedistancetothetail

//Output:thekthnodefromthetailofalist