程序員面試題100題1

程序員面試題精選100題(34)-找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字

題目：-個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序

找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n),空間復(fù)雜度是0(1)。

分析：這是一道很新穎的關(guān)于位運(yùn)算的面試題。

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

數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這個(gè)只出現(xiàn)一次的數(shù)字。

這個(gè)題目的突破口在哪里？題目為什么要強(qiáng)調(diào)有一個(gè)數(shù)字出現(xiàn)一次，其他的出現(xiàn)

兩次？我們想到了異或運(yùn)算的性質(zhì)：任何一個(gè)數(shù)字異或它自己都等于0。也就是

說，如果我們從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那么最終的結(jié)果剛好是那

個(gè)只出現(xiàn)依次的數(shù)字，因?yàn)槟切┏霈F(xiàn)兩次的數(shù)字全部在異或中抵消掉了。

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

為兩個(gè)子數(shù)組。在每個(gè)子數(shù)組中，包含一個(gè)只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出

現(xiàn)兩次。如果能夠這樣拆分原數(shù)組，按照前面的辦法就是分別求出這兩個(gè)只出現(xiàn)

一次的數(shù)字了。

我們還是從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那么最終得到的結(jié)果就是兩個(gè)

只出現(xiàn)一次的數(shù)字的異或結(jié)果。因?yàn)槠渌麛?shù)字都出現(xiàn)了兩次，在異或中全部抵消

掉了。由于這兩個(gè)數(shù)字肯定不一樣，那么這個(gè)異或結(jié)果肯定不為0,也就是說在

這個(gè)結(jié)果數(shù)字的二進(jìn)制表示中至少就有一位為lo我們?cè)诮Y(jié)果數(shù)字中找到第一個(gè)

為1的位的位置，記為第N位?，F(xiàn)在我們以第N位是不是1為標(biāo)準(zhǔn)把原數(shù)組中

的數(shù)字分成兩個(gè)子數(shù)組，第一個(gè)子數(shù)組中每個(gè)數(shù)字的第N位都為1,而第二個(gè)子

數(shù)組的每個(gè)數(shù)字的第N位都為0o

現(xiàn)在我們已經(jīng)把原數(shù)組分成了兩個(gè)子數(shù)組，每個(gè)子數(shù)組都包含一個(gè)只出現(xiàn)一次的

數(shù)字，而其他數(shù)字都出現(xiàn)了兩次。因此到此為止，所有的問題我們都已經(jīng)解決。

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

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

//

//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)-找出兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)

鏈表2008-01-0515:16:09閱讀6477評(píng)論13字號(hào)：大中小訂閱

題目：兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。

鏈表的結(jié)點(diǎn)定義為：

structListNode

(

intm_nKey;

ListNode*m_pNext;

｝；

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

面試題中，鏈表出現(xiàn)的概率相當(dāng)高。

如果兩個(gè)單向鏈表有公共的結(jié)點(diǎn)，也就是說兩個(gè)鏈表從某一結(jié)點(diǎn)開始，它們的

m_pNext都指向同一個(gè)結(jié)點(diǎn)。但由于是單向鏈表的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只有一個(gè)

m_pNext,因此從第一個(gè)公共結(jié)點(diǎn)開始，之后它們所有結(jié)點(diǎn)都是重合的，不可能

再出現(xiàn)分叉。所以，兩個(gè)有公共結(jié)點(diǎn)而部分重合的鏈表，拓?fù)湫螤羁雌饋硐褚粋€(gè)

Y,而不可能像X。

看到這個(gè)題目，第一反應(yīng)就是蠻力法：在第一鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。每遍歷

一個(gè)結(jié)點(diǎn)的時(shí)候，在第二個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。如果此時(shí)兩個(gè)鏈表上的結(jié)

點(diǎn)是一樣的，說明此時(shí)兩個(gè)鏈表重合，于是找到了它們的公共結(jié)點(diǎn)。如果第一個(gè)

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

接下來我們?cè)囍ふ乙粋€(gè)線性時(shí)間復(fù)雜度的算法。我們先把問題簡化：如何判

斷兩個(gè)單向鏈表有沒有公共結(jié)點(diǎn)？前面已經(jīng)提到，如果兩個(gè)鏈表有一個(gè)公共結(jié)

點(diǎn)，那么該公共結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都是重合的。那么，它們的最后一個(gè)結(jié)點(diǎn)必

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

鏈表到最后一個(gè)結(jié)點(diǎn)。如果兩個(gè)尾結(jié)點(diǎn)是一樣的，說明它們用重合；否則兩個(gè)鏈

表沒有公共的結(jié)點(diǎn)。

在上面的思路中，順序遍歷兩個(gè)鏈表到尾結(jié)點(diǎn)的時(shí)候，我們不能保證在兩個(gè)鏈表

