程序員面試題精選100題（01）一把二元查找樹轉變成排序的雙向鏈表

2007-02-2722:47:591分類：樹|標簽：就業找工作編程|字號訂

閱

題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈

表。要求不能創建任何新的結點，只調整指針的指向。

比如將二元查找樹

10

/\

614

/\/\

481216

轉換成雙向鏈表

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

分析：本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來

解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。

思路一：當我們到達某一結點準備調整以該結點為根結點的子樹時，

先調整其左子樹將左子樹轉換成一個排好序的左子鏈表，再調整其右子樹轉換右

子鏈表。最近鏈接左子鏈表的最右結點（左子樹的最大結點）、當前結點和右

子鏈表的最左結點（右子樹的最小結點）。從樹的根結點開始遞歸調整所有結點。

思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結

點先訪問。如果我們每訪問一個結點，假設之前訪問過的結點已經調整成一個排

序雙向鏈表，我們再把調整當前結點的指針將其鏈接到鏈表的末尾。當所有結點

都訪問過之后，整棵樹也就轉換成一個排序雙向鏈表了。

參考代碼：

首先我們定義二元查找樹結點的數據結構如下：

structBSTreeNode//anodeinthebinarysearchtree

{

intm_nValue;//valueofnode

BSTreeNode*m_pLeft;//leftchildofnode

BSTreeNode*m__pRight;//rightchildofnode

）；

思路一對應的代碼：

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

//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->ni_pLeft,false);

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

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

}

思路二對應的代碼：

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

//

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

}

程序員面試題精選100題(02)一設計包含min函數的棧

2007-02-2821:52:281分類：棧|標簽：緘程就業找工作|字號訂

閱

題目：定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。要

求函數min、push以及pop的時間復雜度都是0(1)。

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

我看到這道題目時，第一反應就是每次push一個新元素時，將棧里所有逆序元

素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進棧的元素最

先出棧，這種思路設計的數據結構已經不是一個棧了。

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

新元素進棧的時候，如果該元素比當前的最小元素還要小，則更新最小元素。

乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果當前最

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

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

們需要一個輔助棧。每次push一個新元素的時候，同時將最小元素(或最小元

素的位置?？紤]到棧元素的類型可能是復雜的數據結構，用最小元素的位置將能

減少空間消耗)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_minlndex

if(m_minIndex.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_minIndex.push_back(m_minIndex.back());

}

)

//ereasetheelementattheendofstack

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

(

//popm_data

m_data.pop_back();

//popm_minIndex

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()];

)

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

步驟數據棧輔助棧最小值

1.push3303

2.push43,40z03

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.push03z4,00,0,20

討論：如果思路正確，編寫上述代碼不是一件很難的事情。但如果能注意一些細

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

?用模板類實現。如果別人的元素類型只是int類型，模板將能給面試官帶來

好印象；

?兩個版本的top函數。在很多類中，都需要提供const和非const版本的成

員訪問函數；

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

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

總之，在面試時如果時間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個

小亮點就能讓自己輕松拿到心儀的Offero

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

2007-03-0121:14:07|分類：數組|標簽：編程就業找工作|字

號訂閱

題目：輸入…個整形數組，數組里有正數也有負數。數組中連續的一個或多個整

數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求

時間復雜度為0(n)。

例如輸入的數組為1,-2,3,10,-4,7,2,-5,和最大的子數組為3,10,-4,

7,2,因此輸出為該子數組的和180

分析：本題最初為2005年浙江大學計算機系的考研題的最后一道程序設計題，

在2006年里包括google在內的很多知名公司都把本題當作面試題。由于本題在

網絡中廣為流傳，本題也順利成為2006年程序員面試題中經典中的經典。

如果不考慮時間復雜度，我們可以枚舉出所有子數組并求出他們的和。不過非常

遺憾的是，由于長度為n的數組有0(/)個子數組；而且求一個長度為n的數組

的和的時間復雜度為0(n)。因此這種思路的時間是0(/)。

很容易理解，當我們加上一個正數時，和會增加；當我們加上一個負數時，和會

減少。如果當前得到的和是個負數，那么這個和在接下來的累加中應該拋棄并重

新清零，不然的話這個負數將會減少接下來的和。基于這樣的思路，我們可以寫

