程序員面試題精選100題

前言隨著高校的連續(xù)擴張，每年應(yīng)屆畢業(yè)生的數(shù)目都在不斷增長，隨著而來的是應(yīng)屆畢業(yè)生的就業(yè)壓力也越來越大。在這樣的背景下，就業(yè)變成一個買方市場的趨勢越來越明顯。為了找到一個稱心的工作，絕大多數(shù)應(yīng)屆畢業(yè)生都必須反復(fù)經(jīng)歷簡歷篩選、電話面試、筆試、面試等環(huán)節(jié)。在這些環(huán)節(jié)中，面試無疑起到最為重要的作用，由于通過面試公司可以最直觀的了解學生的能力。為了有效地準備面試，面經(jīng)這個新興概念應(yīng)運而生。筆者在當初找工作階段也從面經(jīng)中獲益匪淺并最終找到滿意的工作。為了方便后來者，筆者花費大量時間收集并整理散落在茫茫網(wǎng)絡(luò)中的面經(jīng)。不同行業(yè)的面經(jīng)全然不同，筆者從自身專業(yè)出發(fā)，著重關(guān)注程序員面試的面經(jīng)，并從精選出若干具有代表性的技術(shù)類的面試題展開討論，希望能給讀者帶來一些啟發(fā)。由于筆者水平有限，給各面試題提供的思緒和代碼難免會有錯誤，還請讀者批評指正。此外，熱忱歡迎讀者可以提供更多、更好的面試題，本人將感激不盡。(01)把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。規(guī)定不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。比如將二元查找樹

10

/

\

6

14

/

\

/\

4

8

12

16

轉(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é)點（右子樹的最小結(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//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_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;

}

//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*&pLastNodeInList)

{

if(pNode==NULL)

return;

BSTreeNode*pCurrent=pNode;

//Converttheleftsub-tree

if(pCurrent->m_pLeft!=NULL)

ConvertNode(pCurrent->m_pLeft,pLastNodeInList);

//Putthecurrentnodeintothedouble-linkedlist

pCurrent->m_pLeft=pLastNodeInList;

if(pLastNodeInList!=NULL)

pLastNodeInList->m_pRight=pCurrent;

pLastNodeInList=pCurrent;

//Converttherightsub-tree

if(pCurrent->m_pRight!=NULL)

ConvertNode(pCurrent->m_pRight,pLastNodeInList);

}

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

//Covertabinarysearchtreeintoasorteddouble-linkedlist

//Input:pHeadOfTree-theheadoftree

//Output:theheadofsorteddouble-linkedlist

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

BSTreeNode*Convert_Solution1(BSTreeNode*pHeadOfTree)

{

BSTreeNode*pLastNodeInList=NULL;

ConvertNode(pHeadOfTree,pLastNodeInList);

//Gettheheadofthedouble-linkedlist

BSTreeNode*pHeadOfList=pLastNodeInList;

while(pHeadOfList&&pHeadOfList->m_pLeft)

pHeadOfList=pHeadOfList->m_pLeft;

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

題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，規(guī)定添加一個min函數(shù)，可以得到棧的最小元素。規(guī)定函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。分析：這是去年google的一道面試題。我看到這道題目時，第一反映就是每次push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進棧的元素最先出棧，這種思緒設(shè)計的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個棧了。在棧里添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，假如該元素比當前的最小元素還要小，則更新最小元素。乍一看這樣思緒挺好的。但仔細一想，該思緒存在一個重要的問題：假如當前最小元素被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_minIndex.push_back(m_minIndex.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_minIndex.size()>0);

returnm_data[m_minIndex.back()];

}舉個例子演示上述代碼的運營過程：

環(huán)節(jié)

數(shù)據(jù)棧

輔助棧

最小值

1.push3

3

0

3

2.push4

3,4

0,0

3

3.push2

3,4,2

0,0,2

2

4.push1

3,4,2,1

0,0,2,3

1

5.pop

3,4,2

0,0,2

2

6.pop

3,4

0,0

3

7.push0

3,4,0

0,0,2

0討論：假如思緒對的，編寫上述代碼不是一件很難的事情。但假如能注意一些細節(jié)無疑能在面試中加分。比如我在上面的代碼中做了如下的工作：

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

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

min函數(shù)中assert。把代碼寫的盡量安全是每個軟件公司對程序員的規(guī)定；

添加一些注釋。注釋既能提高代碼的可讀性，又能增長代碼量，何樂而不為？總之，在面試時假如時間允許，盡量把代碼寫的美麗一些。說不定代碼中的幾個小亮點就能讓自己輕松拿到心儀的Offer。(03)－求子數(shù)組的最大和

