rquwlsx題目輸入一棵二元查找樹將該轉(zhuǎn)換成一個排序的雙向鏈表

//Covertasubbinary-search-treeintoasorteddouble-linked//Input:pNode-theheadofthesub asRight-whetherpNodeistherightchildofits//Output:ifasRightistrue,returntheleastnodeinthesub- elsereturnthegreatestnodeinthesub-BSTreeNode*ConvertNode(BSTreeNode*pNode,bool{returnBSTreeNode*pLeft=NULL;BSTreeNode*pRight=//Converttheleftsub-treepLeft=ConvertNode(pNode->m_pLeft,//Connectthegreatestnodeintheleftsub-treetothecurrentnode{pLeft->m_pRight=pNode;pNode->m_pLeft=pLeft;}//Converttherightsub-treepRight=ConvertNode(pNode->m_pRight,//Connecttheleastnodeintherightsub-treetothecurrentnode{pNode->m_pRight=pRight;pRight->m_pLeft=pNode;}BSTreeNode*pTemp=//Ifthecurrentnodeistherightchildofits//returntheleastnodeinthetreewhoserootisthecurrent{pTemp=pTemp->m_pLeft;}//Ifthecurrentnodeistheleftchildofits//returnthegreatestnodeinthetreewhoserootisthecurrentnode{pTemp=pTemp->m_pRight;}return}//Covertabinarysearchtreeintoasorteddouble-linked//Input:theheadof//Output:theheadofsorteddouble-linkedBSTreeNode*Convert(BSTreeNode*{//Aswewanttoreturntheheadofthesorteddouble-linked//wesetthesecondparametertobetruereturnConvertNode(pHeadOfTree,true);}//Covertasubbinary-search-treeintoasorteddouble-linked//Input:pNode theheadofthesub stNodeInList-thetailofthedouble-linkedvoidConvertNode(BSTreeNode*pNode, {if(pNode==NULL)BSTreeNode*pCurrent=//Converttheleftsub-treeif(pCurrent->m_pLeft!=NULL)//Putthecurrentnodeintothedouble-linkedlistpCurrent->m_pLeft=stNodeInList;if(stNodeInList!=NULL)stNodeInList->m_pRight=pCurrent;stNodeInList=pCurrent;//Converttherightsub-treeif(pCurrent->m_pRight!=NULL)}//Covertabinarysearchtreeintoasorteddouble-linked//Input:pHeadOfTree-theheadof//Output:theheadofsorteddouble-linked{BSTreeNode*stNodeInList=NULL;//Gettheheadofthedouble-linkedlistBSTreeNode*pHeadOfList=stNodeInList;while(pHeadOfList&&pHeadOfList->m_pLeft)pHeadOfList=pHeadOfList->m_pLeft;return}程序員面試題精選100題(02)－設(shè)計(jì)包含min函數(shù)的pop的時間復(fù)雜度都是O(1)分析：這是去年的一道面試題push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素將push進(jìn)棧的元素最先出棧，這種思路設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個棧在棧里添加一個成員變量存放最小元素（或最小元素的位置）push一個新元素進(jìn)棧的時候，如果乍一看這樣思路挺好的。但仔細(xì)，該思路存在一個重要的問題：如果當(dāng)前最小元素被pop出去，如何構(gòu)，用最小元素的位置將能減少空間消耗）pushpoppop#include<deque>temte<typenameT>class{virtual~CStackWithMin(void)T&constT&top(void)voidpush(constT&value);voidpop(void);constT&min(void)T>m_data;//theelementsofstacksize_t>m_minIndex;//theindicesofminimumelements//getthelastelementofmutabletemte<typenameT>T&{return}//getthelastelementofnon-mutabletemte<typenameT>constT&CStackWithMin<T>::top(){return}//insertanelmentattheendof te<typenameT>voidCStackWithMin<T>::push(constT&{//appendthedataintotheendofm_data//settheindexofminimumelmentinm_dataattheendofm_minIndexif(m_minIndex.size()==0){if(value<m_data[m_minIndex.back()])m_minIndex.push_back(m_data.size()-1);}}//ereasetheelementattheendof te<typenameT>void{//popm_data//popm_minIndex}//gettheminimumelementoftemte<typenameT>constT&CStackWithMin<T>::min(){assert(m_data.size()>assert(m_minIndex.size()>return}33034322112300兩個版本的top函數(shù)。在很多類中，都需要提供const和非const版本的成員函數(shù)小輔助棧；若大于當(dāng)前最小元素，則將它進(jìn)棧，并將當(dāng)前最小元素index進(jìn)最程序員面試題精選100題(03)－求子數(shù)組2006年程序員n//Findthegreatestsumofallsub-int //anunsignedintnLength,//thelengthofint //thegreatestsumofallsub-){//iftheinputisinvalid,returnfalseif((pData==NULL)||(nLength==0))returnintnCurSum=nGreatestSum=0;for(unsignedinti=0;i<nLength;++i){nCurSum+=//ifthecurrentsumisnegative,discarditif(nCurSum<0)nCurSum=//ifagreatersumisfound,updatethegreatestsumif(nCurSum>nGreatestSum)nGreatestSum=}//ifalldataarenegative,findthegreatestelementinthearrayif(nGreatestSum==0){nGreatestSum=for(unsignedinti=1;i<nLength;{if(pData[i]>nGreatestSum)nGreatestSum=}}return}0？那這個函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個考慮，本人認(rèn)為把子數(shù)組和的最大值以的方式采用類似分治算法的道理：前i個元素中，最大綜合子數(shù)組要么在i-個元素中(maxsofar)，要么截止到位置i(andngere)程序員面試題精選

