程序員面試題精選100題

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

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

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

比如將二元查找樹

10

/\

614

/\/\

481216

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

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

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

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

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

成一個排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點(左子樹的最

大結(jié)點)、當(dāng)前結(jié)點和右子鏈表的最左結(jié)點(右子樹的最小結(jié)點)。從樹的根結(jié)點開始遞歸調(diào)整所有結(jié)

點。

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

一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當(dāng)前結(jié)點的指針將其鏈

接到鏈表的末尾。當(dāng)所有結(jié)點都訪問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。

參考代碼：

首先我們定義二元查找樹結(jié)點的數(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*pNode,boolasRight)

{

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_pRight=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_pRight)

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

//pLastNodeInList-thetailofthedouble-linkedlist

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

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)

pLastNodeInList->m_pRight=pCurrent;

pLastNodelnList=pCurrent;

//Converttherightsub-tree

if(pCurrent->m_pRight!=NULL)

ConvertNode(pCurrent->m_pRightzpLastNodelnList);

}

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

//Covertabinarysearchtreeintoasorteddouble-linkedlist

//Input:pHeadOfTree-theheadoftree

//Output:theheadofsorteddouble-linkedlist

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

BSTreeNode*Convert_Solutionl(BSTreeNode*pHeadOfTree)

{

BSTreeNode*pLastNodeInList=NULL;

ConvertNode(pHeadOfTree,pLastNodelnList);

//Gettheheadofthedouble-linkedlist

BSTreeNode*pHeadOfList=pLastNodelnList;

while(pHeadOfList&&pHeadOfList->m_pLeft)

pHeadOfList=pHeadOfList->m_pLeft;

returnpHeadOfList;

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

題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及

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

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

我看到這道題目時，第一反應(yīng)就是每次push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素

將是最小元素。但由于不能保證最后push進棧的元素最先出棧，這種思路設(shè)計的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一

個棧了。

在棧里添加一個成員變量存放最小元素(或最小元素的位置)。每次push一個新元素進棧的時候，如

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

乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果當(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_minIndex;//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__minIndex

if(m_minIndex.size()==0)

m_minIndex.push_back(0);

else

(

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

m_minIndex.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_minIndex

m_minIndex.pop_back();

}

//gettheminimumelementofstack

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

(

assert(m_data.size()>0);

assert(m_minlnciex.size()>0);

returnm_data[m_minlndex.back()];

}

舉個例子演示上述代碼的運行過程:

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

1.push3303

2.push43,4ozo3

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

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

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

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

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

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

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

總之，在面試時如果時間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個小亮點就能讓自己輕松

拿到心儀的Offer。

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

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

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

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

18。

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

在內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2006年程序

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

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

n的數(shù)組有0(r)個子數(shù)組；而且求一個長度為n的數(shù)組的和的時間復(fù)雜度為0(n)。因此這種思路的時

間是。(的。

很容易理解，當(dāng)我們加上一個正數(shù)時，和會增加；當(dāng)我們加上一個負數(shù)時，和會減少。如果當(dāng)前得到的

和是個負數(shù)，那么這個和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個負數(shù)將會減少接下來的

和?；谶@樣的思路，我們可以寫出如下代碼。

參考代碼：

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

//Findthegreatestsumofallsub-arrays

//Returnvalue:iftheinputisvalid,returntruerotherwisereturnfalse

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

boolFindGreatestSumOfSubArray

(

int*pData,//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;

)

討論：上述代碼中有兩點值得和大家討論一下：

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

子數(shù)組和的最大值，那么當(dāng)輸入一個空指針是應(yīng)該返回什么呢？返回0?那這個函數(shù)的用戶怎么區(qū)分輸

入無效和子數(shù)組和的最大值剛好是。這兩中情況呢？基于這個考慮，本人認為把子數(shù)組和的最大值以引

用的方式放到參數(shù)列表中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標志。

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

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

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

題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一

條路徑。打印出和與輸入整數(shù)相等的所有路徑。

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

10

/\

512

/\

47

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

二元樹結(jié)點的數(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é)點時，把該結(jié)點添加到路徑上，并累加當(dāng)前結(jié)點的值。如果當(dāng)前結(jié)點為葉結(jié)點并且當(dāng)前

路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來。如果當(dāng)前結(jié)點不是葉結(jié)點，

則繼續(xù)訪問它的子結(jié)點。當(dāng)前結(jié)點訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點。因此我們在函數(shù)退出之前

要在路徑上刪除當(dāng)前結(jié)點并減去當(dāng)前結(jié)點的值，以確保返回父結(jié)點時路徑剛好是根結(jié)點到父結(jié)點的路

徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實際上是一個棧結(jié)構(gòu)，因為路徑要與遞歸調(diào)用狀態(tài)一致，而遞歸

調(diào)用本質(zhì)就是一個壓棧和出棧的過程。

參考代碼：

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

//Findpathswhosesumequaltoexpectedsum

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

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<<'\tf;

std::cout<<std::endl;

)

//ifthenodeisnotaleaf,gotoitschildren

if(pTreeNode->m_pLeft)

FindPath(pTreeNode->m_pLeftzexpectedSum,path,currentSum);

if(pTreeNode->m_pRight)

FindPath(pTreeNode->m_pRightzexpectedSum,path,currentSum);

//whenwefinishvisitinganodeandreturntoitsparentnode,

//weshoulddeletethisnodefromthepathand

//minusthenode1svaluefromthecurrentsum

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(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ù)。這種思路相當(dāng)于只要排序k個整數(shù)，因此時間復(fù)雜可以降到O(n+n【ogk)。

通常情況下k要遠小于n,所以這種辦法要優(yōu)于前面的思路。

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

碼寫得更漂亮一些。從上面的分析，當(dāng)長度為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的好印象，何樂而不為之？

參考代碼：

#include<set>

#include<vector>

#include<iostream>

usingnamespacestd;

typedefmultiset<intzgreater<int>>IntHeap;

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

//findkleastnumbersinavector

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

voidFindKLeastNumbers

(

constvector<int>&data,//avectorofdata

IntHeap&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

IntHeap::iteratoriterFirst=leastNumbers.begin();

//ifislessthanthepreviousgreatestnumber

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

{

//replacethepreviousgreatestnumber

leastNumbers.erase(iterFirst);

leastNumbers.insert(*iter);

}

)

)

}

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