題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。規(guī)定期間復(fù)雜度為O(n)。例如輸入的數(shù)組為1,-2,3,10,-4,7,2,-5，和最大的子數(shù)組為3,10,-4,7,2，因此輸出為該子數(shù)組的和18。分析：本題最初為2023年浙江大學計算機系的考研題的最后一道程序設(shè)計題，在2023年里涉及google在內(nèi)的很多知名公司都把本題當作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2023年程序員面試題中經(jīng)典中的經(jīng)典。假如不考慮時間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。但是非常遺憾的是，由于長度為n的數(shù)組有O(n2)個子數(shù)組；并且求一個長度為n的數(shù)組的和的時間復(fù)雜度為O(n)。因此這種思緒的時間是O(n3)。很容易理解，當我們加上一個正數(shù)時，和會增長；當我們加上一個負數(shù)時，和會減少。假如當前得到的和是個負數(shù)，那么這個和在接下來的累加中應(yīng)當拋棄并重新清零，不然的話這個負數(shù)將會減少接下來的和。基于這樣的思緒，我們可以寫出如下代碼。參考代碼：/////////////////////////////////////////////////////////////////////////////

//Findthegreatestsumofallsub-arrays

//Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse

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

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ù)組和的最大值，那么當輸入一個空指針是應(yīng)當返回什么呢？返回0？那這個函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個考慮，本人認為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標志。

輸入有一類特殊情況需要特殊解決。當輸入數(shù)組中所有整數(shù)都是負數(shù)時，子數(shù)組和的最大值就是數(shù)組中的最大元素。(04)－在二元樹中找出和為某一值的所有途徑

題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所通過的所有結(jié)點形成一條途徑。打印出和與輸入整數(shù)相等的所有途徑。例如輸入整數(shù)22和如下二元樹

10

/

\

5

12

/

\

4

7

則打印出兩條途徑：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ù)的理解。當訪問到某一結(jié)點時，把該結(jié)點添加到途徑上，并累加當前結(jié)點的值。假如當前結(jié)點為葉結(jié)點并且當前程徑的和剛好等于輸入的整數(shù)，則當前的途徑符合規(guī)定，我們把它打印出來。假如當前結(jié)點不是葉結(jié)點，則繼續(xù)訪問它的子結(jié)點。當前結(jié)點訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點。因此我們在函數(shù)退出之前要在途徑上刪除當前結(jié)點并減去當前結(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(!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_pLeft,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(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ù)，因此時間復(fù)雜可以降到O(n+nlogk)。通常情況下k要遠小于n，所以這種辦法要優(yōu)于前面的思緒。這是我可以想出來的最快的解決方案。但是從給面試官留下更好印象的角度出發(fā)，我們可以進一步把代碼寫得更美麗一些。從上面的分析，當長度為k的數(shù)組已經(jīng)滿了之后，假如需要替換，每次替換的都是數(shù)組中的最大值。在常用的數(shù)據(jù)結(jié)構(gòu)中，可以在O(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<int,greater<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

/\/\

579

11因此返回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[],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)字符的順序不變。句子中單詞以空格符隔開。為簡樸起見，標點符號和普通字母同樣解決。例如輸入“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.”中所有字符得到“.tnedutsamaI”，再翻轉(zhuǎn)每個單詞中字符的順序得到“students.aamI”，正是符合規(guī)定的輸出。參考代碼：///////////////////////////////////////////////////////////////////////

//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!='\0')

{

if(*pBegin=='')

{

pBegin++;

pEnd++;

continue;

}

//AwordisbetweenwithpBeginandpEnd,reverseit

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

{

Reverse(pBegin,--pEnd);

pBegin=++pEnd;

}

else

{

pEnd++;

}

}

returnpData;

}(08)－求1+2+...+n題目：求1+2+…+n，規(guī)定不能使用乘除法、for、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達成這個效果。比如定義一個類，我們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;

intsolution1_Sum(intn)

{

Temp::Reset();

Temp*a=newTemp[n];

delete[]a;

a=0;

returnTemp::GetSum();

}我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應(yīng)當終止遞歸，我們不妨定義兩個函數(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*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ù)的選擇。當n不為零時，執(zhí)行函數(shù)B::Sum；當n為0時，執(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);

}此外我們還可以讓編譯器幫我們來完畢類似于遞歸的運算，比如如下代碼：template<intn>structsolution4_Sum

{

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

};template<>structsolution4_Sum<1>

{

enumValue{N=1};

};solution4_Sum<100>::N就是1+2+...+100的結(jié)果。當編譯器看到solution4_Sum<100>時，就是為模板類solution4_Sum以參數(shù)100生成該類型的代碼。但以100為參數(shù)的類型需要得到以99為參數(shù)的類型，由于solution4_Sum<100>::N=solution4_Sum<99>::N+100。這個過程會遞歸一直到參數(shù)為1的類型，由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸編譯到此結(jié)束。由于這個過程是在編譯過程中完畢的，因此規(guī)定輸入n必須是在編譯期間就能擬定，不能動態(tài)輸入。這是該方法最大的缺陷。并且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是規(guī)定n不能太大。大家尚有更多、更巧妙的思緒嗎？歡迎討論^_^(09)－查找鏈表中倒數(shù)第k個結(jié)點題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下：structListNode