100題(04)－在二元樹中找出和為某一/ 則打印出兩條路徑：10121057。structBinaryTreeNode//anodeinthebinary{ m_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode當(dāng)?shù)侥骋唤Y(jié)點(diǎn)時，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路繼續(xù)它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點(diǎn)。因此我們在函數(shù)退出之前要在//Findpathswhosesumequaltoexpected //anodeofbinarytree expectedSum,//theexpectedsum //apathfromroottocurrentnode //thesumofpath){currentSum+=pTreeNode-//ifthenodeisaleaf,andthesumissameaspre-//thepathiswhatwewant.printtheboolisLeaf=(!pTreeNode->m_pLeft&&!pTreeNode->m_pRight);if(currentSum==expectedSum&&isLeaf){std::vector<int>::itoriter=path.begin();for(;iter!=path.end();++iter)}//ifthenodeisnotaleaf,gotoitschildrenFindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum);//whenwefinishvisitinganodeandreturntoitsparent//weshoulddeletethisnodefromthepath//minusthenode'svaluefromthecurrentsumcurrentSum-=pTreeNode->m_nValue;}程序員面試題精選100題(05)－查找最小的k個題目：輸入n個整數(shù)，輸出其中最小的kkk的數(shù)組已經(jīng)滿了，不能再往數(shù)組里插入元素，只k個整數(shù)的最大值要小，則用讀入的這個整數(shù)替換這個最大kO(n+nlogk)。通常情況下k要遠(yuǎn)小于n，所以這種辦法要優(yōu)于前面的思路。k的數(shù)組已經(jīng)滿了之后，如果需要替換，每次替換的都是數(shù)組明出來了。同樣，STLsetmultiset為我們做了很好的堆的實(shí)現(xiàn)，我們可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印象，何樂而不為之？#include<set>#include<vector>usingnamespacetypedefmultiset<int,greater<int>>//findkleastnumbersinaconstvector<int>& //avectorofIntHeap&leastNumbers, //kleastnumbers,outputunsignedintk){if(k==0||data.size()<k) toriter=data.begin();for(;iter!=data.end();++iter){//iflessthanknumberswasinsertedintoleastNumbersif((leastNumbers.size())<k)//leastNumberscontainsknumbersandit'sfullnow{//firstnumberinleastNumbersisthegreatestoneIntHeap::itoriterFirst=//ifislessthanthepreviousgreatestnumberif(*iter<*(leastNumbers.begin())){//recethepreviousgreatestnumber}}}}程序員面試題精選100題(06)－判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果回false。 8/ / / 9因此返回true分析：這是一道trilogy的筆試題，主要考查對二元查找樹的理解。usingnamespace//Verifywhetherasquenceofintegersarethepostorder//ofabinarysearchtree//Input:squence-thesquenceof length-thelengthof//Return:returntureifthesquenceistraversalresultofa otherwise,returnboolverifySquenceOfBST(intsquence[],int{if(squence==NULL||length<=0)returnfalse;//rootofaBSTisattheendofpostordertraversalsquenceintroot=squence[length-1];//thenodesinleftsub-treearelessthantherootinti=0;for(;i<length-1;++{if(squence[i]>root)}//thenodesintherightsub-treearegreaterthantherootintj=i;for(;j<length-1;++{if(squence[j]<root)returnfalse;}//verifywhethertheleftsub-treeisaBSTboolleft=true;if(i>left=verifySquenceOfBST(squence,//verifywhethertherightsub-treeisaBSTboolright=true;if(i<length-right=verifySquenceOfBST(squence+i,length-i-return(left&&}程序員面試題精選100題(07)－翻轉(zhuǎn)句子中單詞的順例如輸入“Iamastudent.”，則輸出“studentaamI還是以上面的輸入為例子。翻轉(zhuǎn)“Iamastudent.”中所有字符得到“.tnedutsamaI”，再翻轉(zhuǎn)每個單詞中字符的順序得到“students.aamI”，正是符合要求的輸出。//Reverseastringbetweentwo//Input:pBegin-thebeginpointerina pEnd-theendpointerinavoidReverse(char*pBegin,char{if(pBegin==NULL||pEnd==NULL)while(pBegin<{chartemp=*pBegin=*pEnd=pBegin++,pEnd--}}//Reversethewordorderinasentence,butmaintainthe//orderinsidea//Input:pData-thesentencetobechar*ReverseSentence(char{if(pData==NULL)returnNULL;char*pBegin=pData;char*pEnd=pData;while(*pEnd!='\0')pEnd++;//ReversethewholesentenceReverse(pBegin,pEnd);//ReverseeverywordinthesentencepBegin=pEnd=pData;while(*pBegin!={if(*pBegin=='{pEnd++;}//AwordisbetweenwithpBeginandpEnd,reverseitelseif(*pEnd==''||*pEnd=='\0'){pBegin=++pEnd;}{pEnd}}return}程序員面試題精選100題(08通常求1+2+…+n除了用n(n+1)/2之外，無外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和whileif語句或者條件判斷語句來判斷是繼續(xù)遞歸下去我們?nèi)匀粐@循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達(dá)到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個思路：class{Temp(){++N;Sum+=N;staticvoidReset(){N=0;Sum=0;}staticintGetSum(){returnSum;}staticintN;staticintSum;intTemp::N=0;intTemp::Sum=0;intsolution1_Sum(int{Temp*a=newTemp[n];delete[]a;a=return}（）（n轉(zhuǎn)換成布爾值。如果對n，那么非零的n為r0轉(zhuǎn)換為fsclassA*class{virtualintSum(intn){return0;classB:public{virtualintSum(intn){returnArray[!!n]->Sum(n-1)+n;intsolution2_Sum(int{ABArray[0]=Array[1]=intvalue=Array[1]-return}typedefintintsolution3_f1(int{return}intsolution3_f2(int{funf[2]={solution3_f1,solution3_f2};returni+f[!!i](i-1);} te<intn>struct{enumValue{N=solution4_Sum<n-1>::N+temte<>struct{enumValue{N=為參數(shù)的類型，因?yàn)閟olution4_Sum<100>::N=solution4_Sum<99>::N+100。這個過程會1的類型，由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸編譯到此結(jié)束。由于這個n必須是在編譯期間就能確定，不能動態(tài)輸入。這是該方法最大的缺點(diǎn)。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。P:intfunc(int{intreturni;}程序員面試題精選100題(09)－查找鏈表中倒數(shù)k個結(jié)struct{ kk步。可是輸入的是n個結(jié)點(diǎn)，那么kn-k-1個結(jié)點(diǎn)（0開始計(jì)數(shù)）。如果我們能夠得到鏈表中結(jié)點(diǎn)的個數(shù)n，那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。如何得到結(jié)點(diǎn)數(shù)n？這個不難，只需要從頭開始點(diǎn)開始的第n-k-1個結(jié)點(diǎn)即倒數(shù)第k個結(jié)點(diǎn)。1？如果可以，將k-1步之前，第二個指針保持不動；在第k-1k-1，當(dāng)?shù)谝粋€（走面的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時，第二個指針（走在后面的）指針正好是倒數(shù)第k個結(jié)//Findthekthnodefromthetailofa//Input:pListHead-theheadof -thedistancetothe//Output:thekthnodefromthetailofa{if(pListHead==NULL)returnNULL;//countthenodesnumberinthelistListNode*pCur=pListHead;unsignedintnNum=0;while(pCur->m_pNext!=NULL){pCur=pCur->m_pNext;nNum++;}//ifthenumberofnodesinthelistislessthan//donothingif(nNum<k)return//thekthnodefromthetailofa//isthe(n-k)thnodefromtheheadpCur=pListHead;for(unsignedinti=0;i<nNum-k;++i)pCur=pCur->m_pNext;return}//Findthekthnodefromthetailofa//Input:pListHead-theheadof -thedistancetothe//Output:thekthnodefromthetailofa{if(pListHead==NULL)returnNULL;ListNode*pAhead=pListHead;ListNode*pBehind=NULL;for(unsignedinti=0;i<k;++{if(pAhead->m_pNext!=NULL)pAhead=pAhead->m_pNext;{//ifthenumberofnodesinthelistislessthan//donothingreturnNULL;}}pBehind=//thedistancebetweenpAheadandpBehindis//whenpAheadarrivesatthetail,//Behindisatthekthnodefromthetailwhile(pAhead->m_pNext!=NULL){pAhead=pAhead->m_pNext;pBehind=pBehind->m_pNext;}return}用小于還是小于等于？是該用k還是該用k-101減1、邊界值加1都運(yùn)行一次（在紙上寫代碼就只能在心里運(yùn)行了）。程序員面試題選值的兩個數(shù)

