程序員面試題精選100題(34)-找出數組中兩個只出現一次的數字

題目：-個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序

找出這兩個只出現一次的數字。要求時間復雜度是O(n),空間復雜度是0(1)。

分析：這是一道很新穎的關于位運算的面試題。

首先我們考慮這個問題的一個簡單版本：一個數組里除了一個數字之外，其他的

數字都出現了兩次。請寫程序找出這個只出現一次的數字。

這個題目的突破口在哪里？題目為什么要強調有一個數字出現一次，其他的出現

兩次？我們想到了異或運算的性質：任何一個數字異或它自己都等于0。也就是

說，如果我們從頭到尾依次異或數組中的每一個數字，那么最終的結果剛好是那

個只出現依次的數字，因為那些出現兩次的數字全部在異或中抵消掉了。

有了上面簡單問題的解決方案之后，我們回到原始的問題。如果能夠把原數組分

為兩個子數組。在每個子數組中，包含一個只出現一次的數字，而其他數字都出

現兩次。如果能夠這樣拆分原數組，按照前面的辦法就是分別求出這兩個只出現

一次的數字了。

我們還是從頭到尾依次異或數組中的每一個數字，那么最終得到的結果就是兩個

只出現一次的數字的異或結果。因為其他數字都出現了兩次，在異或中全部抵消

掉了。由于這兩個數字肯定不一樣，那么這個異或結果肯定不為0,也就是說在

這個結果數字的二進制表示中至少就有一位為lo我們在結果數字中找到第一個

為1的位的位置，記為第N位。現在我們以第N位是不是1為標準把原數組中

的數字分成兩個子數組，第一個子數組中每個數字的第N位都為1,而第二個子

數組的每個數字的第N位都為0o

現在我們已經把原數組分成了兩個子數組，每個子數組都包含一個只出現一次的

數字，而其他數字都出現了兩次。因此到此為止，所有的問題我們都已經解決。

基于上述思路，我們不難寫出如下代碼：

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

//

//Findtwonumberswhichonlyappearonceinanarray

//Input:data-anarraycontainstwonumberappearingexactlyonce,

//whileothersappearingexactlytwice

//length-thelengthofdata

//Output:numl-thefirstnumberappearingonceindata

//num2-thesecondnumberappearingonceindata

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

//

voidFindNumsAppearOnce(intdata[]zintlength,int&numl,int&num2)

if(length<2)

return;

//getnumlAnum2

intresultExclusiveOR=0;

for(inti=0;i<length;++i)

resultExclusiveOR人=data[i];

//getindexofthefirstbit,whichis1inresultExclusiveOR

unsignedintindexOf1=FindFirstBitIsl(resultExclusiveOR);

numl=num2=0;

for(intj=0;j<length;++j)

{

//dividethenumbersindataintotwogroups,

//theindexOf1bitofnumbersinthefirstgroupis1,

IIwhileinthesecondgroupis0

if(IsBit1(data[j],indexOf1))

numl八=data[j];

else

num2A=data[j];

}

}

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

//

//Findtheindexoffirstbitwhichis1innum(assumingnot0)

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

//

unsignedintFindFirstBitIsl(intnum)

(

intindexBit=0;

while(((num&1)==0)&&(indexBit<32))

(

num=num>>1;

++indexBit;

)

returnindexBit;

)

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

//

//IstheindexBitbitofnum1?

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

//

boolIsBit1(intnum,unsignedintindexBit)

(

num=num>>indexBit;

return(num&1);

)

程序員面試題精選100題(35)-找出兩個鏈表的第一個公共結點

鏈表2008-01-0515:16:09閱讀6477評論13字號：大中小訂閱

題目：兩個單向鏈表，找出它們的第一個公共結點。

鏈表的結點定義為：

structListNode