出如下代碼。

參考代碼:

////////

//Findthegreatestsumofallsub-arrays

//Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse

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

////////

boolFindGreatestSumOfSubArray

int*pData,//anarray

unsignedintnLength,//thelengthofarray

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

}

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

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

如果函數返回值的是子數組和的最大值，那么當輸入一個空指針是應該返回什么

呢？返回0?那這個函數的用戶怎么區分輸入無效和子數組和的最大值剛好是0

這兩中情況呢？基于這個考慮，本人認為把子數組和的最大值以引用的方式放到

參數列表中，同時讓函數返回一個函數是否正常執行的標志。

?輸入有一類特殊情況需要特殊處理。當輸入數組中所有整數都是負數時，子

數組和的最大值就是數組中的最大元素。

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

徑

2007-03-0220:35:071分類：機|標簽：緘程就業找工作|字號訂

閱

題目：輸入…個整數和一棵二元樹二從樹的根結點開始往下訪問一直到葉結點所

經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。

例如輸入整數22和如下二元樹

10

/\

512

/\

47

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

二元樹結點的數據結構定義為：

structBinaryTreeNode//anodeinthebinarytree

(

intm_nValue;//valueofnode

BinaryTreeNode*m_pLeft;//leftchildofnode

BinaryTreeNode*m_pRight;//rightchildofnode

)；

分析:這是百度的一道筆試題，考查對樹這種基本數據結構以及遞歸函數的理解。

當訪問到某一結點時，把該結點添加到路徑上，并累加當前結點的值。如果當前

結點為葉結點并且當前路徑的和剛好等于輸入的整數，則當前的路徑符合要求，

我們把它打印出來。如果當前結點不是葉結點，則繼續訪問它的子結點。當前結

點訪問結束后，遞歸函數將自動回到父結點。因此我們在函數退出之前要在路

徑上刪除當前結點并減去當前結點的值，以確保返回父結點時路徑剛好是根結點

到父結點的路徑。我們不難看出保存路徑的數據結構實際上是一個棧結構，因

為路徑要與遞歸調用狀態一致，而遞歸調用本質就是一個壓棧和出棧的過程。

參考代碼：

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

//

//Findpathswhosesumequaltoexpectedsum

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

//

voidFindPath

(

BinaryTreeNode*pTreeNode,//anodeofbinarytree

intexpectedSum,//theexpectedsum

std::vector<int>&pathz//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<<'\t1;

std::cout<<std::endl;

}

//ifthenodeisnotaleaf,gotoitschildren

if(pTreeNode->m_pLeft)

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

if(pTreeNode->m__pRight)

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

//whenwefinishvisitinganodeandreturntoitsparentnode,

//weshoulddeletethisnodefromthepathand

//minusthenodefsvaluefromthecurrentsum

currentsum-=pTreeNode->m_nValue;

path,pop_back();

}

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

2007-03-0415:21:36|分類：W|標簽：編程就業找工作數據結

構篁法導號訂閱

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

例如輸入1，2,3,4,5,6,7和8這8個數字，則最小的4個數字為1,2,3

和4。

分析：這道題最簡單的思路莫過于把輸入的n個整數排序，這樣排在最前面的k

個數就是最小的k個數。只是這種思路的時間復雜度為0(n/o/1)。我們試著尋

找更快的解決思路。

我們可以先創建一個大小為k的數據容器來存儲最小的k個數字。接下來

我們每次從輸入的n個整數中讀入一個數。如果容器中已有的數字少于k個，則

直接把這次讀入的整數放入容器之中；如果容器中已有k個數字了，也就是容器

已滿，此時我們不能再插入新的數字而只能替換已有的數字。我們找出這已有的

k個數中最大值，然和拿這次待插入的整數和這個最大值進行比較。如果待插入

的值比當前已有的最大值小，則用這個數替換替換當前已有的最大值；如果帶插

入的值比當前已有的最大值還要大，那么這個數不可能是最小的k個整數之一，

因為我們容器內已經有k個數字比它小了，于是我們可以拋棄這個整數。

因此當容器滿了之后，我們要做三件事情:一是在k個整數中找到最大數,

二是有可能在這個容器中刪除最大數，三是可能要插入一個新的數字，并保證k

