程序員面試的58個(gè)經(jīng)典算法

程序員面試題精選(01)一把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)

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

比如將二元查找樹

10

//

614

1111

481216

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

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

分析：本題是微軟的面試題。很多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不

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

思路一：當(dāng)我們到達(dá)某一結(jié)點(diǎn)準(zhǔn)備調(diào)整以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹時(shí)，先調(diào)整其左子樹將

左子樹轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(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)。

思路二：我們可以中序遍歷整棵樹。按照這個(gè)方式遍歷樹，比較小的結(jié)點(diǎn)先訪問。如果

我們每訪問一個(gè)結(jié)點(diǎn)，假設(shè)之前訪問過的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整

當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪問過之后，整棵樹也就轉(zhuǎn)換成一個(gè)

排序雙向鏈表了。

參考代碼：

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

structBSTreeNode//anodeinthebinarysearchtree

(

intm_nValue;//valueofnode

BSTreeNode*m_pLeft;//leftchildofnode

BSTreeNode*m_pRight;//rightchildofnode

)；

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

/////〃〃〃〃〃///〃〃〃〃///〃〃〃〃//////〃〃〃/////〃〃〃///////〃〃

IICovertasubbinary-search-treeintoasorteddouble-linkedlist

//Input:pNode-theheadofthesubtree

//asRight-whetherpNodeistherightchildofitsparent

//Output:ifasRightistrue,returntheleastnodeinthesub-tree

//elsereturnthegreatestnodeinthesub-tree

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

BSTreeNode*ConvertNode(BSTreeNode*pNode,boolasRight)

(

if(!pNode)

returnNULL;

BSTreeNode*pLeft=NULL;

BSTreeNode*pRight=NULL;

//Converttheleftsub-tree

if(pNode->m_pLeft)

pLeft=ConvertNode(pNode->m_pLeft,false);

//Connectthegreatestnodeintheleftsub-treetothecurrentnode

if(pLeft)

{

pLeft->m_pRight=pNode;

pNode->m_pLeft=pLeft;

}

//Converttherightsub-tree

if(pNode->m_pRight)

pRight=ConvertNode(pNode->m_pRight,true);

//Connecttheleastnodeintherightsub-treetothecurrentnode

if(pRight)

(

pNode->m_pRight=pRight;

pRight->m_pLeft=pNode;

)

BSTreeNode*pTemp=pNode;

//Ifthecurrentnodeistherightchildofitsparent,

//returntheleastnodeinthetreewhoserootisthecurrentnode

if(asRight)

while(pTemp->m_pLeft)

pTemp=pTemp->m_pLeft;

}

11Ifthecurrentnodeistheleftchildofitsparent,

//returnthegreatestnodeinthetreewhoserootisthecurrentnode

else

{

while(pTemp->m_pRight)

pTemp=pTemp->m_pRight;

)

returnpTemp;

)

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

IICovertabinarysearchtreeintoasorteddouble-linkedlist

//Input:theheadoftree

//Output:theheadofsorteddouble-linkedlist

//〃〃〃/〃〃/〃/〃〃〃/〃〃〃〃〃/〃/〃///〃〃〃/〃〃〃〃〃///〃/〃/〃

BSTreeNode*Convert(BSTreeNode*pHeadOfTree)

(

//Aswewanttoreturntheheadofthesorteddouble-linkedlist,

//wesetthesecondparametertobetrue

returnConvertNode(pHeadOfTree,true);

)

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

/〃〃/〃〃〃/〃////〃〃〃/〃〃//〃〃///////〃/〃〃//〃〃〃〃////////〃/

//Covertasubbinary-search-treeintoasorteddouble-linkedlist

//Input:pNode-theheadofthesubtree

//pLastNodelnList-thetailofthedouble-linkedlist

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

voidConvertNode(BSTreeNode*pNode,BSTreeNode*&pLastNodelnList)