{

intm_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ù)n？這個不難，只需要從頭開始遍歷鏈表，每通過一個結(jié)點，計數(shù)器加一就行了。這種思緒的時間復(fù)雜度是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步之前，第二個指針保持不動；在第k-1步開始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1，當?shù)谝粋€（走在前面的）指針到達鏈表的尾結(jié)點時，第二個指針（走在后面的）指針正好是倒數(shù)第k個結(jié)點。這種思緒只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結(jié)點從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時間效率前面的方法要高。思緒一的參考代碼：///////////////////////////////////////////////////////////////////////

//Findthekthnodefromthetailofalist

//Input:pListHead-theheadoflist

//k-thedistancetothetail

//Output:thekthnodefromthetailofalist

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

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

//Input: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ā)中，錯誤的指針操作是大部分問題的根源。因此每個公司都希望程序員在操作指針時有良好的習慣，比如使用指針之前判斷是不是空指針。這些都是編程的細節(jié)，但假如這些細節(jié)把握得不好，很有也許就會和心儀的公司失之交臂。此外，這兩種思緒相應(yīng)的代碼都具有循環(huán)。具有循環(huán)的代碼經(jīng)常出的問題是在循環(huán)結(jié)束條件的判斷。是該用小于還是小于等于？是該用k還是該用k-1？由于題目規(guī)定的是從0開始計數(shù)，而我們的習慣思維是從1開始計數(shù)，因此一方面要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之后再用邊界值、邊界值減1、邊界值加1都運營一次（在紙上寫代碼就只能在心里運營了）。擴展：和這道題類似的題目尚有：輸入一個單向鏈表。假如該鏈表的結(jié)點數(shù)為奇數(shù)，輸出中間的結(jié)點；假如鏈表結(jié)點數(shù)為偶數(shù)，輸出中間兩個結(jié)點前面的一個。假如各位感愛好，請自己分析并編寫代碼。(10)－在排序數(shù)組中查找和為給定值的兩個數(shù)字題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。規(guī)定期間復(fù)雜度是O(n)。假如有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。分析：假如我們不考慮時間復(fù)雜度，最簡樸想法的莫過去先在數(shù)組中固定一個數(shù)字，再依次判斷數(shù)組中剩下的n-1個數(shù)字與它的和是不是等于輸入的數(shù)字?？上н@種思緒需要的時間復(fù)雜度是O(n2)。我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個數(shù)。假如它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個數(shù)字；假如小于輸入的數(shù)字呢？我們希望兩個數(shù)字的和再大一點。由于數(shù)組已經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后面移動一個數(shù)字？由于排在后面的數(shù)字要大一些，那么兩個數(shù)字的和也要大一些，就有也許等于輸入的數(shù)字了；同樣，當兩個數(shù)字的和大于輸入的數(shù)字的時候，我們把較大的數(shù)字往前移動，由于排在數(shù)組前面的數(shù)字要小一些，它們的和就有也許等于輸入的數(shù)字了。我們把前面的思緒整理一下：最初我們找到數(shù)組的第一個數(shù)字和最后一個數(shù)字。當兩個數(shù)字的和大于輸入的數(shù)字時，把較大的數(shù)字往前移動；當兩個數(shù)字的和小于數(shù)字時，把較小的數(shù)字往后移動；當相等時，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。問題是這樣的思緒是不是對的的呢？這需要嚴格的數(shù)學證明。感愛好的讀者可以自行證明一下。參考代碼：///////////////////////////////////////////////////////////////////////

//Findtwonumberswithasuminasortedarray

//Output:tureisfoundsuchtwonumbers,otherwisefalse

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

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;

}擴展：假如輸入的數(shù)組是沒有排序的，但知道里面數(shù)字的范圍，其他條件不變，如和在O(n)時間里找到這兩個數(shù)字？(11)－求二元查找樹的鏡像題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完畢樹的鏡像轉(zhuǎn)換。例如輸入：8

/\

610

/\/\

57911輸出：8

/\

106

/\

/\

119

75定義二元查找樹的結(jié)點為：structBSTreeNode//anodeinthebinarysearchtree(BST)

{

intm_nValue;//valueofnode

BSTreeNode*m_pLeft;//leftchildofnode

BSTreeNode*m_pRight;//rightchildofnode

};分析：盡管我們也許一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就是互換結(jié)點的左右子樹。我們試著在遍歷例子中的二元查找樹的同時來互換每個結(jié)點的左右子樹。遍歷時一方面訪問頭結(jié)點8，我們互換它的左右子樹得到：8