個整數依然是排序的。如果我們用一個二叉樹來實現這個數據容器，那么我們能

在0("涿)時間內實現這三步操作。因此對于n個輸入數字而言，總的時間效率

就是0(n_Zo或)。

我們可以選擇用不同的二叉樹來實現這個數據容器。由于我們每次都需要

找到k個整數中的最大數字，我們很容易想到用最大堆。在最大堆中，根結點的

值總是大于它的子樹中任意結點的值。于是我們每次可以在0(1)得到已有的k

個數字中的最大值，但需要0(1四k)時間完成刪除以及插入操作。

我們自己從頭實現一個最大堆需要一定的代碼。我們還可以采用紅黑樹來

實現我們的容器。紅黑樹通過把結點分為紅、黑兩種顏色并根據一些規則確保樹

是平衡的，從而保證在紅黑樹中查找、刪除和插入操作都只需要0(1?；?。在STL

中set和multiset都是基于紅黑樹實現的。如果面試官不反對我們用STL中的

數據容器，我們就直接拿過來用吧。下面是基于STL中的multiset的參考代碼:

typedefmultiset<int,greater<int>>IntHeap;

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

//

//findkleastnumbersinavector

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

//

voidFindKLeastNumbers

(

constvector<int>&data,//avectorofdata

IntHeap&leastNumbersz//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);

)

}

}

}

程序員面試題精選100題(06)—判斷整數序列是不是二元查找樹的后

序遍歷結果

2007-03-0515:01:091分類：笆|標簽：編程就業找工作|字號訂

閱

題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。

如果是返回true,否則返回falseo

例如輸入5、7、6、9、11、10、8,由于這一整數序列是如下樹的后序遍歷結果:

8

/\

610

/\/\

57911

因此返回trueo

如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結果是這個序列，因此返回falseo

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

在后續遍歷得到的序列中，最后一個元素為樹的根結點。從頭開始掃描這個序

列，比根結點小的元素都應該位于序列的左半部分；從第一個大于跟結點開始到

跟結點前面的一個元素為止，所有元素都應該大于跟結點，因為這部分元素對應

的是樹的右子樹。根據這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確

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

參考代碼:

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

}

程序員面試題精選100題(07)—翻轉句子中單詞的順序

2007-03-0809:20:52|分類:字符串|標簽：編程就業找工作|字

號訂閱

題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。

句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。

例如輸入“Iamastudent.”，則輸出"student,aamI”。

分析?：由于編寫字符串相關代碼能夠反映程序員的編程能力和編程習慣，與字符

串相關的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微

軟在內的大量公司的青睞。

由于本題需要翻轉句子，我們先顛倒句子中的所有字符。這時，不但翻轉了句子

中單詞的順序，而且單詞內字符也被翻轉了。我們再顛倒每個單詞內的字符。由

于單詞內的字符被翻轉兩次，因此順序仍然和輸入時的順序保持一致。

還是以上面的輸入為例子。翻轉“Iamastudent."中所有字符得到“.tneduts

amar,再翻轉每個單詞中字符的順序得到“students.aamI"，正是符合

要求的輸出。

參考代碼：

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

//

//Reverseastringbetweentwopointers

//Input:pBegin-thebeginpointerinastring

//pEnd-theendpointerinastring

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

//

voidReverse(char*pBeginfchar*pEnd)

(

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

return;

while(pBegin<pEnd)

chartemppBegin;

*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!='\01)

{

if(*pBegin=='')

{

pBegin++;

pEnd++;

continue;

)

//AwordisbetweenwithpBeginandpEnd,reverseit

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

(

Reverse(pBegin,——pEnd);

pBegin=++pEnd;

)

else

{

pEnd++;

)

)

returnpData;

}

程序員面試題精選100題(08)一求1+2+...+n

2007-03-0913:51:311分類:雜題|標簽：轆就業找工作|字

號訂閱

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

case等關鍵字以及條件判斷語句(A?B:C)。

分析：這道題沒有多少實際意義，因為在軟件開發中不會有這么變態的限制。但

這道題卻能有效地考查發散思維能力，而發散思維能力能反映出對編程相關技術

理解的深刻程度。