100題(10)－在排序數(shù)組中查找和為給 下的n-1個數(shù)字與它的和是不是等于輸入的數(shù)字?？上н@種思路需要的時間復(fù)雜度是O(n2)。//Findtwonumberswithasuminasorted//Output:tureisfoundsuchtwonumbers,otherwiseint //asortedunsignedintlength,//thelengthofthesortedarrayintsum, //thesumint& //thefirstnumber,int& //thesecondnumber,){boolfound=false;if(length<1)returnintahead=length-1;intbehind=0;while(ahead>{longlongcurSum=data[ahead]+//ifthesumoftwonumbersisequaltothe//wehavefoundthemif(curSum==sum){num1=data[behind];num2=data[ahead];found=true;}//ifthesumoftwonumbersisgreaterthanthe//decreasethegreaternumberelseif(curSum>sum)ahead--//ifthesumoftwonumbersislessthanthe//increasethelessnumberbehind}return}0k，在新數(shù)組中k-min1O(n)的時間內(nèi)把原數(shù)組轉(zhuǎn)換為一個排好序的程序員面試題精選100題(11)－求二元查找樹的鏡8/ 5 98/ 1197structBSTreeNode//anodeinthebinarysearchtree{ m_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode左右子樹。我們試著在遍歷例子中的二元查找樹的同時來交換每個結(jié)點(diǎn)的左右子樹。遍歷時首先頭結(jié)8，我們交換它的左右子樹得到：8/ 9115610的左右子樹仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們再試著交換他們的左右子8/ 11 7//MirroraBST(swaptheleftrightchildofeachnode)//theheadofBSTininitial{//swaptherightandleftchildsub-treeBSTreeNode*pTemp=pNode->m_pLeft;pNode->m_pLeft=pNode->m_pRight;pNode->m_pRight=//mirrorleftchildsub-treeifnotnull//mirrorrightchildsub-treeifnotnull}//MirroraBST(swaptheleftrightchildofeachnode)I//Input:pTreeHead:theheadofvoid tively(BSTreeNode{{BSTreeNode*pNode=stackTreeNode.top();//swaptherightandleftchildsub-treeBSTreeNode*pTemp=pNode->m_pLeft;pNode->m_pLeft=pNode->m_pRight;pNode->m_pRight=//pushleftchildsub-treeintostackifnotnull//pushrightchildsub-treeintostackifnot}}程序員面試題精選100題(12)－從上往下遍歷二元8/6/6596579#include<deque>#include<iostream>usingnamespacestructBTreeNode//anodeinthebinary{ m_nValue;//valueofnodeBTreeNode*m_pLeft;//leftchildofnodeBTreeNode*m_pRight;//rightchildofnode//Printabinarytreefromtopleveltobottom//Input:pTreeRoot-therootofbinary{//getaemptyqueuedeque<BTreeNode*>dequeTreeNode;//inserttherootatthetailofqueue{//getanodefromtheheadofqueueBTreeNode*pNode=dequeTreeNode.front();//printthecout<<pNode->m_nValue<<'//printitsleftchildsub-treeifithas//printitsrightchildsub-treeifithas}}程序員面試題精選100題(13)－第一個只出現(xiàn)題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。分析：這道題是2006年的一道筆試題。大小為256，以字符ASCII碼為鍵值的哈希表。//Findthefirstcharwhichappearsonlyonceina//Input:pString-the//Output:thefirstnotrepeatingcharifthestringhas,otherwise{//invalidinputreturn//getahashtable,andinitializeitconstinttableSize=256;for(unsignedinti=0;i<tableSize;++i)hashTable[i]=0;//getthehowmanytimeseachcharappearsinthestringchar*pHashKey=pString;while(*(pHashKey)!='\0')//findthefirstcharwhichappearsonlyonceinastringpHashKey=pString;while(*pHashKey!={if(hashTable[*pHashKey]==1)return*pHashKey;}//ifthestringis//oreverycharinthestringappearsatleasttwicereturn0;}程序員面試題精選100題(14)－圓圈中最后剩下的數(shù)除第m個數(shù)字。求出在這個圓圈中剩下的最后一個數(shù)字。構(gòu)中，我們很容易想到用環(huán)形列表。我們可以創(chuàng)建一個總共有m個數(shù)字的環(huán)形列表，然后每次從這個列表中刪除第m個元素。STLstd::listlist并不是一個環(huán)形的結(jié)構(gòu)，因此每次這種思路需要一個有n個結(jié)點(diǎn)的環(huán)形列表來模擬這個刪除的過程，因此內(nèi)存開銷為O(n)。而且這種方法每刪除一個數(shù)字需要m步運(yùn)算，總共有n個數(shù)字，因此總的時間復(fù)雜度是O(mn)。當(dāng)m和n都很大的時候，接下來我們試著從數(shù)學(xué)上分析出一些規(guī)律。首先定義最初的n個數(shù)字（0,1,…,n-1）中最后剩下的數(shù)字是關(guān)于n和m的方程為f(n,m)。在這n個數(shù)字中，第一個被刪除的數(shù)字是m%n-1，為簡單起見記為k。那么刪除k之后的剩下n-1的數(shù)字0,1,…,k-1,k+1,…,n-1，并且下一個開始計(jì)數(shù)的數(shù)字是k+1。相當(dāng)于在剩下的序列中，k+1排到最前面，k+1,…,n-1,0,…k-1nm的函數(shù)。由于這個序列的規(guī)律和前面最初的序列不一樣（0開始的連續(xù)序列），因此該函數(shù)不同于前面函數(shù)，記為到n-2 - - …n- - …k- - 把映射定義為p，則p(x)=(x-k-1)%n，即如果映射前的數(shù)字是x，則映射后的數(shù)字是(x-k-1)%n。對應(yīng)的逆0f來表f(n-1,m。根據(jù)我們的映射規(guī)則，映射之前的序列最后剩下的數(shù)字f’(n-1,m)=p-1f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。經(jīng)過上面復(fù)雜的分析，我們終于找到一個遞歸的。要得到n個數(shù)字的序列的最后剩下的數(shù)字，只需要得到n-1個數(shù)字的序列的最后剩下的數(shù)字，并可以依此類推。當(dāng)n=1時，也就是序列中開始只有一個數(shù)字0，那么很顯然最后剩下的數(shù)字就是0。我們把這種關(guān)系表示為：