(

if(pNode==NULL)

return;

BSTreeNode*pCurrent=pNode;

//Converttheleftsub-tree

if(pCurrent->m_pLeft!=NULL)

ConvertNode(pCurrent->m_pLeft,pLastNodelnList);

//Putthecurrentnodeintothedouble-linkedlist

pCurrent->m_pLeft=pLastNodelnList;

if(pLastNodelnList!=NULL)

pLastNodelnList->m_pRight=pCurrent;

pLastNodelnList=pCurrent;

//Converttherightsub-tree

if(pCurrent->m_pRight!=NULL)

ConvertNode(pCurrent->m_pRight,pLastNodelnList);

)

////〃〃//〃///〃/〃〃〃/〃/〃〃〃/〃//////〃〃〃〃///〃〃/////////〃〃

//Covertabinarysearchtreeintoasorteddouble-linkedlist

//Input:pHeadOfTree-theheadoftree

//Output:theheadofsorteddouble-linkedlist

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

BSTreeNode*Convert_Solution1(BSTreeNode*pHeadOfTree)

(

BSTreeNode*pLastNodelnList=NULL;

ConvertNode(pHeadOfTree,pLastNodelnList);

//Gettheheadofthedouble-linkedlist

BSTreeNode*pHeadOfList=pLastNodelnList;

while(pHeadOfList&&pHeadOfList->m_pLeft)

pHeadOfList=pHeadOfList->m_pLeft;

returnpHeadOfList;

)

程序員面試題精選（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è)成員變量存放最小元素（或最小元素的位置）。每次push一個(gè)新元素進(jìn)棧

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

乍一看這樣思路挺好的。但仔細(xì)一想，該思路存在一個(gè)重要的問題：如果當(dāng)前最小元素被

pop出去，如何才能得到下一個(gè)最小元素？

因此僅僅只添加一個(gè)成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個(gè)

輔助棧。每次push一個(gè)新元素的時(shí)候，同時(shí)將最小元素（或最小元素的位置。考慮到棧元

素的類型可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能減少空間消耗）push到輔助棧中；

每次pop一個(gè)元素出棧的時(shí)候，同時(shí).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_minlndex

if(m_minlndex.size()==0)

m_minlndex.push_back(O);

else

{

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

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

else

m_minlndex.push_back(m_minlndex.back());

}

)

//ereasetheelementattheendofstack

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

{

//popm__data

m_data.pop_back();

//popm_minlndex

m_minlndex.pop_back();

)

//gettheminimumelementofstack

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

(

assert(m_data.size()>0);

assert(m_minlndex.size()>0);

returnm_data[m_minlndex.back()];

)

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

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

l.push3303

2.push43,40,03

3.push23,4,20,0,22

4.push13,4,2,10,0,2,31

5.pop3,4,20,0,22

6.pop3,40,03

7.push03,4,00,0,20

討論：如果思路正確，編寫上述代碼不是一件很難的事情。但如果能注意一些細(xì)節(jié)無疑能在

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

??????????用模板類實(shí)現(xiàn)。如果別人的元素類型只是Mt類型，模板將能給面試官帶來好

印象；

??????????兩個(gè)版本的top函數(shù)。在很多類中，都需要提供const和非const版本的成員

訪問函數(shù)；

??????????min函數(shù)中assert.,把代碼寫的盡量安全是每個(gè)軟件公司對(duì)程序員的要求；

??????????添加一些注釋。注釋既能提高代碼的可讀性，又能增加代碼量，何樂而不為？

總之，在面試時(shí)如果時(shí)間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個(gè)小亮點(diǎn)就能

讓自己輕松拿到心儀的Offer。

程序員面試題精選(03)一求子數(shù)組的最大和

題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)

子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為0(n)。

例如輸入的數(shù)組為1,-2,3,10,-4,7,2,-5,和最大的子數(shù)組為3,10,-4,7,2,因此輸出為

該子數(shù)組的和18o

分析：本題最初為2005年浙江大學(xué)計(jì)算機(jī)系的考研題的最后一道程序設(shè)計(jì)題，在2006年