(

intm_nKey;

ListNode*m_pNext;

｝；

分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關的題目，因此在微軟的

面試題中，鏈表出現的概率相當高。

如果兩個單向鏈表有公共的結點，也就是說兩個鏈表從某一結點開始，它們的

m_pNext都指向同一個結點。但由于是單向鏈表的結點，每個結點只有一個

m_pNext,因此從第一個公共結點開始，之后它們所有結點都是重合的，不可能

再出現分叉。所以，兩個有公共結點而部分重合的鏈表，拓撲形狀看起來像一個

Y,而不可能像X。

看到這個題目，第一反應就是蠻力法：在第一鏈表上順序遍歷每個結點。每遍歷

一個結點的時候，在第二個鏈表上順序遍歷每個結點。如果此時兩個鏈表上的結

點是一樣的，說明此時兩個鏈表重合，于是找到了它們的公共結點。如果第一個

鏈表的長度為m,第二個鏈表的長度為n,顯然，該方法的時間復雜度為0(mn)。

接下來我們試著去尋找一個線性時間復雜度的算法。我們先把問題簡化：如何判

斷兩個單向鏈表有沒有公共結點？前面已經提到，如果兩個鏈表有一個公共結

點，那么該公共結點之后的所有結點都是重合的。那么，它們的最后一個結點必

然是重合的。因此，我們判斷兩個鏈表是不是有重合的部分，只要分別遍歷兩個

鏈表到最后一個結點。如果兩個尾結點是一樣的，說明它們用重合；否則兩個鏈

表沒有公共的結點。

在上面的思路中，順序遍歷兩個鏈表到尾結點的時候，我們不能保證在兩個鏈表

上同時到達尾結點。這是因為兩個鏈表不一定長度一樣。但如果假設一個鏈表比

另一個長I個結點，我們先在長的鏈表上遍歷I個結點，之后再同步遍歷，這個

時候我們就能保證同時到達最后一個結點了。由于兩個鏈表從第一個公共結點考

試到鏈表的尾結點，這一部分是重合的。因此，它們肯定也是同時到達第一公共

結點的。于是在遍歷中，第一個相同的結點就是第一個公共的結點。

在這個思路中，我們先要分別遍歷兩個鏈表得到它們的長度，并求出兩個長度之

差。在長的鏈表上先遍歷若干次之后，再同步遍歷兩個鏈表，知道找到相同的結

點，或者一直到鏈表結束。此時，如果第一個鏈表的長度為m,第二個鏈表的長

度為n,該方法的時間復雜度為O(m+n)。

基于這個思路，我們不難寫出如下的代碼：

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

//

//FindthefirstcommonnodeinthelistwithheadpHeadland

//thelistwithheadpHead2

//Input:pHeadl-theheadofthefirstlist

//pHead2-theheadofthesecondlist

//Return:thefirstcommonnodeintwolist.Ifthereisnocommon

//nodes,returnNULL

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

//

ListNode*FindFirstCommonNode(ListNode*pHeadlzListNode*pHead2)

(

//Getthelengthoftwolists

unsignedintnLengthl=ListLength(pHeadl);

unsignedintnLength2=ListLength(pHead2);

intnLengthDif=nLengthl-nLength2;

//Getthelongerlist

ListNode*pListHeadLong=pHeadl;

ListNode*pListHeadShort=pHead2;

if(nLength2>nLengthl)

{

pListHeadLong=pHead2;

pListHeadShort=pHeadl;

nLengthDif=nLength2-nLengthl;

)

//Moveonthelongerlist

for(inti=0;i<nLengthDif;++i)

pListHeadLong=pListHeadLong->m_pNext;

//Moveonbothlists

while((pListHeadLong!=NULL)&&

(pListHeadShort!=NULL)&&

(pListHeadLong!=pListHeadShort))

(

pListHeadLong=pListHeadLong->m_pNext;

pListHeadShort=pListHeadShort->rn_pNext;

}

//Getthefirstcommonnodeintwolists

ListNode*pFisrtCommonNode=NULL;

if(pListHeadLong==pListHeadShort)

pFisrtCommonNode=pListHeadLong;

returnpFisrtCommonNode;

}

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

//

//GetthelengthoflistwithheadpHead

//Input:pHead-theheadoflist

//Return:thelengthoflist

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

//

unsignedintListLength(ListNode*pHead)

(

unsignedintnLength=0;

ListNode*pNode=pHead;

while(pNode!=NULL)

{

++nLength;

pNode=pNode->m_pNext;

)

returnnLength;

}

程序員面試題精選100題(36)-在字符串中刪除特定的字符

字符串2008-01-1915:14:26閱讀7133評論15字號：大中小訂閱

題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，

輸入〃Theyarestudents.〃和〃aeiou”,則刪除之后的第一個字符串變成〃Thyr

stdnts/o

分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關的題目占了

很大的一部分，因為寫程序操作字符串能很好的反映我們的編程基本功。

要編程完成這道題要求的功能可能并不難。畢竟，這道題的基本思路就是在第一

個字符串中拿到一個字符，在第二個字符串中查找一下，看它是不是在第二個字

符串中。如果在的話，就從第一個字符串中刪除。但如何能夠把效率優化到讓人

滿意的程度，卻也不是一件容易的事情。也就是說，如何在第一個字符串中刪除

一個字符，以及如何在第二字符串中查找一個字符，都是需要一些小技巧的。

首先我們考慮如何在字符串中刪除一個字符。由于字符串的內存分配方式是連續

分配的。我們從字符串當中刪除一個字符，需要把后面所有的字符往前移動一個

字節的位置。但如果每次刪除都需要移動字符串后面的字符的話，對于一個長度

為n的字符串而言，刪除一個字符的時間復雜度為0(n)。而對于本題而言，有可

能要刪除的字符的個數是n,因此該方法就刪除而言的時間復雜度為OS?)。