上同時(shí)到達(dá)尾結(jié)點(diǎn)。這是因?yàn)閮蓚€(gè)鏈表不一定長度一樣。但如果假設(shè)一個(gè)鏈表比

另一個(gè)長I個(gè)結(jié)點(diǎn)，我們先在長的鏈表上遍歷I個(gè)結(jié)點(diǎn)，之后再同步遍歷，這個(gè)

時(shí)候我們就能保證同時(shí)到達(dá)最后一個(gè)結(jié)點(diǎn)了。由于兩個(gè)鏈表從第一個(gè)公共結(jié)點(diǎn)考

試到鏈表的尾結(jié)點(diǎn)，這一部分是重合的。因此，它們肯定也是同時(shí)到達(dá)第一公共

結(jié)點(diǎn)的。于是在遍歷中，第一個(gè)相同的結(jié)點(diǎn)就是第一個(gè)公共的結(jié)點(diǎn)。

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

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

點(diǎn)，或者一直到鏈表結(jié)束。此時(shí)，如果第一個(gè)鏈表的長度為m,第二個(gè)鏈表的長

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

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

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

//

//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評(píng)論15字號(hào)：大中小訂閱

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

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

stdnts/o

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

很大的一部分，因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟Α?/p>

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

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

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

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

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

首先我們考慮如何在字符串中刪除一個(gè)字符。由于字符串的內(nèi)存分配方式是連續(xù)

分配的。我們從字符串當(dāng)中刪除一個(gè)字符，需要把后面所有的字符往前移動(dòng)一個(gè)

字節(jié)的位置。但如果每次刪除都需要移動(dòng)字符串后面的字符的話，對(duì)于一個(gè)長度

為n的字符串而言，刪除一個(gè)字符的時(shí)間復(fù)雜度為0(n)。而對(duì)于本題而言，有可

能要?jiǎng)h除的字符的個(gè)數(shù)是n,因此該方法就刪除而言的時(shí)間復(fù)雜度為OS?)。

事實(shí)上，我們并不需要在每次刪除一個(gè)字符的時(shí)候都去移動(dòng)后面所有的字符。我

們可以設(shè)想，當(dāng)一個(gè)字符需要被刪除的時(shí)候，我們把它所占的位置讓它后面的字

符來填補(bǔ)，也就相當(dāng)于這個(gè)字符被刪除了。在具體實(shí)現(xiàn)中，我們可以定義兩個(gè)指

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

符是需要?jiǎng)h除的字符，則pFast直接跳過，指向下一個(gè)字符。如果pFast指向的

字符是不需要?jiǎng)h除的字符，那么把pFast指向的字符賦值給pSIow指向的字符，

并且pFast和pStart同時(shí)向后移動(dòng)指向下一個(gè)字符。這樣，前面被pFast跳過的

字符相當(dāng)于被刪除了。用這種方法，整個(gè)刪除在0(n)時(shí)間內(nèi)就可以完成。

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

頭到尾掃描整個(gè)字符串。顯然，這種方法需要一個(gè)循環(huán)，對(duì)于一個(gè)長度為n的字

符串，時(shí)間復(fù)雜度是0(n)。

由于字符的總數(shù)是有限的。對(duì)于八位的char型字符而言，總共只有28=256個(gè)字

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

字符串中每一個(gè)字符，把它的ASCII碼映射成索引，把數(shù)組中該索引對(duì)應(yīng)的元素

設(shè)為1。這個(gè)時(shí)候，要查找一個(gè)字符就變得很快了：根據(jù)這個(gè)字符的ASCII碼，

在數(shù)組中對(duì)應(yīng)的下標(biāo)找到該元素，如果為0,表示字符串中沒有該字符，否則字

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

就是一個(gè)hash表。這種思路的詳細(xì)說明，詳見本面試題系列的第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)-尋找丑數(shù)

數(shù)字游戲2009-05-2417:36:06閱讀5857評(píng)論12字號(hào)：大中小訂閱

題目：我們把只包含因子

2、3和5的數(shù)稱作丑數(shù)(UglyNumber)。例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。習(xí)慣上我

們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第1500個(gè)丑數(shù)。

分析：這是?道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。

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

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

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

是。

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

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;

}

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

intGetUglyNumber_Solutionl(intindex)

(

if(index<=0)

return0;

intnumber=0;

intuglyFound=0;

while(uglyFound<index)

(

++number;

if(IsUgly(number))

++uglyFound;

}

returnnumber;

)

我們只需要在函數(shù)GetUglyNumber_Solutionl中傳入?yún)?shù)1500,就能得到第1500個(gè)丑數(shù)。該算

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

是需要對(duì)它做求余數(shù)和除法操作。因此該算法的時(shí)間效率不是很高。

接下來我們換一種思路來分析這個(gè)問題，試圖只計(jì)算丑數(shù)，而不在非丑數(shù)的整數(shù)上花費(fèi)時(shí)間。根據(jù)丑