//nintegers(0,1,...n-1)formacircle.Removethemth//thecircleateverytime.Findthelastnumber//Input:n-thenumberofintegersinthecircle m-removethemthnumberatevery//Output:thelastnumberremainingwhentheinputis otherwise-intLastRemaining_Solution1(unsignedintn,unsignedint{//invalidinputif(n<1||m<1)return-1;unsignedinti=0;//initiatealistwithnintegers(0,1,...n-1)list<int>integers;for(i=0;i<n;++i) torcurinteger=integers.begin();while(integers.size()>1){//findthemthinteger.Notethatstd::listisnota//soweshouldhandleitmanuallyfor(inti=1;i<m;++i){curintegerif(curinteger==integers.end())curinteger=integers.begin();}//removethemthinteger.Notethatstd::listisnota//soweshouldhandleit tornextinteger=++curinteger;if(nextinteger==integers.end())nextinteger=--curinteger;curinteger=nextinteger;}return}//nintegers(0,1,...n-1)formacircle.Removethemth//thecircleateverytime.Findthelastnumber//Input:n-thenumberofintegersinthecircle m-removethemthnumberatevery//Output:thelastnumberremainingwhentheinputis otherwise-intLastRemaining_Solution2(intn,unsignedint{//invalidinputif(n<=0||m<0)return-//ifthereareonlyoneintegerinthecircle//ofcoursethelastremainingoneis0intlastinteger=0;//findthelastremainingoneinthecirclewithnintegersfor(inti=2;i<=n;i++)lastinteger=(lastinteger+m)%return}如果對兩種思路的時間復(fù)雜度感的讀者可以把n和m的值設(shè)的稍微大一點(diǎn)，比如十萬這個數(shù)量級的數(shù)程序員面試題精選100題(15)－含有指針成員的類的拷temte<typenameT>class{{if(size>data=new}{if(data)delete[]}voidsetValue(unsignedindex,constT&{if(index<size)data[index]=value;}TgetValue(unsignedindex){if(index<size)return}T*data;面的方式并實(shí)例化該類的一個實(shí)例ArrayA(10);ArrayB(A);ArrayA(10);ArrayB(10);容。因此在執(zhí)行完前面的代碼之后，A.dataB.dataAB中任意一個結(jié)束其生datadata的時候，程序就會不可避法就是使用這兩個函數(shù)。于是我們可以把這兩個函數(shù)為私有函數(shù)，如果類的用戶企圖調(diào)用這兩個Array(constArray&constArray&operator=(constArray&datadata會把另外一個實(shí)例的data也同時刪除。因此我們還可以讓構(gòu)造拷貝函數(shù)或者拷貝運(yùn)算符的重載函數(shù)拷貝的不只是地址，而是數(shù)據(jù)。由于我們重新了一份數(shù)據(jù)，這樣一個實(shí)例刪除的時候，對另外一個實(shí)例沒有影響。這種思路我們Array(constArray©):data(0),{if(size>{data=newfor(inti=0;i<size;++i)}}constArray&operator=(constArray&{if(this==©)returnif(data!={data=NULL;}size=copy.size;if(size>0){data=newfor(inti=0;i<size;++i)}}任何指針指向該數(shù)的時候才可以刪除。這種路通常被之為計(jì)數(shù)技術(shù)在構(gòu)造函數(shù)中，計(jì)數(shù)初化為每把個實(shí)賦給其實(shí)或以參傳給他例的造貝函的候，計(jì)ta減的a到0taArray(unsigned:data(0),size(arraySize),count(newunsigned{*count=if(size>data=new}Array(constArray&:size(copy.size),data(copy.data),{++}{}constArray&operator=(constArray&{if(data==copy.data)return*this;data=copy.data;size=copy.size;count=copy.count;}void{if(*count==0){{data=NULL;}count=0;}}unsignedint程序員面試題精選100題(16)－O(lognFibonacci數(shù)題目：定義Fibonacci/01\輸入n，用最快的方法求該數(shù)列的第n//CalculatethenthitemofFibonacciSerieslonglongFibonacci_Solution1(unsignedint{intresult[2]={0,if(n<returnreturnFibonacci_Solution1(n-1)+Fibonacci_Solution1(n-}作為例子來分析遞歸求解的過程。要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和 f(7)f(6) /\ /\f(7)f(6)f(6)f(5)n的增大而急劇增加。這意味這計(jì)算量會隨著n的增大而急劇增大。事實(shí)上，用遞歸方法計(jì)算的時間復(fù)雜度是以n的指數(shù)的方式遞增的。Fibonacci100項(xiàng)試試，感受一下這樣遞歸會慢到什么程度。在我的機(jī)器上，連續(xù)運(yùn)行了更簡單的辦法是從下往上計(jì)算，首先根據(jù)f(0)和f(1)算出f(2)，在根據(jù)f(1)和f(2)算出f(3)……依此類推就可以算出第n項(xiàng)了。很容易理解，這種思路的時間復(fù)雜度是O(n)。//CalculatethenthitemofFibonacciSeries longlongFibonacci_Solution2(unsigned{intresult[2]={0,if(n<returnlonglongfibNMinusOne=longlongfibNMinusTwo=0;longlongfibN=0;for(unsignedinti=2;i<=n;++{fibN=fibNMinusOne+fibNMinusTwo=fibNMinusOne;fibNMinusOne=fibN;}return}：{f(n),f(n-1),f(n-1),f(n-2)}={1,1,1,0}n-(注：{f(n+1f(nf(nf(n-1)}表示一個矩陣。在矩陣中第一行第一列是f(n+1)，第一行第二列是f(n)，第二有了這個，要求得f(n)，我們只需要求得矩陣{1,1,1,0}的n-1次方，因?yàn)榫仃噞1,1,1,0}的n-1次方的結(jié)果的第一行第一列就是f(n)。這個數(shù)學(xué)用數(shù)學(xué)歸納法不難證明。感的朋友不妨自己證明一下現(xiàn)在的問題轉(zhuǎn)換為求矩陣{1110}0開始循環(huán)，n次方將需要n次運(yùn)算，并不比前