事實上，我們并不需要在每次刪除一個字符的時候都去移動后面所有的字符。我

們可以設想，當一個字符需要被刪除的時候，我們把它所占的位置讓它后面的字

符來填補，也就相當于這個字符被刪除了。在具體實現中，我們可以定義兩個指

針(pFast和pSIow),初始的時候都指向第一字符的起始位置。當pFast指向的字

符是需要刪除的字符，則pFast直接跳過，指向下一個字符。如果pFast指向的

字符是不需要刪除的字符，那么把pFast指向的字符賦值給pSIow指向的字符，

并且pFast和pStart同時向后移動指向下一個字符。這樣，前面被pFast跳過的

字符相當于被刪除了。用這種方法，整個刪除在0(n)時間內就可以完成。

接下來我們考慮如何在一個字符串中查找一個字符。當然，最簡單的辦法就是從

頭到尾掃描整個字符串。顯然，這種方法需要一個循環，對于一個長度為n的字

符串，時間復雜度是0(n)。

由于字符的總數是有限的。對于八位的char型字符而言，總共只有28=256個字

符。我們可以新建一個大小為256的數組，把所有元素都初始化為0。然后對于

字符串中每一個字符，把它的ASCII碼映射成索引，把數組中該索引對應的元素

設為1。這個時候，要查找一個字符就變得很快了：根據這個字符的ASCII碼，

在數組中對應的下標找到該元素，如果為0,表示字符串中沒有該字符，否則字

符串中包含該字符。此時，查找一個字符的時間復雜度是0(1)。其實，這個數組

就是一個hash表。這種思路的詳細說明，詳見本面試題系列的第13題。

基于上述分析，我們可以寫出如下代碼:

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

//

//DeleteallcharactersinpStrDeletefrompStrSource

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

//

voidDeleteChars(char*pStrSource,constchar*pStrDelete)