通常求1+2+…+n除了用公式n(n+l)/2之外，無外乎循環和遞歸兩種思路。由于

已經明確限制for和while的使用，循環已經不能再用了。同樣，遞歸函數也需

要用if語句或者條件判斷語句來判斷是繼續遞歸下去還是終止遞歸，但現在題

目已經不允許使用這兩種語句了。

我們仍然圍繞循環做文章。循環只是讓相同的代碼執行n遍而已，我們完全可以

不用for和while達到這個效果。比如定義一個類，我們new—含有n個這種類

型元素的數組，那么該類的構造函數將確定會被調用n次。我們可以將需要執行

的代碼放到構造函數里。如下代碼正是基于這個思路：

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

}

我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我們不妨

定義兩個函數。一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況,

我們需要做的就是在兩個函數里二選一。從二選i我們很自然的想到布爾變量，

比如ture(1)的時候調用第一個函數，false(0)的時候調用第二個函數。那

現在的問題是如和把數值變量n轉換成布爾值。如果對n連續做兩次反運算，

即！！n,那么非零的n轉換為true,0轉換為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;

}

這種方法是用虛函數來實現函數的選擇。當n不為零時，執行函數當n

為0時，執行A::Sum。我們也可以直接用函數指針數組，這樣可能還更直接一

些：

typedefint(*fun)(int);

intsolution3_f1(inti)

(

return0;

}

intsolution3_f2(inti)

(

funf[2]={solution3_f1solution3_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<100>::N就是1+2+...+100的結果。當編譯器看到

solution4_Sum<100>H't,就是為模板類solution4_Sum以參數100生成該類型的

代碼。但0100為參數的類型需要得到以99為參藪的類型，因為

solution4_Sum<100>::N=solution4_Sum<99>::N+100。這個過程會遞歸一直到參

數為1的云型，由于該類型已經顯式定義，編譯器無需生成，遞歸編譯到此結束。

由于這個過程是在編譯過程中完成的，因此要求輸入n必須是在編譯期間就能確

定，不能動態輸入。這是該方法最大的缺點。而且編譯器對遞歸編譯代碼的遞歸

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

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

程序員面試題精選100題（09）一查找鏈表中倒數第k個結點

2007-03-1116:47:081分類：鏈表|標簽：轆就業找工作|字

號訂閱

題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。鏈表的倒數第。個結

點為鏈表的尾指針。鏈表結點定義如下：

structListNode

intm_nKey;

ListNode*m_pNext;

｝；

分析：為了得到倒數第k個結點，很自然的想法是先走到鏈表的尾端，再從尾端

回溯k步。可是輸入的是單向鏈表,只有從前往后的指針而沒有從后往前的指針。

因此我們需要打開我們的思路。

既然不能從尾結點開始遍歷這個鏈表，我們還是把思路回到頭結點上來。假設整

個鏈表有n個結點，那么倒數第k個結點是從頭結點開始的第n-k-1個結點（從

0開始計數）。如果我們能夠得到鏈表中結點的個數n,那我們只要從頭結點開

始往后走n-k-1步就可以了。如何得到結點數n?這個不難，只需要從頭開始遍

歷鏈表，每經過一個結點，計數器加-就行了。

這種思路的時間復雜度是0（n）,但需要遍歷鏈表兩次。第一次得到鏈表中結點

個數n,第二次得到從頭結點開始的第n-k-1個結點即倒數第k個結點。

如果鏈表的結點數不多，這是一種很好的方法。但如果輸入的鏈表的結點個數很

多，有可能不能一次性把整個鏈表都從硬盤讀入物理內存，那么遍歷兩遍意味著

一個結點需要兩次從硬盤讀入到物理內存。我們知道把數據從硬盤讀入到內存是

非常耗時間的操作。我們能不能把鏈表遍歷的次數減少到1?如果可以，將能

有效地提高代碼執行的時間效率。

如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第

kT步之前，第二個指針保持不動；在第k-1步開始，第二個指針也開始從鏈表

的頭指針開始遍歷。由于兩個指針的距離保持在k-1,當第一個（走在前面的）

指針到達鏈表的尾結點時，第二個指針（走在后面的）指針正好是倒數第k個結

點。

這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結點從硬盤導入

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

思路-的參考代碼:

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

//

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

}

//if