題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(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é)點小的元素都

應(yīng)該位于序列的左半部分；從第一個大于跟結(jié)點開始到跟結(jié)點前面的一個元素為止，所有元素都應(yīng)該大

于跟結(jié)點，因為這部分元素對應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞

歸地確認序列的左、右兩部分是不是都是二元查找樹。

參考代碼：

usingnamespacestd;

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

//Verifywhetherasquenceofintegersarethepostordertraversal

//ofabinarysearchtree(BST)

//Input:squence-thesquenceofintegers

//length-thelengthofsquence

//Return:returntureifthesquenceistraversalresultofaBST,

//otherwise,returnfalse

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

boolverifySquenceOfBST(intsquence[]zintlength)

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+izlength-i-1);

return(left&&right);

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

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

開。為簡單起見，標點符號和普通字母一樣處理。

例如輸入“l(fā)amastudent.M,則輸出“student,aam\"。

分析：由于編寫字符串相關(guān)代碼能夠反映程序員的編程能力和編程習(xí)慣，與字符串相關(guān)的問題一直是程

序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。

由于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所有字符。這時，不但翻轉(zhuǎn)了句子中單詞的順序，而且單

詞內(nèi)字符也被翻轉(zhuǎn)了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和

輸入時的順序保持一致。

還是以上面的輸入為例子。翻轉(zhuǎn)"Iamastudent.”中所有字符得到”.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;

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--;

//Reversethewholesentence

Reverse(pBegin,pEnd);