(

if(NULL==pStrSource||NULL==pStrDelete)

return;

//Initializeanarray,theindexinthisarrayisASCIIvalue.

//Allentriesinthearray,whoseindexisASCIIvalueofa

//characterinthepStrDelete,willbesetas1.

//Otherwise,theywillbesetas0.

constunsignedintnTableSize=256;

inthashTable[nTableSize];

memset(hashTable,0,sizeof(hashTable));

constchar*pTemp=pStrDelete;

while(*\0'!=*pTemp)

(

hashTable[*pTemp]=1;

++pTemp;

)

char*pSlow=pStrSource;

char*pFast=pStrSource;

while(*\0'!=*pFast)

(

//ifthecharacterisinpStrDelete,movebothpStartand

//pEndforward,andcopypEndtopStart.

//Otherwise,moveonlypEndforward,andthecharacter

//pointedbypEndisdeleted

if(1!=hashTable[*pFast])

{

*pSlow=*pFast;

++pSlow;

)

++pFast;

)

*pSlow=T\0f;

}

程序員面試題精選100題(37)-尋找丑數

數字游戲2009-05-2417:36:06閱讀5857評論12字號：大中小訂閱

題目：我們把只包含因子

2、3和5的數稱作丑數(UglyNumber)。例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我

們把1當做是第一個丑數。求按從小到大的順序的第1500個丑數。

分析：這是?道在網絡上廣為流傳的面試題，據說google曾經采用過這道題。

所謂一個數m是另一個數n的因子，是指n能被m整除，也就是n%m=0。根據丑數的定義，丑

數只能被2、3和5整除。也就是說如果?個數如果它能被2整除，我們把它連續除以2；如果能被3整除，

就連續除以3；如果能被5整除，就除以連續5。如果最后我們得到的是1,那么這個數就是丑數，否則不

是。

基于前面的分析，我們可以寫出如下的函數來判斷一個數是不是五數：

boolIsUgly(intnumber)

(

while(number%2==0)

number/=2;

while(number%3==0)

number/-3;

while(number%5==0)

number/=5;

return(number==1)?true:false;

}

接下來，我們只需要按順序判斷每一個整數是不是丑數，即：

intGetUglyNumber_Solutionl(intindex)

(

if(index<=0)

return0;

intnumber=0;

intuglyFound=0;

while(uglyFound<index)

(

++number;

if(IsUgly(number))

++uglyFound;

}

returnnumber;

)

我們只需要在函數GetUglyNumber_Solutionl中傳入參數1500,就能得到第1500個丑數。該算

法非常直觀，代碼也非常簡潔，但最大的問題我們每個整數都需要計算。即使一個數字不是丑數，我們還

是需要對它做求余數和除法操作。因此該算法的時間效率不是很高。

接下來我們換一種思路來分析這個問題，試圖只計算丑數，而不在非丑數的整數上花費時間。根據丑

數的定義，丑數應該是另一個丑數乘以2、3或者5的結果(1除外)。因此我們可以創建一個數組，里面

的數字是排好序的丑數。里面的每一個丑數是前面的J1數乘以2、3或者5得到的。

這種思路的關鍵在于怎樣確保數組里面的丑數是排好序的。我們假設數組中已經有若干個丑數，排好

序后存在數組中。我們把現有的最大丑數記做M。現在我們來生成下一個丑數，該丑數肯定是前面某一個

丑數乘以2、3或者5的結果。我們首先考慮把已有的每個丑數乘以2。在乘以2的時候，能得到若干個結

果小于或等于M的。由于我們是按照順序生成的，小于或者等于M肯定已經在數組中了，我們不需再次

考慮；我們還會得到若干個大于M的結果，但我們只需要第一個大于M的結果，因為我們希望丑數是按

從小到大順序生成的，其他更大的結果我們以后再說。我們把得到的第一個乘以2后大于M的結果，記為

同樣我們把已有的每一個丑數乘以和能得到第一個大于的結果和那么下一個丑數應

M2?35,MM3M”

該是M2、M3和Ms三個數的最小者。

前面我們分析的時候，提到把已有的每個丑數分別都乘以2、3和5,事實上是不需要的，因為已有的

丑數是按順序存在數組中的。對乘以2而言，肯定存在某一個丑數Tz，排在它之前的每一個丑數乘以2得

到的結果都會小于已有最大的丑數，在它之后的每一個丑數乘以2得到的結果都會太大。我們只需要記下

這個丑數的位置，同時每次生成新的丑數的時候，去更新這個對乘以3和5而言，存在著同樣的和

Ts。

有了這些分析?，我們不難寫出如下的代碼：

intGetUglyNumber_Solution2(intindex)

(

if(index<=0)

return0;

int*pUglyNumbers=newint[index];

pUglyNumbers[0]=1;

intnextUglyIndex=1;

int*pMultiply2=pUglyNumbers;

int*pMultiply3=pUglyNumbers;

int*pMultiply5=pUglyNumbers;

while(nextUglylndex<index)

(

intmin=Min(*pMultiply2*2,*pMultiply3*3,*pMultiply5*5);

pUglyNumbers[nextUglylndex]=min;

while(*pMultiply2*2<=pUglyNumbers[nextUglylndex])

++pMultiply2;

while(*pMultiply3*3<=pUglyNumbers[nextUglylndex])

++pMultiply3;

while(*pMultiply5*5<=pUglyNumbers[nextUglylndex])

4-+pMultiply5;

++nextUglyIndex;

)

intugly=pUglyNumbers[nextUglylndex-1];

delete[]pUglyNumbers;

returnugly;

)

intMin(intnumberl,intnumber2,intnumber3)

(

intmin=(numberl<number2)?numberl:number2;

min=(min<number3)?min:number3;

returnmin;

}

和第一種思路相比，這種算法不需要在非丑數的整數上做任何計算，因此時間復雜度要低很多。感興

趣的讀者可以分別統計兩個函數GetUglyNumber_Solutionl(1500)和

GetUg1yNumber_Solution2(1500)的運行時間。當然我們也要指出，第二種算法由于要保存已經生成

的丑數，因此需要?個數組，從而需要額外的內存。第?種算法是沒有這樣的內存開銷的。

程序員面試題精選100題(38)-輸出1到最大的N位數

數字游戲2009-05-2709:42:06閱讀5076評論4字號：大中小訂閱

題目：輸入數字n,按順序輸出從1最大的n位10進制數?比如輸入3,則輸出1、2、3一直到最大的3

位數即999。

分析：這是一道很有意思的題目。看起來很簡單，其實里面卻有不少的玄機。

應聘者在解決這個問題的時候，最容易想到的方法是先求出最大的n位數是什么，然后用個循環從

1開始逐個輸出。很快，我們就能寫出如下代碼：

//Printnumbersfrom1tothemaximumnumberwithndigits,inorder

voidPrint!ToMaxOfNDigits_l(intn)

//calculate10An

intnumber=1;

inti=0;

while(i++<n)

number*=10;

//printfrom1to(10An-1)

for(i=1;i<number;++i)

rt,,

printf(%d\tzi);

)

初看之3好像沒有問題。但如果我們仔細分析這個問題，就能注意到這里沒有規定n的范圍，當我

們求最大的n位數的時候，是不是有可能用整型甚至長整型都會溢出？

分析到這里，我們很自然的就想到我們需要表達?個大數。最常用的也是最容易實現的表達大數的方

法是用字符串或者整型數組(當然不一定是最有效的)。

用字符串表達數字的時候，最直觀的方法就是字符串里每個字符都是‘0'至『9'之間的某一個字符，表

示數字中的某一位。因為數字最大是n位的，因此我們需要一個n+1位字符串(最后一位為結束符號’

\0')o當實際數字不夠n位的時候，在字符串的前半部分補零。這樣，數字的個位永遠都在字符串的末

尾(除去結尾符號)。

首先我們把字符串中每一位數字都初始化為'0'。然后每一次對字符串表達的數字加1,再輸出。因

此我們只需要做兩件事：一是在字符串表達的數字上模擬加法。另外我們要把字符串表達的數字輸出。值

得注意的是，當數字不夠n位的時候，我們在數字的前面補零。輸出的時候這些補位的0不應該輸出。比

如輸入3的時候，那么數字98以098的形式輸出，就不符合我們的習慣了。

基于上述分析，我們可以寫出如下代碼：

//Printnumbersfrom1tothemaximumnumberwithndigits,inorder

voidPrintIToMaxOfNDigits_2(intn)

(

//0orminusnumbersareinvalidinput

if(n<=0)

return;

//numberisinitializedas0

char*number=newchar[n+1];

memset(number,'O',n);

number[n]=*\01;

while(!Increment(number))

(

PrintNumber(number);

delete[]number;

)

//Incrementanumber.Whenoverflow,returntrue;otherwisereturnfalse

boolIncrement(char*number)

boolisOverflow=false;

intnTakeOver=0;

intnLength=strlen(number);

//Increment(Add1)operationbeginsfromtheendofnumber

for(inti=nLength-1;i>=0;i-)

(

intnSum=number[i]-'01+nTakeOver;

if(i==nLength-1)

nSum++；

if(nSum>=10)

{

if(i==0)

isOverflow=true;

else

(

nSum-=10;

nTakeOver=1;

number[i]='01+nSum;

)

)

else

{

number[i]=*0*+nSum;

break;

)

)

returnisOverflow;

}

//Printnumberstoredinstring,ignore0atitsbeginning

//Forexample,print"0098"as"98"

voidPrintNumber(char*number)

{

boolisBeginningO=true;

intnLength=strlen(number);

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

if(isBeginningO&&number[i]!='0*)

isBeginningO=false;

if(!isBeginningO)

|

n

printf("%cznumber[i]);

)

)

printf(,,\tn);

)

第二種思路基本上和第一種思路相對應，只是把一個整型數值換成了字符串的表示形式。同時，值得

提出的是，判斷打印是否應該結束時；我沒有調用函數strcmp比較字符串number和"99...999"(n個9)。

這是因為strcmp的時間復雜度是O(n),而判斷是否溢出的平均時間復雜度是0(1)。

第二種思路雖然比較直觀，但由于模擬了整數的加法，代碼有點長。要在面試短短幾十分鐘時間里完

整正確寫出這么長代碼，不是件容易的事情。接下來我們換一種思路來考慮這個問題。如果我們在數字前

面補0的話，就會發現n位所有10進制數其實就是n個從。到9的全排列。也就是說，我們把數字的每一

位都從。到9排列一遍，就得到了所有的10進制數。只是我們在輸出的時候，數字排在前面的。我們不輸

出罷了。

全排列用遞歸很容易表達，數字的每一位都可能是。到9中的?個數，然后設置下?位。遞歸結束的

條件是我們已經設置了數字的最后一位。

//Printnumbersfrom1tothemaximumnumberwithndigits,inorder

voidPrintlToMaxOfNDigits_3(intn)

(

//0orminusnumbersareinvalidinput

if(n<=0)

return;

char*number=newchar[n+1];

number[n]=*\0*;

for(inti=0;i<10;++i)

(

//firstdigitcanbe0to9

number[0]=i+*0*;

PrintIToMaxOfNDigitsRecursively(number,n,0);

)

delete[]number;

}

//length:lengthofnumber

//index:currentindexofdigitinnumberforthisround

voidPrintIToMaxOfNDigitsRecursively(char*number,intlength,intindex)

//wehavereachedtheendofnumber,printit

if(index==length-1)

(

PrintNumber(number);

return;

)

for(inti=0;i<10;++i)

(

//nextdigitcanbe0to9

number[index+1]=i+10,;

//gotothenextdigit

PrintIToMaxOfNDigitsRecursively(number,length,index+1);

)

)

函數PrintNumber和前面第二種思路中的一樣，這里就不重復了。對比這兩種思路，我們可以發現，

遞歸能夠用很簡潔的代碼來解決問題。

程序員面試題精選100題(39)-顛倒棧

棧2009-05-3120:24:11閱讀5739評論10字號：大中小訂閱

題目:用遞歸顛倒?個棧。例如輸入棧｛1,2,3,4,5｝,1在棧頂。顛倒之后的棧為｛5,4,3,2,1｝,5處在

棧頂。

分析：乍一看到這道題目，第一反應是把棧里的所有元素逐一pop出來，放到一個數組里，然后在數

組里顛倒所有元素，最后把數組中的所有元素逐一push進入棧。這時棧也就顛倒過來了。顛倒一個數組是

一件很容易的事情。不過這種思路需要顯示分配一個長度為0(n)的數組而且也沒有充分利用遞歸的特性。

我們再來考慮怎么遞歸。我們把棧｛1,2,3,4,5｝看成由兩部分組成：棧頂元素1和剩卜的部分｛2,3,4,

5｝。如果我們能把｛2,3,4,5｝顛倒過來，變成｛5,4,3,2｝,然后在把原來的棧頂元素1放到底部，那么就整個

棧就顛倒過來了，變成｛5,4,3,2,1).