/\

106

/\/\

91157我們發(fā)現(xiàn)兩個結(jié)點6和10的左右子樹仍然是左結(jié)點的值小于右結(jié)點的值，我們再試著互換他們的左右子樹，得到：8

/\

106

/\

/\

119

75剛好就是規(guī)定的輸出。上面的分析印證了我們的直覺：在遍歷二元查找樹時每訪問到一個結(jié)點，互換它的左右子樹。這種思緒用遞歸不難實現(xiàn)，將遍歷二元查找樹的代碼稍作修改就可以了。參考代碼如下：///////////////////////////////////////////////////////////////////////

//MirroraBST(swaptheleftrightchildofeachnode)recursively

//theheadofBSTininitialcall

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

voidMirrorRecursively(BSTreeNode*pNode)

{

if(!pNode)

return;

//swaptherightandleftchildsub-tree

BSTreeNode*pTemp=pNode->m_pLeft;

pNode->m_pLeft=pNode->m_pRight;

pNode->m_pRight=pTemp;

//mirrorleftchildsub-treeifnotnull

if(pNode->m_pLeft)

MirrorRecursively(pNode->m_pLeft);

//mirrorrightchildsub-treeifnotnull

if(pNode->m_pRight)

MirrorRecursively(pNode->m_pRight);

}由于遞歸的本質(zhì)是編譯器生成了一個函數(shù)調(diào)用的棧，因此用循環(huán)來完畢同樣任務(wù)時最簡樸的辦法就是用一個輔助棧來模擬遞歸。一方面我們把樹的頭結(jié)點放入棧中。在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點，互換它的左右子樹。假如它有左子樹，把它的左子樹壓入棧中；假如它有右子樹，把它的右子樹壓入棧中。這樣在下次循環(huán)中就能互換它兒子結(jié)點的左右子樹了。參考代碼如下：///////////////////////////////////////////////////////////////////////

//MirroraBST(swaptheleftrightchildofeachnode)Iteratively

//Input:pTreeHead:theheadofBST

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

voidMirrorIteratively(BSTreeNode*pTreeHead)

{

if(!pTreeHead)

return;

std::stack<BSTreeNode*>stackTreeNode;

stackTreeNode.push(pTreeHead);

while(stackTreeNode.size())

{

BSTreeNode*pNode=stackTreeNode.top();

stackTreeNode.pop();

//swaptherightandleftchildsub-tree

BSTreeNode*pTemp=pNode->m_pLeft;

pNode->m_pLeft=pNode->m_pRight;

pNode->m_pRight=pTemp;

//pushleftchildsub-treeintostackifnotnull

if(pNode->m_pLeft)

stackTreeNode.push(pNode->m_pLeft);

//pushrightchildsub-treeintostackifnotnull

if(pNode->m_pRight)

stackTreeNode.push(pNode->m_pRight);

}

}(12)－從上往下遍歷二元樹

題目：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。例如輸入8

/\

610

/\/\

57911輸出861057911。分析：這曾是微軟的一道面試題。這道題實質(zhì)上是規(guī)定遍歷一棵二元樹，只但是不是我們熟悉的前序、中序或者后序遍歷。我們從樹的根結(jié)點開始分析。自然先應(yīng)當打印根結(jié)點8，同時為了下次可以打印8的兩個子結(jié)點，我們應(yīng)當在遍歷到8時把子結(jié)點6和10保存到一個數(shù)據(jù)容器中?，F(xiàn)在數(shù)據(jù)容器中就有兩個元素6

和10了。按照從左往右的規(guī)定，我們先取出6訪問。打印6的同時要把6的兩個子結(jié)點5和7放入數(shù)據(jù)容器中，此時數(shù)據(jù)容器中有三個元素10、5和7。接下來我們應(yīng)當從數(shù)據(jù)容器中取出結(jié)點10訪問了。注意10比5和7先放入容器，此時又比5和7先取出，就是我們通常說的先入先出。因此不難看出這個數(shù)據(jù)容器的類型應(yīng)當是個隊列。既然已經(jīng)擬定數(shù)據(jù)容器是一個隊列，現(xiàn)在的問題變成怎么實現(xiàn)隊列了。事實上我們無需自己動手實現(xiàn)一個，由于STL已經(jīng)為我們實現(xiàn)了一個很好的deque（兩端都可以進出的隊列），我們只需要拿過來用就可以了。我們知道樹是圖的一種特殊退化形式。同時假如對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式事實上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹上實現(xiàn)廣度優(yōu)先遍歷。參考代碼：#include<deque>

#include<iostream>

usingnamespacestd;

structBTreeNode//anodeinthebinarytree

{

int