數(shù)的定義，丑數(shù)應(yīng)該是另一個(gè)丑數(shù)乘以2、3或者5的結(jié)果(1除外)。因此我們可以創(chuàng)建一個(gè)數(shù)組，里面

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

這種思路的關(guān)鍵在于怎樣確保數(shù)組里面的丑數(shù)是排好序的。我們假設(shè)數(shù)組中已經(jīng)有若干個(gè)丑數(shù)，排好

序后存在數(shù)組中。我們把現(xiàn)有的最大丑數(shù)記做M?，F(xiàn)在我們來生成下一個(gè)丑數(shù)，該丑數(shù)肯定是前面某一個(gè)

丑數(shù)乘以2、3或者5的結(jié)果。我們首先考慮把已有的每個(gè)丑數(shù)乘以2。在乘以2的時(shí)候，能得到若干個(gè)結(jié)

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

考慮；我們還會(huì)得到若干個(gè)大于M的結(jié)果，但我們只需要第一個(gè)大于M的結(jié)果，因?yàn)槲覀兿Ｍ髷?shù)是按

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

同樣我們把已有的每一個(gè)丑數(shù)乘以和能得到第一個(gè)大于的結(jié)果和那么下一個(gè)丑數(shù)應(yīng)

M2?35,MM3M”

該是M2、M3和Ms三個(gè)數(shù)的最小者。

前面我們分析的時(shí)候，提到把已有的每個(gè)丑數(shù)分別都乘以2、3和5,事實(shí)上是不需要的，因?yàn)橐延械?/p>

丑數(shù)是按順序存在數(shù)組中的。對(duì)乘以2而言，肯定存在某一個(gè)丑數(shù)Tz，排在它之前的每一個(gè)丑數(shù)乘以2得

到的結(jié)果都會(huì)小于已有最大的丑數(shù)，在它之后的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)太大。我們只需要記下

這個(gè)丑數(shù)的位置，同時(shí)每次生成新的丑數(shù)的時(shí)候，去更新這個(gè)對(duì)乘以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;

}

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

趣的讀者可以分別統(tǒng)計(jì)兩個(gè)函數(shù)GetUglyNumber_Solutionl(1500)和

GetUg1yNumber_Solution2(1500)的運(yùn)行時(shí)間。當(dāng)然我們也要指出，第二種算法由于要保存已經(jīng)生成

的丑數(shù)，因此需要?個(gè)數(shù)組，從而需要額外的內(nèi)存。第?種算法是沒有這樣的內(nèi)存開銷的。

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

數(shù)字游戲2009-05-2709:42:06閱讀5076評(píng)論4字號(hào)：大中小訂閱

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

位數(shù)即999。

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

應(yīng)聘者在解決這個(gè)問題的時(shí)候，最容易想到的方法是先求出最大的n位數(shù)是什么，然后用個(gè)循環(huán)從

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

//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好像沒有問題。但如果我們仔細(xì)分析這個(gè)問題，就能注意到這里沒有規(guī)定n的范圍，當(dāng)我

們求最大的n位數(shù)的時(shí)候，是不是有可能用整型甚至長整型都會(huì)溢出？

分析到這里，我們很自然的就想到我們需要表達(dá)?個(gè)大數(shù)。最常用的也是最容易實(shí)現(xiàn)的表達(dá)大數(shù)的方

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

用字符串表達(dá)數(shù)字的時(shí)候，最直觀的方法就是字符串里每個(gè)字符都是‘0'至『9'之間的某一個(gè)字符，表

示數(shù)字中的某一位。因?yàn)閿?shù)字最大是n位的，因此我們需要一個(gè)n+1位字符串(最后一位為結(jié)束符號(hào)’

\0')o當(dāng)實(shí)際數(shù)字不夠n位的時(shí)候，在字符串的前半部分補(bǔ)零。這樣，數(shù)字的個(gè)位永遠(yuǎn)都在字符串的末

尾(除去結(jié)尾符號(hào))。

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

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

得注意的是，當(dāng)數(shù)字不夠n位的時(shí)候，我們?cè)跀?shù)字的前面補(bǔ)零。輸出的時(shí)候這些補(bǔ)位的0不應(yīng)該輸出。比

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

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

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

)

第二種思路基本上和第一種思路相對(duì)應(yīng)，只是把一個(gè)整型數(shù)值換成了字符串的表示形式。同時(shí)，值得

提出的是，判斷打印是否應(yīng)該結(jié)束時(shí)；我沒有調(diào)用函數(shù)strcmp比較字符串number和"99...999"(n個(gè)9)。

這是因?yàn)閟trcmp的時(shí)間復(fù)雜度是O(n),而判斷是否溢出的平均時(shí)間復(fù)雜度是0(1)。

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