接下來我們需要考慮兩件事情：一是如何把｛2,3,4,5｝顛倒過來變成｛5,4,3,2｝。我們只要把｛2,3,4,5)

看成由兩部分組成：棧頂元素2和剩下的部分｛3,4,5｝。我們只要把｛3,4,5｝先顛倒過來變成｛5,4,3｝,然后再

把之前的棧頂元素2放到最底部，也就變成了｛5,4,3,2｝。

至于怎么把｛3,4,5｝顛倒過來……很多讀者可能都想到這就是遞歸。也就是每?次試圖顛倒?個棧的時

候，現在棧頂元素pop出來，再順倒剩下的元素組成的棧，最后把之前的棧頂元素放到剩下元素組成的棧

的底部。遞歸結束的條件是剩下的棧已經空了。這種思路的代碼如下：

//Reverseastackrecursivelyinthreesteps:

//1.Popthetopelement

//2.Reversetheremainingstack

//3.Addthetopelementtothebottomoftheremainingstack

template<typenameT>voidReversestack.(std::stack<T>&stack)

(

if(!stack.empty())

｛

Ttop=stack.top();

stack.pop();

Reversestack(stack);

AddToStackBottom(stack,top);

)

)

我們需要考慮的另外一件事情是如何把一個元素e放到一個棧的底部，也就是如何實現