/ \a(n-1)/2*a(n- 要求得n次方，我們先求得n/2n/2的結(jié)果平方一下。如果把求n次方的問題看成一個大問題，次方就只需要logn次運(yùn)算了。#include//A2by2struct{longlongm00=0,longlongm01=0,longlongm10=0,longlongm11=0):m_00(m00),m_01(m01),m_10(m10),{}longlongm_00;longlongm_01;longlongm_10;longlong//Multiplytwo//Input:matrix1-thefirst matrix2-thesecond//Output:theproductionoftwoconstMatrix2By2&matrix1,constMatrix2By2&matrix2){returnmatrix1.m_00*matrix2.m_00+matrix1.m_01*matrix2.m_10,matrix1.m_00*matrix2.m_01+matrix1.m_01*matrix2.m_11,matrix1.m_10*matrix2.m_00+matrix1.m_11*matrix2.m_10,matrix1.m_10*matrix2.m_01+matrix1.m_11*}//Thenthpowerof//1//1Matrix2By2MatrixPower(unsignedint{assert(n>if(n==1){matrix=Matrix2By2(1,1,1,}elseif(n%2=={matrix=MatrixPower(n/matrix=MatrixMultiply(matrix,}elseif(n%2=={matrix=MatrixPower((n-1)/2);matrix=MatrixMultiply(matrix,matrix);matrix=MatrixMultiply(matrix,Matrix2By2(1,1,1,}return}//CalculatethenthitemofFibonacciSeriesusingdevideandlonglongFibonacci_Solution3(unsignedint{intresult[2]={0,if(n<returnMatrix2By2PowerNMinus2=MatrixPower(n-1);returnPowerNMinus2.m_00;}程序員面試題精選100題(17)－把字符串轉(zhuǎn)換成整3453。當(dāng)掃描到第二個數(shù)字'4'3了，再在后面加上一個數(shù)字的前面已經(jīng)有了34，由于后面要加上一個5，前面的34就相當(dāng)于340了，因此得到的數(shù)字就是intStrToInt(constchar*boolStrToInt(constchar*str,int&前面的第一種就很直觀。如何在保證直觀的前提下當(dāng)碰到輸入的時候通知用戶呢？一種解決方案就是定義一個全局變量，每當(dāng)碰到輸入的時候，就標(biāo)記該全局變量。用戶在調(diào)用這個函數(shù)之后，就可enumStatus{kValid=0,kInvalid};intg_nStatus=kValid;//ConvertastringintoanintStrToInt(constchar*{g_nStatus=kInvalid;longlongnum=0;if(str!={constchar*digit=//thefirstcharinthestringmaybe'+'or'-'boolminus=false;if(*digit=='+')digit++;elseif(*digit=='-{digit++;minus=true;}//theremainingcharsinthestringwhile(*digit!='\0'){if(*digit>='0'&&*digit<={num=num*10+(*digit-//{num=}}

//ifthecharisnotadigit,invalidinput{num=0;}}if(*digit=={g_nStatus=kValid;num=0-}}return}是否合法，在很多API中都用這種方法，但該方法的函數(shù)使用起來不夠直觀。最后值得一提的是，在C語言提供的庫函數(shù)中，函數(shù)atoi能夠把字符串轉(zhuǎn)換整數(shù)。它的是intatoi(constchar*str)。該函數(shù)就是用一個全局變量來標(biāo)志輸入是否合法的。程序員面試題精選100題(18)－用兩個棧實(shí)現(xiàn)隊(duì)temte<typenameT>class{CQueue()~CQueue()voidappendTail(constT&node);//appendaelementtotailvoid //removeaelementfroma，不妨把先它插入m_stack1中，此時m_stack1中的元素有{a,b,c}，m_stack2中仍然是空的。這個時候我們試著從隊(duì)列中刪除一個元素。按照隊(duì)列先入先出的規(guī)則，由于a比b、c先插入到隊(duì)列中，這次被刪除的元素應(yīng)該是a。元素a在m_stack1中，但并不在棧頂上，因此不能直接進(jìn)行刪除。注意到m_stack2我們還一直沒有使用過，現(xiàn)在是讓m_stack2起作用的時候了。如果我們把m_stack1中的元素逐個pop出來并push進(jìn)入m_stack2，元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。poppush之后，m_stack1m_stack2中的元素是{c,b,a}pop出m_stack2的棧頂a了。pop之后的m_stack1為空，而m_stack2的元素為{c,b}，其中b在棧頂。bc，bcb應(yīng)該先刪除。而此時b恰好又在棧頂上，因此可以直接pop出去。這次pop之后，m_stack1中仍然為空，而m_stack2為{c}。于m_stack2的頂端了，又可以直接pop出去。dpushm_stack1？這樣會不會有問題呢？我們說不會有問題。因?yàn)樵趧h除元素的時候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進(jìn)入由于m_stack2中元素的順序和m_stack1相反，最先進(jìn)入隊(duì)列的元素還是處于m_stack2的棧頂，仍然可appendappendappenddeletedeleteappenddelete//Appendaelementatthetailofthetemte<typenameT>voidCQueue<T>::appendTail(constT&{//pushthenewelementintom_stack1}//Deletetheheadfromthetemte<typenameT>void{//ifm_stack2isempty,andthereare//elementsinm_stack1,pushtheminm_stack2if(m_stack2.size()<=0){{}}//pushtheelementintom_stack2}程序員面試題精選100題(19)－反轉(zhuǎn)鏈struct{ a??b??…??l結(jié)點(diǎn)。現(xiàn)在我們遍歷到結(jié)點(diǎn)m。當(dāng)然，我們需要把調(diào)整結(jié)點(diǎn)的m_pNext指針讓它指向結(jié)點(diǎn)l。但注意a??b??…l??m整mm_pNext之前要把n保存下來。結(jié)點(diǎn)是尾結(jié)點(diǎn)？就是m_pNext為空指針的結(jié)點(diǎn)。//Reversealisti//Input:pHead-theheadoftheoriginal//Output:theheadofthereversed{ListNode*pReversedHead=NULL;ListNode*pNode=pHead;ListNode*pPrev=NULL;while(pNode!=NULL){//getthenextnode,andsaveitatpNextListNode*pNext=pNode->m_pNext;//ifthenextnodeisnull,thecurrectistheendof//list,andit'stheheadofthereversedlistif(pNext==NULL)pReversedHead=//reversethelinkagebetweennodespNode->m_pNext=pPrev;//moveforwardonthethelistpPrev=pNode;pNode=}return}程序員面試題精選100題(20)－最長輸出它們的長度4，并打印任意一個子串。分析：求最長公共子串（LongestCommonSubsequence,LCS）是一道非常經(jīng)典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。完整介紹動態(tài)規(guī)劃將需要很長的篇幅，因此我不打算在此全面討論動態(tài)規(guī)劃相關(guān)的概念，只集中對LCS直先介紹LCS問題的性質(zhì)：記Xm={x0,x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個字符串，而Zk={z0,z1,…zk-1}是它們的LCS，則：如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的如果xm-1≠yn-1，那么當(dāng)zk-1≠xm-1時Z是Xm-1和Y的如果xm-1≠yn-1，那么當(dāng)zk-1≠yn-1時Z是Yn-1和X的LCS；的公共子串Z’。這就與長度為k的Z是X和Y的LCS相了。因此一定有zk-1=xm-1=yn-1個長度超過k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長度超過k，這就和已知條件相了。Z不是Xm-1和Y的LCSk的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。。Xm={x0x1,…xm-1}Yn={y0,y1,…,yn-1}LCS，分別求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個LCS中較長的一個為X和Y的LCS。如果我們記字符串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求 ifi<0or ifi,j>=0and ifi,j>=0and上面的用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項(xiàng)(本面試題系列第16題）的分析中我們知為了能夠采用循環(huán)求解的思路，我們用一個矩陣（LCS_length）保存下來當(dāng)前已經(jīng)計(jì)算個各自移動到c[i,j]，因此在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中只有向左上方移動時才表明找到LCS中的一個字符。于是我們需要用另外一個矩陣（參考代碼中的LCS_direction）#include//directionsofLCSenumdecreaseDir{kInit=0,kLeft,kUp,//Getthelengthoftwostrings'LCSs,andprintoneofthe//Input: -thefirst -thesecond//Output:thelengthoftwostrings'intLCS(char*pStr1,char*{if(!pStr1||!pStr2)return0;size_tlength1=strlen(pStr1);size_tlength2=strlen(pStr2);if(!length1||!length2)size_ti,j;//initiatethelengthmatrixint**LCS_length;LCS_length=(int**)(newint[length1]);for(i=0;i<length1;++i)LCS_length[i]=(int*)newfor(i=0;i<length1;++i)for(j=0;j<length2;++j)LCS_length[i][j]=//initiatethedirectionmatrixint**LCS_direction;LCS_direction=(int**)(newint[length1]);for(i=0;i<length1;++i)LCS_direction[i]=(int*)newfor(i=0;i<length1;++i)for(j=0;j<length2;++j)LCS_direction[i][j]=for(i=0;i<length1;++{for(j=0;j<length2;++{if(i==0||j=={if(pStr1[i]=={LCS_length[i][j]=1;LCS_direction[i][j]=kLeftUp;}LCS_length[i][j]=}//acharofLCSis//itcomesfromtheleftupentryinthedirectionmatrixelseif(pStr1[i]==pStr2[j]){LCS_length[i][j]=LCS_length[i-1][j-1]+1;LCS_direction[i][j]=kLeftUp;}//itcomesfromtheupentryinthedirectionmatrixelseif(LCS_length[i-1][j]>LCS_length[i][j-1]){LCS_length[i][j]=LCS_length[i-1][j];LCS_direction[i][j]=kUp;}//itcomesfromtheleftentryinthedirectionmatrix{LCS_length[i][j]=LCS_length[i][j-1];LCS_direction[i][j]=kLeft;}}}LCS_Print(LCS_direction,pStr1,pStr2,length1-1,length2-returnLCS_length[length1-1][length2-}//PrintaLCSfortwo//Input:LCS_direction-a2dmatrixwhichrecordsthedirection LCS -thefirst -thesecond -therowindexinthematrix -thecolumnindexinthematrixvoidLCS_Print(intchar*pStr1,char*pStr2,size_trow,size_tcol){if(pStr1==NULL||pStr2==NULL)size_tlength1=strlen(pStr1);size_tlength2=if(length1==0||length2==0||!(row<length1&&col<length2))//kLeftUpimpliesacharintheLCSisfoundif(LCS_direction[row][col]==kLeftUp){if(row>0&&col>LCS_Print(LCS_direction,pStr1,pStr2,row-1,col-//printtheprintf("%c",}elseif(LCS_direction[row][col]=={//movetotheleftentryinthedirectionmatrixif(col>0)LCS_Print(LCS_direction,pStr1,pStr2,row,col-}elseif(LCS_direction[row][col]=={//movetotheupentryinthedirectionmatrixif(row>0)LCS_Print(LCS_direction,pStr1,pStr2,row-1,}}但要求是連續(xù)分布在其他字符串中。比如輸入兩個字符串BDCABA和ABCBDAB的最長公符串有BDAB，它們的長度都是2。程序員面試題精選100題(21)－左旋轉(zhuǎn)題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bcdef2位得到字符串cdefab。請實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。分，通過旋轉(zhuǎn)操作把這兩個部分交換位置。于是我們可以新開辟一塊長度為n+1的輔助空間，把原字符串接下來的一種思路可能要稍微麻煩一點(diǎn)。我們假設(shè)把字符串左旋轉(zhuǎn)m0個字符保存起第m+1個元素移動到第1個位置…重復(fù)前面處理第0個字符的步驟，直到處理完前面的m個字符。該思路還是比較容易理解，但當(dāng)字符串的長度n不是m的整數(shù)倍的時候，寫程序會有些麻煩，感的朋上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)字符串中字符的先后順序。把X翻轉(zhuǎn)后記為XT。顯然有(XT)T=X。XYXTYTXTYT分析到這里我們再回到原來的題目。我們要做的僅僅是把字符串分成兩段，第一段為前面m個字符，其余#include//Movethefirstncharsinastringtoitschar*LeftRotateString(char*pStr,unsignedint{if(pStr!={intnLength=static_cast<int>(strlen(pStr));if(nLength>0||n==0||n>nLength){char*pFirstStart=pStr;char*pFirstEnd=pStr+n-1;char*pSecondStart=pStr+n;char*pSecondEnd=pStr+nLength-//reversethefirstpartofthestringReverseString(pFirstStart,pFirstEnd);//reversethesecondpartofthestrint//reversethewholestring}}return}//ReversethestringbetweenpStartandvoidReverseString(char*pStart,char*{if(pStart==NULL||pEnd=={while(pStart<={chartemp=*pStart=*pEnd=pEnd--;}}}程序員面試題精選100題(22)－整數(shù)的二進(jìn)制表示中1的個兩個1，因此輸出2。一個很基本的想法是，我們先判斷整數(shù)的最右邊一位是不是1。接著把整數(shù)右移一位，原來處于右邊第二10為止?，F(xiàn)在的//Gethowmany1sinaninteger'sbinaryintNumberOf1_Solution1(int{intcount=0;{if(i&counti=i>>}return}2呢？答案是最好不要換成除法。因?yàn)槌ǖ男时纫莆贿\(yùn)算要低的多，個數(shù)，還將導(dǎo)致死循環(huán)。以負(fù)數(shù)0x為例，右移一位的時候，并不是簡單地把最10x0xC。這是因?yàn)橐莆磺笆莻€負(fù)數(shù)，仍然要保成0xFFFFFFFF而陷入死循環(huán)。復(fù)左移，每次都能判斷i的其中一位是不是1?；诖?，我們得到如下代碼：//Gethowmany1sinaninteger'sbinaryintNumberOf1_Solution2(int{intcount=0;unsignedintflag=1;{if(i&flag)flag=flag<<}return}1100&1011=10001，再和原整數(shù)做與運(yùn)算，會把該整數(shù)最右邊一個1變成0。那么一個整數(shù)的二進(jìn)制有多少個1，就可以進(jìn)行多少次這樣的操作。//Gethowmany1sinaninteger'sbinaryintNumberOf1_Solution3(int{intcount=while{++i=(i-1)&}return}程序員面試題精選100題(23)－跳臺階問題MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時，第一次跳f(n-1)2n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。/1\2Fibonaccin項(xiàng)，請參考本面試題系列第16題，這里就不在贅述了。程序員面試題精選100題(24)－棧push、pop序。為了簡單起見，我們假設(shè)push序列的任意兩個整數(shù)都是不相等的。比如輸入的push1、2、3、4、54、5、3、2、1poppushpoppush1，push2，push3，push4，pop，push5，pop，pop，pop，pop，這樣得到同樣需要pop的時候就把該棧的棧頂整數(shù)pop出來。pushpush4push1，2，3push數(shù)字是3，2，1。每次操作前都位于棧頂，直接pop即可。55pushpop51、2，其中pushpushpop#include//Givenapushorderofastack,determinewhetheranarrayispossible//beitscorrespondingpop//Input:pPush-anarrayofintegers,thepush -anarrayofintegers,thepop nLength-thelengthofpPushand Otherwisereturn{boolbPossible=if(pPush&&pPop&&nLength>{constint*pNextPush=pPush;constint*pNextPop=pPop;//ancillarystack//checkeveryintegersinpPopwhile(pNextPop-pPop<{//whilethetopoftheancillarystackisnotthe//tobepoped,trytopushsomeintegersintothestackwhile(stackData.empty()||stackData.top()!={//pNextPush==NULLmeansallintegershave//pushedintothestack,can'tpushany//ifthereareintegersleftinpPush,//pNextPushforward,otherwisesetittobeNULLif(pNextPush-pPush<nLength-1)pNextPush=}//Afterpushing,thetopofstackisstillnotsame//pPextPop,pPextPopisnotinapop//correspondingtopPushif(stackData.top()!=*pNextPop)//CheckthenextintegerinpPoppNextPop}//ifallintegersinpPophavebeencheck//pPopisapopsequencecorrespondingtopPushif(stackData.empty()&&pNextPop-pPop==nLength)bPossible=}return}程序員面試題選的次

100題(25從

1n的正數(shù)1出題目：輸入一個整數(shù)n1到n這n1分析：這是一道廣為流傳的面試題。用最直觀的方法求解并不是很難，但遺憾的是效率不是很高；而要得出一個效率較高的算法