整正確寫出這么長代碼，不是件容易的事情。接下來我們換一種思路來考慮這個(gè)問題。如果我們?cè)跀?shù)字前

面補(bǔ)0的話，就會(huì)發(fā)現(xiàn)n位所有10進(jìn)制數(shù)其實(shí)就是n個(gè)從。到9的全排列。也就是說，我們把數(shù)字的每一

位都從。到9排列一遍，就得到了所有的10進(jìn)制數(shù)。只是我們?cè)谳敵龅臅r(shí)候，數(shù)字排在前面的。我們不輸

出罷了。

全排列用遞歸很容易表達(dá)，數(shù)字的每一位都可能是。到9中的?個(gè)數(shù)，然后設(shè)置下?位。遞歸結(jié)束的

條件是我們已經(jīng)設(shè)置了數(shù)字的最后一位。

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

)

)

函數(shù)PrintNumber和前面第二種思路中的一樣，這里就不重復(fù)了。對(duì)比這兩種思路，我們可以發(fā)現(xiàn)，

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

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

棧2009-05-3120:24:11閱讀5739評(píng)論10字號(hào)：大中小訂閱

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

棧頂。

分析：乍一看到這道題目，第一反應(yīng)是把棧里的所有元素逐一pop出來，放到一個(gè)數(shù)組里，然后在數(shù)

組里顛倒所有元素，最后把數(shù)組中的所有元素逐一push進(jìn)入棧。這時(shí)棧也就顛倒過來了。顛倒一個(gè)數(shù)組是

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

我們?cè)賮砜紤]怎么遞歸。我們把棧｛1,2,3,4,5｝看成由兩部分組成：棧頂元素1和剩卜的部分｛2,3,4,

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

棧就顛倒過來了，變成｛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｝顛倒過來……很多讀者可能都想到這就是遞歸。也就是每?次試圖顛倒?個(gè)棧的時(shí)

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

的底部。遞歸結(jié)束的條件是剩下的棧已經(jīng)空了。這種思路的代碼如下：

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

)

)

我們需要考慮的另外一件事情是如何把一個(gè)元素e放到一個(gè)棧的底部，也就是如何實(shí)現(xiàn)

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

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

注意到我們?cè)趐ush元素e之前，我們已經(jīng)把棧里原有的所有元素都pop出來了，我們需要把它們保

存起來，以便之后能把他們?cè)賞ush回去。我們當(dāng)然可以開辟一個(gè)數(shù)組來做，但這沒有必要。由于我們可以

用遞歸來做這件事情，而遞歸本身就是一個(gè)棧結(jié)構(gòu)。我們可以用遞歸的棧來保存這些元素。

基于如上分析，我們可以寫出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)-撲克牌的順子

數(shù)組2009-06-1218:29:30閱讀5480評(píng)論15字號(hào)：大中小訂閱

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

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

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

我們需要把撲克牌的背景抽象成計(jì)算機(jī)語言。不難想象，我們可以把5張牌看成由5個(gè)數(shù)字組成的數(shù)

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

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

由于0可以當(dāng)成任意數(shù)字，我們可以用。去補(bǔ)滿數(shù)組中的空缺。也就是排序之后的數(shù)組不是連續(xù)的，即相

鄰的兩個(gè)數(shù)字相隔若干個(gè)數(shù)字，但如果我們有足夠的?？梢匝a(bǔ)滿這兩個(gè)數(shù)字的空缺，這個(gè)數(shù)組實(shí)際上還是

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

也就是我們可以它當(dāng)成2去填補(bǔ)這個(gè)空缺。

于是我們需要做三件事情：把數(shù)組排序，統(tǒng)計(jì)數(shù)組中0的個(gè)數(shù)，統(tǒng)計(jì)排序之后的數(shù)組相鄰數(shù)字之間的

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

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

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

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

//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++的標(biāo)準(zhǔn)模板庫中的vector來表達(dá)數(shù)組，同時(shí)用函數(shù)sort

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

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

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

數(shù)字游戲2009-06-2119:41:33閱讀6606評(píng)論33字號(hào)：大中小訂閱

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

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

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

面有很高的要求。

這道題其實(shí)是希望我們能找到一個(gè)排序規(guī)則，根據(jù)這個(gè)規(guī)則排出來的數(shù)組能排成一個(gè)最小的數(shù)字。要

確定排序規(guī)則，就得比較兩個(gè)數(shù)字，也就是給出兩個(gè)數(shù)字m和n,我們需要確定一個(gè)規(guī)則m和n哪個(gè)更大，

而不是僅僅只是比較這兩個(gè)數(shù)字的數(shù)值哪個(gè)更大。

根據(jù)題目的要求，兩個(gè)數(shù)字m和n排成的數(shù)字mn和nm,如果mn<nm,那么我們應(yīng)該輸出mn,也

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