AddToStackBottomo這件事情不難，只需要把棧里原有的元素逐一pop出來。當棧為空的時候，push

元素e進棧，此時它就位于棧的底部了。然后再把棧里原有的元素按照pop相反的順序逐一push進棧。

注意到我們在push元素e之前，我們已經把棧里原有的所有元素都pop出來了，我們需要把它們保

存起來，以便之后能把他們再push回去。我們當然可以開辟一個數組來做，但這沒有必要。由于我們可以

用遞歸來做這件事情，而遞歸本身就是一個棧結構。我們可以用遞歸的棧來保存這些元素。

基于如上分析，我們可以寫出AddToStackBottom的代碼：

//Addanelementtothebottomofastack:

tempiate<typenameT>voidAddToStackBottom(std::stack<T>&stack,Tt)

(

if(stack.empty())

(

stack.push(t);

)

else

(

Ttop=stack.top();

stack.pop();

AddToStackBottom(stack,t);

stack.push(top);

)

)

程序員面試題精選100題(40)-撲克牌的順子

數組2009-06-1218:29:30閱讀5480評論15字號：大中小訂閱

題目：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續的。2?10為數字本身，

A為1,J為11,Q為12,K為13,而大小王可以看成任意數字。

分析：這題目很有意思，是一個典型的寓教于樂的題目。