里包括google在內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本

題也順利成為2006年程序員面試題中經(jīng)典中的經(jīng)典。

如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是,

由于長(zhǎng)度為n的數(shù)組有O(n2)個(gè)子數(shù)組；而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為

O(n)o因此這種思路的時(shí)間是0(n3)?

很容易理解，當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果

當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)

負(fù)數(shù)將會(huì)減少接下來的和。基于這樣的思路，我們可以寫出如下代碼。

參考代碼：

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

IIFindthegreatestsumofallsub-arrays

//Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

boolFindGreatestSumOfSubArray

(

int*pData,//anarray

unsignedintnLength,11thelengthofarray

int&nGreatestSum//thegreatestsumofallsub-arrays

)

{

//iftheinputisinvalid,returnfalse

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

returnfalse;

intnCurSum=nGreatestSum=0;

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

(

nCurSum+=pData;

//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>nGreatestSum)

nGreatestSum=pData;

)

)

returntrue;

}

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

??????????函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如

果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回0?

那這個(gè)函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是。這兩中情況呢？基于這

個(gè)考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)

函數(shù)是否正常執(zhí)行的標(biāo)志。

??????????輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時(shí)，子數(shù)

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

程序員面試題精選(04)一在二元樹中找出和為某一值的所有路徑

題目：輸入一個(gè)整數(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

);

分析：這是百度的一道筆試題，考查對(duì)樹這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。

當(dāng)訪問到某一結(jié)點(diǎn)時(shí)，把該結(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ù)將自動(dòng)回

到父結(jié)點(diǎn)。因此我們?cè)诤瘮?shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保

返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上

是一個(gè)棧結(jié)構(gòu)，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過

程。

參考代碼：

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

IIFindpathswhosesumequaltoexpectedsum

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

voidFindPath

(

BinaryTreeNode*pTreeNode,//anodeofbinarytree

intexpectedSum,//theexpectedsum

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

int¤tSum//thesumofpath

)

{

if(ipTreeNode)

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?7t';

std::cout?std::endl;

)

//ifthenodeisnotaleaf,gotoitschildren

if(pTreeNode->m_pLeft)

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

if(pTreeNode->m_pRight)

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

//whenwefinishvisitinganodeandreturntoitsparentnode,

//weshoulddeletethisnodefromthepathand

//minusthenode'svaluefromthecurrentsum

currentSum-=pTreeNode->m_nValue;

path.pop_back();

)

程序員面試題精選(05)一查找最小的k個(gè)元素

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

例如輸入1,2,3,4,5,6,7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1,2,3和4。

分析：這道題最簡(jiǎn)單的思路莫過于把輸入的n個(gè)整數(shù)排序，這樣排在最前面的k個(gè)數(shù)就是

最小的k個(gè)數(shù)。只是這種思路的時(shí)間復(fù)雜度為O(nlogn)。我們?cè)囍鴮ふ腋斓慕鉀Q思路。

我們可以開辟一個(gè)長(zhǎng)度為k的數(shù)組。每次從輸入的n個(gè)整數(shù)中讀入一個(gè)數(shù).如果數(shù)組中已

經(jīng)插入的元素少于k個(gè)，則將讀入的整數(shù)直接放到數(shù)組中。否則長(zhǎng)度為k的數(shù)組已經(jīng)滿了，

不能再往數(shù)組里插入元素，只能替換了。如果讀入的這個(gè)整數(shù)比數(shù)組中已有k個(gè)整數(shù)的最大

值要小，則用讀入的這個(gè)整數(shù)替換這個(gè)最大值；如果讀入的整數(shù)比數(shù)組中已有k個(gè)整數(shù)的最

大值還要大，則讀入的這個(gè)整數(shù)不可能是最小的k個(gè)整數(shù)之一，拋棄這個(gè)整數(shù)。這種思路相