//Reverseeverywordinthesentence

pBegin=pEnd=pData;

while(*pBegin!=1\0')

(

if(*pBegin==1')

(

pBegin++;

pEnd++;

continue;

//AwordisbetweenwithpBeginandpEnd,reverseit

elseif(*pEnd=='*||*pEnd==1\0*)

(

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

分析：這道題沒有多少實際意義，因為在軟件開發(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)不允許使用這兩種語句了。

我們?nèi)匀粐@循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達到這

個效果。比如定義一個類，我們new—含有n個這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會被

調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個思路：

classTemp

{

public:

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

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

staticintGetSum(){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(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*Array[2];

classA

{

public:

virtualintSum(intn){return0;}

)；

classB:publicA

{

public:

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

)；

intsolution2_Sum(intn)

{

Aa;

Bb;

Array[0]=&a;

Array[1]=&b;

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

returnvalue;

)

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

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

typedefint(*fun)(int);

intsolution3_fl(inti)

{

return0;

)

intsolution3_f2(inti)

{

funf[2]={solution3_flzsolution3_f2};

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

}

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

template<intn>structsolution4_Sum

{

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

）；

template<>structsolution4_Sum<l>

（

enumValue{N=1};

）；

solution4_Sum<l00>::N就是1+2+...+100的結(jié)果。當(dāng)編譯器看到solution4_Sum<100>IFj",就是為

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

因為solution4_Sum<100>::N=solution4_Sum<99>::N+100?這個過程會遞歸一直到參數(shù)為

1的類型，由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸編譯到此結(jié)束。由于這個過程是在編譯過

程中完成的，因此要求輸入n必須是在編譯期間就能確定，不能動態(tài)輸入。這是該方法最大的缺點。而

且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。

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

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

題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈

表結(jié)點定義如卜：

structListNode

{

intm_nKey;

ListNode*m_pNext;

）；

分析：為了得到倒數(shù)第k個結(jié)點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步?？墒禽斎氲?/p>

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

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

么倒數(shù)第k個結(jié)點是從頭結(jié)點開始的第n-k-1個結(jié)點（從0開始計數(shù)）。如果我們能夠得到鏈表中結(jié)點

的個數(shù)n,那我們只要從頭結(jié)點開始往后走n-k-1步就可以了。如何得到結(jié)點數(shù)n?這個不難，只需要從

頭開始遍歷鏈表，每經(jīng)過一個結(jié)點，計數(shù)器加一就行了。

這種思路的時間復(fù)雜度是。（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步之前，第二個指針

保持不動；在第k-1步開始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在

k-1,當(dāng)?shù)谝粋€（走在前面的）指針到達鏈表的尾結(jié)點時，第二個指針（走在后面的）指針正好是倒數(shù)第

k個結(jié)點。

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

方法的時間效率前面的方法要高。

思路一的參考代碼：

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

//Findthekthnodefromthetailofalist

//Input:pListHead-theheadoflist

//kthedistancetothetail

//Output:thekthnodefromthetailofalist

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

ListNode*FindKthToTail_Solutionl(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

//Input:pListHead-theheadoflist

//kthedistancetothetail

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

//ifthenumberofnodesinthelistislessthankz

//donothing

returnNULL;

}

}

pBehind=pListHead;

//thedistancebetweenpAheadandpBehindisk

//whenpAheadarrivesatthetail,p

//Behindisatthekthnodefromthetail

while(pAhead->m_pNext!=NULL)

(

pAhead=pAhead->m_pNext;

pBehind=pBehind->m_pNext;

)

returnpBehind;

)

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

個公司都希望程序員在操作指針時有良好的習(xí)慣，比如使用指針之前判斷是不是空指針。這些都是編程

的細節(jié)，但如果這些細節(jié)把握得不好，很有可能就會和心儀的公司失之交臂。

另外，這兩種思路對應(yīng)的代碼都含有循環(huán)。含有循環(huán)的代碼經(jīng)