我們需要把撲克牌的背景抽象成計算機語言。不難想象，我們可以把5張牌看成由5個數字組成的數

組。大小王是特殊的數字，我們不妨把它們都當成0,這樣和其他撲克牌代表的數字就不重復了。

接下來我們來分析怎樣判斷5個數字是不是連續的。最直觀的是，我們把數組排序。但值得注意的是，

由于0可以當成任意數字，我們可以用。去補滿數組中的空缺。也就是排序之后的數組不是連續的，即相

鄰的兩個數字相隔若干個數字，但如果我們有足夠的。可以補滿這兩個數字的空缺，這個數組實際上還是

連續的。舉個例子，數組排序之后為{0,1,3,4,5}o在1和3之間空缺了一個2,剛好我們有一個0,

也就是我們可以它當成2去填補這個空缺。

于是我們需要做三件事情：把數組排序，統計數組中0的個數，統計排序之后的數組相鄰數字之間的

空缺總數。如果空缺的總數小于或者等于0的個數，那么這個數組就是連續的；反之則不連續。最后，我

們還需要注意的是，如果數組中的非。數字重復出現，則該數組不是連續的。換成撲克牌的描述方式，就

是如果?副牌里含有對子，則不可能是順子。

基于這個思路，我們可以寫出如下的代碼：