當(dāng)于只要排序k個(gè)整數(shù)，因此時(shí)間復(fù)雜可以降到O(n+nlogk)。通常情況下k要遠(yuǎn)小于n,所

以這種辦法要優(yōu)于前面的思路。

這是我能夠想出來的最快的解決方案。不過從給面試官留下更好印象的角度出發(fā)，我們可以

進(jìn)一步把代碼寫得更漂亮一些。從上面的分析，當(dāng)長(zhǎng)度為k的數(shù)組已經(jīng)滿了之后，如果需要

替換，每次替換的都是數(shù)組中的最大值。在常用的數(shù)據(jù)結(jié)構(gòu)中，能夠在0(1)時(shí)間里得到最

大值的數(shù)據(jù)結(jié)構(gòu)為最大堆。因此我們可以用堆(heap)來代替數(shù)組。

另外，自己重頭開始寫一個(gè)最大堆需要一定量的代碼。我們現(xiàn)在不需要重新去發(fā)明車輪，因

為前人早就發(fā)明出來了。同樣，STL中的set和multiset為我們做了很好的堆的實(shí)現(xiàn)，我們

可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印象，何樂而不為之？

參考代碼：

#include<set>

#include<vector>

/include<iostream>

usingnamespacestd;

typedefmultiset<int,greater<int>>IntHeap;

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

//findkleastnumbersinavector

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

voidFindKLeastNumbers

(

constvector<int>&data,//avectorofdata

lntHeap&leastNumbers,//kleastnumbers,output

unsignedintk

)

(

leastNumbers.clear();

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

return;

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

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

(

//iflessthanknumberswasinsertedintoleastNumbers

if((leastNumbers.size())<k)

leastNumbers.insert(*iter);

//leastNumberscontainsknumbersandit*sfullnow

else

{

//firstnumberinleastNumbersisthegreatestone

lntHeap::iteratoriterFirst=leastNumbers.begin();

//ifislessthanthepreviousgreatestnumber

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

(

//replacethepreviousgreatestnumber

leastNumbers.erase(iterFirst);

leastNumbers.insert(*iter);

)

)

)

)

程序員面試題精選(06)一判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果

題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回

true,否則返回false。例如輸入5、7、6、9、11、10、8,由于這一整數(shù)序列是如下樹的

后序遍歷結(jié)果：

8

//

610

////

57911

因此返回true。

如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。

分析：這是一道trilogy的筆試題，主要考查對(duì)二元查找樹的理解。

在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹的根結(jié)點(diǎn)。從頭開始掃描這個(gè)序列，比根結(jié)點(diǎn)

小的元素都應(yīng)該位于序列的左半部分;從第一個(gè)大于跟結(jié)點(diǎn)開始到跟結(jié)點(diǎn)前面的一個(gè)元素為

止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹的右子樹。根據(jù)這樣的劃分,

把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。

參考代碼：

usingnamespacestd;

/〃//〃/〃〃/〃//〃〃〃/〃〃〃〃〃〃〃〃//〃/〃〃〃〃〃〃///〃〃///〃〃

//Verifywhetherasquenceofintegersarethepostordertraversal

//ofabinarysearchtree(BST)

//Input:squence-thesquenceofintegers

//length-thelengthofsquence

//Return:returntureifthesquenceistraversalresultofaBST,

IIotherwise,returnfalse

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

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>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)句子中單詞的順序

題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞

以空格符隔開。為簡(jiǎn)單起見，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。

例如輸入"Iamastudent.",則輸出"student.aamI",

分析：由于編寫字符串相關(guān)代碼能夠反映程序員的編程能力和編程習(xí)慣，與字符串相關(guā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"，正是符合要求的輸出。

參考代碼：

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

IIReverseastringbetweentwopointers

//Input:pBegin-thebeginpointerinastring

//pEnd-theendpointerinastring

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

voidReverse(char*pBegin,char*pEnd)

(

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

return;

while(pBegin<pEnd)

chartemp=*pBegin;

*pBegin=*pEnd;

*pEnd=temp;

pBegin++,pEnd

}

)

/〃///〃〃/〃/〃/〃〃//〃///〃/〃〃〃//////〃〃/〃///〃/〃〃///////〃〃

//Reversethewordorderinasentence,butmaintainthecharacter

//orderinsideaword

//Input:pData-thesentencetobereversed

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

char*ReverseSentence(char*pData)

(

if(pData==NULL)

returnNULL;

char*pBegin=pData;

char*pEnd=pData;

while(*pEnd!=70')

pEnd++;

pEnd-;

//Reversethewholesentence

Reverse(pBegin,pEnd);

//Reverseeverywordinthesentence

pBegin=pEnd=pData;

while(*pBegin!=70')

(

if(*pBegin=='')

{

pBegin++;

pEnd++;

continue;

)

//AwordisbetweenwithpBeginandpEnd,reverseit

elseif(*pEnd=="||*pEnd==701)

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)。

分析：這道題沒有多少實(shí)際意義，因?yàn)樵谲浖_發(fā)中不會(huì)有這么變態(tài)的限制。但這道題卻能

有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對(duì)編程相關(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達(dá)到這個(gè)效果。比如定義一個(gè)類，我們new—含有n個(gè)這種類型元素的數(shù)組，那么該

類的構(gòu)造函數(shù)將確定會(huì)被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代

碼正是基于這個(gè)思路：

classTemp

(

public:

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=newTemp[n];

delete[]a;

a=0;

returnTemp::GetSum();

)

我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應(yīng)該終止遞歸，我們不妨定義兩個(gè)函

數(shù)。一個(gè)函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個(gè)函數(shù)處理終止遞歸的情況，我們需要做的就是在

兩個(gè)函數(shù)里二選一。從二選一我們很自然的想到布爾變量，比如ture(1)的時(shí)候調(diào)用第一

個(gè)函數(shù)，false(0)的時(shí)候調(diào)用第二個(gè)函數(shù)。那現(xiàn)在的問題是如和把數(shù)值變量n轉(zhuǎn)換成布爾

值。如果對(duì)n連續(xù)做兩次反運(yùn)算，即!!n,那么非零的n轉(zhuǎn)換為true,0轉(zhuǎn)換為false。有了

上述分析，我們?cè)賮砜聪旅娴拇a：

classA;

A*Array[2];

classA

{

public:

virtualintSum(intn){return0;}

)；

classB:publicA

{

public:

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

);

intsolution2_Sum(intn)

(

Aa;

Bb;

Array[O]=&a;

Array[1]=&b;

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

returnvalue;

)

這種方法是用虛函數(shù)來實(shí)現(xiàn)函數(shù)的選擇。當(dāng)n不為零時(shí)，執(zhí)行函數(shù)B::Sum；當(dāng)n為。時(shí),

執(zhí)行A::Sum。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：

typedefint(*fun)(int);

intsolution3_f1(inti)

(

return0;

)

intsolution3_f2(inti)

{

funf[2]={solution3_f1,solution3_f2};

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

)

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

template<intn>structsolution4_Sum

{

enumValue{N=solution4_Sum<n-1>::N+n};

)；

template<>structsolution4_Sum<1>

(

enumValue{N=1};

);

solutior)4_Sum<100>::N就是1+2+...+100的結(jié)果。當(dāng)編譯器看至I]solution4_Sum<100>時(shí)，

就是為模板類solution4_Sum以參數(shù)100生成該類型的代碼。但以100為參數(shù)的類型需要

得到以99為參數(shù)的類型，因?yàn)閟olution4_Sum<100>::N=solution4_Sum<99>::N+100。這

個(gè)過程會(huì)遞歸一直到參數(shù)為1的類型，由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸

編譯到此結(jié)束。由于這個(gè)過程是在編譯過程中完成的，因此要求輸入n必須是在編譯期間