//Determinewhethernumbersinanarrayarecontinuous

//Parameters:numbers:anarray,eachnumberinthearrayisbetween

//0andmaxNumber.0canbetreetedasanynumberbetween

//1andmaxNumber

//maxNumber:themaximumnumberinthearraynumbers

boolIsContinuous(std::vector<int>numbers,intmaxNumber)

(

if(numbers.size()==0IImaxNumber<=0)

returnfalse;

//Sortthearraynumbers.

std::sort(numbers.begin(),numbers.end());

intnumberOfZero=0;

intnumberOfGap=0;

//howmany0sinthearray?

std::vector<int>::iteratorsmallerNumber=numbers.begin();

while(smallerNumber!=numbers.end()&&*smallerNumber==0)

numberOfZero++;

++smallerNumber;

//getthetotalgapsbetweenalladjacenttwonumbers

std::vector<int>::iteratorbiggerNumber=smallerNumber+1;

while(biggerNumber<numbers.end())

(

//ifanynon-zeronumberappearsmorethanonceinthearray,

//thearraycan*tbecontinuous

if(*biggerNumber==*smallerNumber)

returnfalse;

numberOfGap+=*biggerNumber-*smallerNumber-1;

smallerNumber=biggerNumber;

++biggerNumber;

}

return(numberOfGap>numberOfZero)?false:true;

}

本文為了讓代碼顯得比較簡潔,上述代碼用C++的標準模板庫中的vector來表達數組，同時用函數sort

排序。當然我們可以自己寫排序算法。為了有更好的通用性，上述代碼沒有限定數組的長度和允許出現的

最大數字。要解答原題，我們只需耍確保傳入的數組的長度是5,并且maxNumber為13即可。

程序員面試題精選100題(41)-把數組排成最小的數

數字游戲2009-06-2119:41:33閱讀6606評論33字號：大中小訂閱

題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的一個。例

如輸入數組{32,321},則輸出這兩個能排成的最小數字32132。請給出解決問題的算法，并證明該算法。

分析：這是09年6月份百度新鮮出爐的?道面試題，從這道題我們可以看出百度對應聘者在算法方

面有很高的要求。

這道題其實是希望我們能找到一個排序規則，根據這個規則排出來的數組能排成一個最小的數字。要

確定排序規則，就得比較兩個數字，也就是給出兩個數字m和n,我們需要確定一個規則m和n哪個更大，

而不是僅僅只是比較這兩個數字的數值哪個更大。

根據題目的要求，兩個數字m和n排成的數字mn和nm,如果mn<nm,那么我們應該輸出mn,也

就是m應該排在n的前面，也就是m小于反之，如果nm<mn,n小于m。如果mn==mn,m等