就能確定，不能動(dòng)態(tài)輸入。這是該方法最大的缺點(diǎn)。而且編譯器對(duì)遞歸編譯代碼的遞歸深度

是有限制的，也就是要求n不能太大。

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

程序員面試題精選(09)一查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表

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

(

intm_nKey;

ListNode*m_pNext;

)；

分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。

可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我

們的思路。

既然不能從尾結(jié)點(diǎn)開始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來。假設(shè)整個(gè)鏈表有n

個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)(從0開始計(jì)數(shù))。如果我

們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù)n,那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。如何

得到結(jié)點(diǎn)數(shù)n?這個(gè)不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。

這種思路的時(shí)間復(fù)雜度是0(n),但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點(diǎn)個(gè)數(shù)n,第

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

如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點(diǎn)個(gè)數(shù)很多，有可能

不能一次性把整個(gè)鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個(gè)結(jié)點(diǎn)需要兩次從硬

盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時(shí)間的操作。我們能不能把

鏈表遍歷的次數(shù)減少到1?如果可以，將能有效地提高代碼執(zhí)行的時(shí)間效率。

如果我們?cè)诒闅v時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第k-1步之前,

第二個(gè)指針保持不動(dòng)；在第k-1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。由于

兩個(gè)指針的距離保持在k-1,當(dāng)?shù)谝粋€(gè)(走在前面的)指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指

針(走在后面的)指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。

這種思路只需要遍歷鏈表一次。對(duì)于很長(zhǎng)的鏈表，只需要把每個(gè)結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。

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

思路一的參考代碼：

/////〃//////////〃/〃//////〃/〃//〃/////〃////〃///〃////〃/////〃///

//Findthekthnodefromthetailofalist

//Input:pListHead-theheadoflist

//k-thedistancetothetail

//Output:thekthnodefromthetailofalist

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

ListNode*FindKthToTail_Solution1(ListNode*pListHead,unsignedintk)

if(pListHead==NULL)

returnNULL;

//countthenodesnumberinthelist

ListNode*pCur=pListHead;

unsignedintnNum=0;

while(pCur->m_pNext!=NULL)

(

pCur=pCur->m_pNext;

nNum++;

)

//ifthenumberofnodesinthelistislessthank

//donothing

if(nNum<k)

returnNULL;

//thekthnodefromthetailofalist

//isthe(n-k)thnodefromthehead

pCur=pListHead;

for(unsignedinti=0;i<nNum-k;++i)

pCur=pCur->m_pNext;

returnpCur;

)

思路二的參考代碼：

〃//〃〃/〃〃〃〃/〃〃/〃〃/〃〃//〃〃〃/〃〃〃〃〃〃〃〃/〃〃〃/〃/〃/

//Findthekthnodefromthetailofalist

IIInput:pListHead-theheadoflist

//k-thedistancetothetail

//Output:thekthnodefromthetailofalist

〃///〃/〃//〃〃/〃/〃〃/〃//////〃//〃〃/〃〃/〃〃////〃/〃〃〃〃〃〃/

ListNode*FindKthToTail_Solution2(ListNode*pListHead,unsignedintk)

if(pListHead==NULL)

returnNULL;

ListNode*pAhead=pListHead;

ListNode*pBehind=NULL;

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

(

if(pAhead->m_pNext!=NULL)

pAhead=pAhead->m_pNext;

else

{

//ifthenumberofnodesinthelistislessthank,

//donothing

returnNULL;

)

)

pBehind=pListHead;

//thedistancebetweenpAheadandpBehindisk

//whenpAheadarrivesatthetail,p

//Behindisatthekthnodefromthetail

while(pAhead->m_pNext!=NULL)

(

pAhead=pAhead->m_pNext;

pBehind=pBehind->m_pNext;

}

returnpBehind;

)

討論：這道題的代碼有大量的指針操作。在軟件開發(fā)中，錯(cuò)誤的指針操作是大部分問題的根

源。因此每個(gè)公司都希望程序員在操作指針時(shí)有良好的習(xí)慣，比如使用指針之前判斷是不是

空指針。這些都是編程的細(xì)節(jié)，但如果這些細(xì)節(jié)把握得不好，很有可能就會(huì)和心儀的公司失

之交臂。

另外，這兩種思路對(duì)應(yīng)的代碼都含有循環(huán)。含有循環(huán)的代碼經(jīng)常出的問題是在循環(huán)結(jié)束條件

的判斷。是該用小于還是小于等于？是該用k還是該用k-1?由于題目要求的是從0開始計(jì)

數(shù)，而我們的習(xí)慣思維是從1開始計(jì)數(shù)，因此首先要想好這些邊界條件再開始編寫代碼，

再者要在編寫完代碼之后再用邊界值、邊界值減1、邊界值加1都運(yùn)行一次(在紙上寫代碼

就只能在心里運(yùn)行了)。

擴(kuò)展：和這道題類似的題目還有：輸入一個(gè)單向鏈表。如果該鏈表的結(jié)點(diǎn)數(shù)為奇數(shù)，輸出中

間的結(jié)點(diǎn)；如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，輸出中間兩個(gè)結(jié)點(diǎn)前面的一個(gè)。如果各位感興趣，請(qǐng)自

己分析并編寫代碼0

程序員面試題精選(10)一在排序數(shù)組中查找和為給定值的兩個(gè)數(shù)字

題目：輸入一個(gè)己經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和

正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是0(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，

輸出任意一對(duì)即可。

例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15,因此輸出4和11。

分析：如果我們不考慮時(shí)間復(fù)雜度，最簡(jiǎn)單想法的莫過去先在數(shù)組中固定一個(gè)數(shù)字，再依次

判斷數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字。可惜這種思路需要的時(shí)間復(fù)

雜度是0(n2)。

我們假設(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ù)字往前移動(dòng)，因?yàn)榕旁跀?shù)組前面的數(shù)字要小一

些，它們的和就有可能等于輸入的數(shù)字了。

我們把前面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字

的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng)；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)

字往后移動(dòng)：當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。

問題是這樣的思路是不是正確的呢？這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一

下。

參考代碼：

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

〃Findtwonumberswithasuminasortedarray

//Output:tureisfoundsuchtwonumbers,otherwisefalse

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

boolFindTwoNumbersWithSum

intdata。,//asortedarray

unsignedintlength,//thelengthofthesortedarray

intsum,//thesum

int&num1,//thefirstnumber,output

int&num2//thesecondnumber,output

boolfound=false;

if(length<1)

returnfound;

intahead=length-1;

intbehind=0;

while(ahead>behind)

(

longlongcurSum=data[ahead]+data[behind];

//ifthesumoftwonumbersisequaltotheinput

//wehavefoundthem

if(curSum==sum)

{

num1=data[behind];

num2=data[ahead];

found=true;

break;

)

//ifthesumoftwonumbersisgreaterthantheinput

//decreasethegreaternumber

elseif(curSum>sum)

ahead

//ifthesumoftwonumbersislessthantheinput

//increasethelessnumber

else

behind++;

)

returnfound;

)

擴(kuò)展：如果輸入的數(shù)組是沒有排序的，但知道里面數(shù)字的范圍，其他條件不變，如和在0(n)

時(shí)間里找到這兩個(gè)數(shù)字？

程序員面試題精選(11)一求二元查找樹的鏡像

題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹

的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。例如輸入：

8

//

610

////

57911

輸出：

8

//

106

////

11975

定義二元查找樹的結(jié)點(diǎn)為：

structBSTreeNode//anodeinthebinarysearchtree(BST)

(

intm_nValue;//valueofnode

BSTreeNode*m_pLeft;//leftchildofnode

BSTreeNode*m_pRight;//rightchildofnode

)；

分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就

是交換結(jié)點(diǎn)的左右子樹。我們?cè)囍诒闅v例子中的二元