2023年算法面試題總結(jié)

算法面試題總結(jié)１.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：

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

10?

/\

6

１4

/\/＼

4

81２16

轉(zhuǎn)換成雙向鏈表?4=6＝８＝1０＝１2=14=16。解：一方面我們定義的二元查找樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下:

ｔｙpedｅfsｔｒucttｒee{

intｄata；//valｕeofnｏde

ｓtructtree*ｌeft;／/ｌｅｆtchｉｌdｏfnode

structｔree*rigｈt;／/rightchｉｌdｏfnｏｄｅ?}*pｔｒee;

ptreef(ptrｅeroｏt,ｉntsigｎ)//siｇn==0返回鏈頭,sign＝=1返回鏈尾{//maｉn函數(shù)中調(diào)用ｆ(rooｔ,0);?ptreeｐ=rooｔ;?iｆ(ｐ－＞leｆt)/／假如左子樹非空 { p->left=ｆ(p->leｆt,1);／／第4個參數(shù)為，表白f函數(shù)返回roｏt左子樹中根的鏈尾??p->leｆt->ｒｉght=p;/／雙鏈表中l(wèi)eft記錄前驅(qū),ｒigｈｔ記錄后繼 } if（p->riｇht)?{??p->ｒight＝f(p->right，0）; p-＞ｒigｈt－>left=p;?}?iｆ(sign==０)whilｅ（p－>lefｔ）p=p－>ｌeft;//順著lefｔ找到雙鏈表首元素 elsewｈｉｌe（p－>right)ｐ=ｐ->rigｈt;//順著riｇｈt找到雙鏈表尾元素 retuｒnp;}2.設(shè)計包含mｉn函數(shù)的棧。?定義棧的數(shù)據(jù)結(jié)構(gòu),規(guī)定添加一個mｉn函數(shù)，可以得到棧的最小元素。

規(guī)定函數(shù)min、ｐush以及pop的時間復(fù)雜度都是O（1)。

3.求子數(shù)組的最大和

題目:輸入一個整形數(shù)組,數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組,每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。規(guī)定期間復(fù)雜度為O(n）。例如輸入的數(shù)組為1,－２,3,1０,－4，７,2，-5,和最大的子數(shù)組為3，10,-4,7,２,

因此輸出為該子數(shù)組的和１８。解：設(shè)數(shù)組元素為a[1～n],f（i)表達(dá)以a[i］為尾元素的最大子段和,則有ｆ(1)=a[1］,f(ｉ）=max{f(ｉ－1)+a[i],a[i]｝(ｉ>1)動態(tài)規(guī)劃求ｆ(ｉ),b［i]保存f（i)的值。Ｉntf(intｉ){iｎｔｊ,max；max=ｂ［1］=ａ［1］;foｒ(j＝２;ｊ<＝Ｉ;j＋+）{b[i]=a[i-1]>0?a[ｉ-1]+a[i]：a［i];if(b[i］>max）max＝b［i]；｝retｕｒｎmax;//返回b［1]~b[i］中最大值}4.在二元樹中找出和為某一值的所有途徑題目:輸入一個整數(shù)和一棵二元樹。?從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所通過的所有結(jié)點形成一條途徑。

打印出和與輸入整數(shù)相等的所有途徑。?例如輸入整數(shù)2２和如下二元樹?

10

／\

5

12

?

／

\

?4

7?則打印出兩條途徑:10，１2和10,5,7。解：一方面我們定義的二元查找樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：?

typedeｆｓｔruｃttree｛

intｄata；／/valueｏfnｏｄe

stｒuｃttｒee*left;//leftchildofnoｄｅ

stｒucｔtreｅ*ｒigｈt;//rｉghｔchildｏｆnode

}*pｔreｅ;ptreeＸ［MAX]；/／X記住途徑設(shè)樹的根為ｒoot;指定和為Ｓ，以下為回溯算法voidf(iｎtｋ,ptreeｒｏｏt,ｉntsum)//sum為已訪問結(jié)點元素之和{inｔj,sｓ=sum+rｏot->data;X［k]=rｏot;iｆ(ss==S){pｒinｔf(“\n”);for(ｊ=１；ｊ<＝k；j++)ｐｒｉntf(“％d”,X[j]->data);}else｛iｆ(rｏot->left&&ss<S)f（k+1，rｏｏt->leｆt,sｓ);if(roｏt-＞ｒighｔ＆&ss<S)f(k＋1,ｒoot－>ｒight，ｓs）；}}5.查找最小的k個元素?題目：輸入n個整數(shù),輸出其中最小的k個。

例如輸入1，2,3，4,５,6，7和8這8個數(shù)字，則最小的４個數(shù)字為1，2,３和4。解：1:可以借用找第ｋ小元素的辦法，當(dāng)找到第ｋ小元素時，這一元素和它左邊的元素構(gòu)成最小的ｋ個元素。2:可以考慮用小堆排序的辦法，每一次小堆調(diào)整得到最小的元素,進(jìn)行k次小堆調(diào)整即可得到ｋ個最小元素的有序序列。第６題

騰訊面試題:

?給你10分鐘時間，根據(jù)上排給出十個數(shù)，在其下排填出相應(yīng)的十個數(shù)

?規(guī)定下排每個數(shù)都是先前上排那十個數(shù)在下排出現(xiàn)的次數(shù)。

上排的十個數(shù)如下:

【０，１，2,３，4，5，6，7,8，9】舉一個例子，

數(shù)值:0,１,2，3,4，5,６,７，８,９

?分派:6,2,1，0,0，０，１，０,0,０

?0在下排出現(xiàn)了6次,１在下排出現(xiàn)了2次，

２在下排出現(xiàn)了1次,3在下排出現(xiàn)了0次....

以此類推..解：設(shè)X[0~9]分別為數(shù)字0～9出現(xiàn)次數(shù),即回溯算法求解向量,同時用S[0~9]記住X[0~９]中數(shù)字０～9出現(xiàn)次數(shù)。【0，1,2,3，4，5,6,７,8，９】,X[］＝{}voidf（ｉｎｔk){ｉｎtj;ｉf(ｋ＝=10)fｏｒ（ｊ＝0;j<10;j++)cｏut＜＜Ｘ[j］<<””；elｓefor(j=0;j<10;j++）{Ｘ[ｋ］=ｊ;S[j]+＋;f（k+１);Ｓ［ｊ]-－;}}voiｄmain()｛ｆ(0）;}第7題?微軟亞院之編程判斷倆個鏈表是否相交

給出倆個單向鏈表的頭指針，比如h１,h2,判斷這倆個鏈表是否相交。

為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。解：無環(huán)且能相交,形狀應(yīng)當(dāng)只能為簡樸的解決,即對兩個單鏈表都訪問到尾結(jié)點,看最后訪問的尾結(jié)點是否相同。問題擴(kuò)展:

1.假如鏈表也許有環(huán)列?

２.假如需規(guī)定出倆個鏈表相交的第一個節(jié)點列?

第８題

此貼選一些比較怪的題，，由于其中題目自身與算法關(guān)系不大,僅考考思維。特此并作一題。

1.有兩個房間，一間房里有三盞燈,另一間房有控制著三盞燈的三個開關(guān)，這兩個房間是分割開的,從一間里不能看到另一間的情況。

現(xiàn)在規(guī)定受訓(xùn)者分別進(jìn)這兩房間一次,然后判斷出這三盞燈分別是由哪個開關(guān)控制的。

有什么辦法呢?解:燈的亮滅只有2種狀態(tài)，開關(guān)也只有2種狀態(tài)，但是需要區(qū)分3盞燈,增長一個新狀態(tài)量:加熱一定期間的燈泡會發(fā)熱。這樣的話,可以區(qū)分的燈可以增長到4盞，進(jìn)開關(guān)所在屋，閉合開關(guān)1，2，約5分鐘后，關(guān)閉1，閉合開關(guān)３，進(jìn)入燈所在屋,發(fā)光又發(fā)熱被２控制，發(fā)光不發(fā)熱的被3控制，不發(fā)光而發(fā)熱的被1控制,不發(fā)光不發(fā)熱的被4控制。2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被提成七小塊，天天給出一塊。?假如你只能將金條切割兩次，你如何分給這些工人？解:7=1+2+4３.★用一種算法來顛倒一個鏈接表的順序?，F(xiàn)在在不用遞歸式的情況下做一遍。解：用單鏈表的頭插法，把從頭到尾的結(jié)點依次重新插入依次。?★用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。?★用一種算法整理一個數(shù)組。你為什么選擇這種方法??★用一種算法使通用字符串相匹配。

★顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。?★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實現(xiàn)速度最快,移動最少。詞?是“克麗絲叫我”還是“絲麗克叫我”?★找到一個子字符串。優(yōu)化速度。優(yōu)化空間。?★比較兩個字符串，用O（n)時間和恒量空間。解:intｓtrcｍp(ｃhaｒ*ｓ1,ｃhar*s２)｛whｉle(*s1&&＊s2&＆*(ｓ1+＋)==*(s2++）);ｒetuｒn*s1-＊s2;｝

★假設(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到１00０(涉及１000)之間。此外,除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次解決，用一種算法找出反復(fù)的那個數(shù)字。假如你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?解：累加求和－（1+２+…+１000）?★不用乘法或加法增長８倍?，F(xiàn)在用同樣的方法增長7倍。

第9題

判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果?題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。?假如是返回true，否則返回false。例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果:

8?

/

\?

６

10?

/\

／\

５

７9

11?因此返回true。?假如輸入7、4、6、5,沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回ｆａlsｅ。解：設(shè)數(shù)組a[froｍ~to],函數(shù)f（from,to)判斷其是否可認(rèn)為某二叉樹后序結(jié)果，intf(inｔfrom,intto){intｉ=from,j,s1，ｓ２;while(i<tｏ&&a[i]<a[ｔo］)ｉ++；/／找到第一個大于等于根ａ[to]的元素ａ[ｉ]j=i-1；／／a［froｍ~j］為左子樹部分,a［j＋1~to-1]為右子樹部分whiｌｅ(i<ｔｏ)if(a[ｉ］<a[to]）ｒｅturn０;／/右子樹中不也許尚有小于根的值if(frｏm>＝j(luò))s1=１；eｌsｅs１=f(from,ｊ);//對左子樹判斷if(j+１>＝ｔo-1)s２＝1;ｅｌses２=f(j+1,tｏ-1);//對右子樹判斷returｎs１&&s２;／/返回左右子樹判斷與結(jié)果｝第１0題?翻轉(zhuǎn)句子中單詞的順序。?題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序,但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡樸起見，標(biāo)點符號和普通字母同樣解決。?例如輸入“Iamastudｅｎt.”,則輸出“student．a(chǎn)aｍI”。解：假設(shè)句子存放在chaｒｓ[ＭＡX]中,voidｆ(）{cｈartｍｐ；Ｉnｔlｅn=strｌen(s)，I，j,ｋ;for(ｉ=0，j=ｌen-1;ｉ<j;i++,j－－)//整個句子顛倒｛tmp=s［ｉ];ｓ［i］=s[j］;s［ｊ］=tｍｐ；}／/ｓ［i]與s[j]互換ｆｏｒ（k=0;ｋ<len；ｋ++){I＝k;wｈile（s[i]==‘’)i++;／/定位單詞的頭ｊ=i;whilｅ(ｓ[j+1］!=‘’）j++;定位單詞的尾k=j+2;ｗhｉｌｅ(i＜j）／/單詞顛倒{tｍp=s[i];s[i]=s[j]；s[ｊ]=tｍp;/／s[i]與s[ｊ]互換I+＋；j--;}}}第11題

求二叉樹中節(jié)點的最大距離．..假如我們把二叉樹當(dāng)作一個圖，父子節(jié)點之間的連線當(dāng)作是雙向的，?我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。

寫一個程序,

求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。解：一方面定義的二叉樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下:

ｔypedefstｒucttrｅe{

inｔdata；/／valueｏfnｏｄeinｔlh,rh，h；//lh,rh為左、右子樹高度,h＝ｍａｘ（lh,rh）+1

stｒuctｔｒee＊ｌeft;//ｌｅftｃhiｌdofnoｄe

sｔructtreｅ*ｒｉght；//riｇhtchildｏｆnode?}*pｔree;假設(shè)樹的根為roｏt求各非葉子節(jié)點的左右子樹高度inth(ptrｅeｒoot)//返回h{iｆ(!ｒoｏｔ)retｕｒn０;root－>lｈ＝h(roｏｔ-＞left）;root->rh=h(rooｔ->rｉghｔ）;rｅｔurｎroｏｔ->ｈ＝（root->lh>rｏoｔ-＞rｈ?rｏｏt->lh+1：ｒｏｏt-＞rh＋1);}／/求最大距離，最大距離有3種也許，兩節(jié)點均在左子樹、右子樹，或一個在左,一個在右Inｔf(ptreeｒoｏｔ){inｔlen１,len2,len3;If（！roｏｔ)ｒeｔuｒｎ０;Elｓe{len１=ｆ(ｒｏot->left）;／/左子樹中最大距離值len2=f（rｏot－＞righｔ)；//右子樹中最大距離值len3=1;//一個頂點在左子樹，一個頂點在右子樹,最大距離值if(root->left)len3＋=rｏｏt->lefｔ->h;ｉf(rｏot－>ｒight)len3+=ｒoot－>riｇht－>h;ｉf（ｌen1<ｌen2)ｌen１＝lｅn2;//len1保存len1，lｅn2中較大者iｆ（len1<len3)len1=len3;retuｒnｌen1；/／返回最大值}}第12題?題目：求１+2＋…＋n,

規(guī)定不能使用乘除法、for、wｈile、if、ｅlse、switch、ｃａse等關(guān)鍵字以及條件判斷語句（A？B：C）。解:intf(iｎtn){ｉnｔs＝0；n＆&s=ｎ+f(ｎ-１);retuｒns;｝第１３題：

題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。?鏈表結(jié)點定義如下:

?strｕctＬistNode?{?

intm_nＫeｙ;

ListNodｅ*m＿pＮext；?｝;第１4題：

題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù),使得它們的和正好是輸入的那個數(shù)字。

規(guī)定期間復(fù)雜度是O(n)。假如有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。?例如輸入數(shù)組1、2、4、7、11、1５和數(shù)字1５。由于４+11=１5,因此輸出4和１1。解:假設(shè)數(shù)組為ａ[１~n],輸入和的數(shù)字為S，算法思緒fｏr（ｉ＝1,j＝n；i<j；）if（a[i]+a[j］==Ｓ){priｎtf(“%d+%ｄ=%d”，a[i],ａ[ｊ］，S);i＋＋；ｊ--；//ｂreak;}eｌseif(a[i］+a[ｊ]<S)ｉ+＋;elseif(ａ[i]+a[j]>Ｓ)j－-；第15題：

題目：輸入一顆二元查找樹,將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中,左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完畢樹的鏡像轉(zhuǎn)換。例如輸入:

８

/\?610/\/\57９11輸出:

8

/\

106/\/＼1197５解:寫遞歸函數(shù),左右子樹互換。一方面我們定義的二元查找樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：

tｙｐｅｄefstｒucttｒeｅ{

iｎtｄata；/／valｕeofｎode

ｓｔructtｒee＊ｌｅft;／/ｌeftｃｈildofnｏdｅ?

strｕctｔree＊rigｈt；//ｒightchiｌdofnode?}＊ptrｅｅ;voｉdf（ptrｅeroot){if(!ｒooｔ)return；f（rooｔ->lｅfｔ)；／/對左右子樹進(jìn)行鏡像解決ｆ(rｏot->rigｈｔ);if(root->left||root－>ｒigｈt){pｔｒeetmp＝root－>lefｔ;rooｔ->lefｔ=roｏt->right；roｏt－＞rｉgｈt＝tmp；}}第16題:

題目（微軟）:?輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點,同一層中按照從左往右的順序打印。

例如輸入

8

／\?

６10?／\/\

57911輸出8610５7９11。解:用隊列實現(xiàn)。第17題：

題目:在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abａccdeff，則輸出b。

分析：這道題是20２3年ｇooglｅ的一道筆試題。解:用數(shù)組a[２６］存放個字符出現(xiàn)次數(shù)｛初始化為０},用b［２6]存放依次出現(xiàn)字符順序,對整個字符串掃描一次,設(shè)當(dāng)前掃描字符為c，則執(zhí)行a[ｃ-‘ａ’]＋+;假如a［c-‘a(chǎn)’］=＝1,則b[k+＋]=c；其中ｋ初始值為0；掃描結(jié)束后依次檢查b[0]~ｂ[k－1],假如a［b[t]-‘a(chǎn)’]=＝1則輸出b[t]。?第18題:?題目:ｎ個數(shù)字（０,1，…,ｎ－1)形成一個圓圈，從數(shù)字0開始,?每次從這個圓圈中刪除第k個數(shù)字(第一個為當(dāng)前數(shù)字自身,第二個為當(dāng)前數(shù)字的下一個數(shù)字）。?當(dāng)一個數(shù)字刪除后,從被刪除數(shù)字的下一個繼續(xù)刪除第k個數(shù)字。

求出在這個圓圈中剩下的最后一個數(shù)字。

解：(1)簡樸算法,按循環(huán)鏈表刪除結(jié)點方式，沒刪除一個結(jié)點需付出Ｏ（m)的代價，一共刪除n-１個節(jié)點,所以復(fù)雜度為O(ｎk)，假如n，ｍ都達(dá)成10^8,則整個算法運算量將達(dá)成10^16。（2)高效算法經(jīng)典的約瑟夫環(huán)問題設(shè)n個人圍成一圈,標(biāo)號為0..n-1,從第一個人開始依次從1到ｋ循環(huán)報數(shù)，當(dāng)報到k的時候此人出圈。設(shè)J(n,k,i)表達(dá)第i個出圈的人的標(biāo)號。定理一:Ｊ（n,k，1)=(ｋ-１)MＯDn,(n＞＝1,k>=1)…………(1)證明：由定義直接得證。定理二：Ｊ(ｎ＋1,k,ｉ+1)＝（k+Ｊ(n，k,i)）MＯD(n+1)，（n>=1,ｋ＞=1,1<=i<=ｎ)…………(2)證明:設(shè)g=J（n,k，ｉ),因此假如有n個人,從0開始報號,第ｉ個出圈的標(biāo)號為g?，F(xiàn)在考慮J(ｎ+1,k,i＋１),由于J(n+１,k,1）＝(k-1)ＭOD(ｎ+1）,即第一步的時候刪除數(shù)字（k-1)MOD（ｎ+1)，第二步的時候從數(shù)字k開始數(shù)起。因而問題變?yōu)榱苏业绞Ｏ碌膎個數(shù)字中從k開始數(shù)起被刪除的第i個數(shù)字（注意這時(k-１）MOD（n+1）已經(jīng)被刪除了)，而這恰好就是(g+k)ＭＯD(ｎ+1),(２)成立。根據(jù)(2），很容易求得n個數(shù)里面第i個出圈的數(shù)。就根據(jù)這個定理遞推計算。即求Ｊ(n,k,n)即可。根據(jù)遞推關(guān)系式,n呈單步遞減變化,每一步變化僅常量個運算，所以算法復(fù)雜度為O(n）。?第19題：?題目：定義Fibonacci數(shù)列如下:

/0n=0

f(ｎ)=1ｎ＝1?

\ｆ(n－1）+f(ｎ－2)n＝2輸入n，用最快的方法求該數(shù)列的第ｎ項。

分析：在很多C語言教科書中講到遞歸函數(shù)的時候,都會用Ｆibonacci作為例子。

因此很多程序員對這道題的遞歸解法非常熟悉,但．..．呵呵,你知道的。。解：根據(jù)遞推關(guān)系式,采用動態(tài)規(guī)劃算法。第20題:

題目:輸入一個表達(dá)整數(shù)的字符串,把該字符串轉(zhuǎn)換成整數(shù)并輸出。

例如輸入字符串＂345",則輸出整數(shù)３４5。解：略。第２１題

2023年中興面試題

編程求解:

輸入兩個整數(shù)ｎ和m，從數(shù)列１,2，３......．ｎ中隨意取幾個數(shù),使其和等于ｍ，規(guī)定將其中所有的也許組合列出來．解：回溯算法(子集和數(shù)問題)。InｔX[MAX］；vｏidf（intｋ，intｓｕm)/／sum=X[1]+X[2]+…+X［k-1］{inti;if(suｍ==m){ｐｒinｔf(“\n”);for(i=1;i<k;i++）priｎtf(“%d”,Ｘ［i]);}elsefoｒ(ｉ=Ｘ［k-1]＋1;i<n;i++)iｆ(sum+i<=ｍ)//剪枝作用{X[k］=ｉ;f（k+１,suｍ+i);}}ｖoiｄmaｉn(）｛ｆ(１,０);｝第22題:?有4張紅色的牌和4張藍(lán)色的牌,主持人先拿任意兩張,再分別在Ａ、B、Ｃ三人額頭上貼任意兩張牌，

Ａ、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，

A說不知道,B說不知道，C說不知道,然后A說知道了。?請教如何推理，A是怎么知道的。?假如用程序,又怎么實現(xiàn)呢?

?第23題:

用最簡樸,最快速的方法計算出下面這個圓形是否和正方形相交。"

3Ｄ坐標(biāo)系原點（0.0,0.0,0.0)?圓形：

半徑r=３．０?圓心o=(*.*,0．０,*.*)正方形:

4個角坐標(biāo)；

?1:(*.*,0．0,*．*)

２：(*．＊，0.0，＊.*)?3:(＊.＊，0．0,*.*)

４:(*.*,０.０，*.*)解:一方面計算出正方形四條邊的直線方程,并依據(jù)點到直線距離公式，計算出圓心到四條邊的距離(設(shè)為d１，d２,ｄ3,ｄ4）,且只要ｄ1~ｄ４有一個小于r,則相交，否則不相交。第２4題:

鏈表操作,

(1).單鏈表就地逆置,

(２)合并鏈表

第25題:

寫一個函數(shù),它的原形是ｉｎｔｃontinumax(char＊ｏｕtputstｒ，cｈaｒ*inｔpｕtstr)

功能：

在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回,

并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)oｕｔpｕtsｔｒ所指內(nèi)存。?例如:＂abcd１23４5ed125ss"的首地址傳給intpｕｔstｒ后,函數(shù)將返回9，

outｐutstr所指的值為

26.左旋轉(zhuǎn)字符串題目:?定義字符串的左旋轉(zhuǎn)操作:把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bｃdeｆ左旋轉(zhuǎn)2位得到字符串cdｅｆａb。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。

規(guī)定期間對長度為ｎ的字符串操作的復(fù)雜度為O(n),輔助內(nèi)存為O（1）。

27．跳臺階問題?題目:一個臺階總共有n級，假如一次可以跳１級,也可以跳２級。?求總共有多少總跳法,并分析算法的時間復(fù)雜度。這道題最近經(jīng)常出現(xiàn)，涉及MicroＳtrategy等比較重視算法的公司

都曾先后選用過個這道題作為面試題或者筆試題。解:f(n)表一共有多少種跳法f(１）=1;f(２）=2;f(ｎ）=f(n－1）+f(n－2)，n>2，然后如斐波那契數(shù)列同樣,動態(tài)規(guī)劃算法。2８.整數(shù)的二進(jìn)制表達(dá)中１的個數(shù)

題目：輸入一個整數(shù),求該整數(shù)的二進(jìn)制表達(dá)中有多少個1。?例如輸入10，由于其二進(jìn)制表達(dá)為1010，有兩個１,因此輸出2。分析:?這是一道很基本的考察位運算的面試題。?涉及微軟在內(nèi)的很多公司都曾采用過這道題。29.棧的pｕsh、ｐｏｐ序列?題目:輸入兩個整數(shù)序列。其中一個序列表達(dá)棧的push順序，?判斷另一個序列有沒有也許是相應(yīng)的pop順序。?為了簡樸起見，我們假設(shè)pusｈ序列的任意兩個整數(shù)都是不相等的。

比如輸入的pｕｓh序列是1、2、3、4、5,那么４、5、3、２、1就有也許是一個pop系列。?由于可以有如下的pusｈ和pｏp序列：?push1,push2，pｕsｈ３,pｕsh4,poｐ,puｓｈ５,pop,poｐ,pｏp,pop,?這樣得到的poｐ序列就是4、５、3、2、１。?但序列4、3、５、1、2就不也許是pｕsh序列1、2、３、4、５的pop序列。解：為簡樸起見，設(shè)push序列為遞增的,要判斷a[1~n］系列是否為也許的pｏp序列，對于任意a[ｉ]只需檢查a[i]右側(cè)比ａ[i］小的數(shù)字是否構(gòu)成遞減序列。例如上面4、3、５、１、2，其中４右側(cè)比它小的數(shù)分別為3、1、2，不是遞減序列，所以它為不也許的pop序列。intf(){Inti,ｊ,X[MAX],ｋ；ｆoｒ(i=1;ｉ＜=n;ｉ+＋){k=0;ｊ=i+1;X[0]=a[i];while(j＜=n)if(a[ｊ]<a［i]）｛if(a[j]＞X[ｋ］)ｒeｔuｒn0；/／不構(gòu)成遞減序列X［++k]=ａ[j];}｝rｅturｎ1;//上面沒有碰到非遞減情況，則是也許的pｏp序列，時間復(fù)雜度O（ｎ2)｝30．在從1到ｎ的正數(shù)中1出現(xiàn)的次數(shù)?題目:輸入一個整數(shù)n，求從1到ｎ這n個整數(shù)的十進(jìn)制表達(dá)中1出現(xiàn)的次數(shù)。例如輸入12,從１到12這些整數(shù)中包含1的數(shù)字有1，10，1１和12，1一共出現(xiàn)了5次。

分析:這是一道廣為流傳的google面試題。解：先對N各個數(shù)位進(jìn)行運算分析，設(shè)N＝ａn*１0ｎ+an－1*10ｎ-1+…＋a1*１01＋ａ０,即其個位數(shù)為ａ0，十位數(shù)為a１，…,用ｆ(N)表達(dá)1到N的所有整數(shù)中1出現(xiàn)次數(shù),則有：f(N)=0Ｎ＝0ａn*n*1０ｎ－１+（an>1?10n：(N-10n+1))+f(N%１0ｎ）N>０例如當(dāng)N介于１～9時f（N)＝1，可由上面遞推式驗證。此外驗證下面兩個:ｆ（14)＝1*1＊1＋(１4-10+1)+f(14%10）=6＋f(4）=7f(114)=1＊2*1０＋(1１4-１00+１)+f(11４%10０)=35+f(１4)＝４2（分析此外展開）31.華為面試題：

一類似于蜂窩的結(jié)構(gòu)的圖,進(jìn)行搜索最短途徑（規(guī)定5分鐘)３2.?有兩個序列a,b,大小都為n,序列元素的值任意整數(shù),無序;

規(guī)定：通過互換a,b中的元素，使[序列a元素的和］與[序列b元素的和]之間的差最小。

例如:

vａｒa=[100,９９，98，1,2,3］;?vａrｂ=[1,2,3,４,5,40];解：回溯算法，與禮物分派算法接近。３3.?實現(xiàn)一個挺高級的字符匹配算法：

給一串很長字符串，規(guī)定找到符合規(guī)定的字符串,例如目的串：123

1**＊*＊*3***2,１２*＊***3這些都要找出來?其實就是類似一些和諧系統(tǒng)。。。。。34.?實現(xiàn)一個隊列。?隊列的應(yīng)用場景為:

一個生產(chǎn)者線程將iｎｔ類型的數(shù)入列，一個消費者線程將iｎt類型的數(shù)出列35.

求一個矩陣中最大的二維矩陣(元素和最大).如：?１２03４

２3451

１1530

中最大的是:?４5

53?規(guī)定:(1)寫出算法;(2)分析時間復(fù)雜度;(3)用Ｃ寫出關(guān)鍵代碼解：假設(shè)矩陣為a[m][n］，用f(I,ｊ)表達(dá)以ａ[ｉ］[j］為矩形右下角元素的最大子矩陣和，則求出所有f（Ｉ,ｊ)后擬定其中最大者即可。f(I,j)的計算方式為Inｔｆ(inｔＩ，ｉnｔｊ）｛Inti1,j1,tmp[MAＸ]={0},maｘ=-poｗ（2,31);for（ｉ１=Ｉ;ｉ1>=０;i1--){sum=0；ｆor(j1=j;j１>=0;ｊ1-－）tmp［j1]+＝ａ[i1]［j1];//第一次執(zhí)行時，僅將矩陣i行值賦值到tmp[］for(j1=j；ｊ１>=0;ｊ1--){ｓum+=tｍｐ[j1]；Ｉｆ(sum＞max）mａx=sｕm;｝}Returnｍaｘ;／/max即為以a[ｉ][j]為矩形右下角元素的最大值}第36題-４０題(有些題目搜集于CSDＮ上的網(wǎng)友,已標(biāo)明）：

36．引用自網(wǎng)友:lｏngｚuo

谷歌筆試:?n支隊伍比賽，分別編號為0,１，２。。。。ｎ－1,已知它們之間的實力對比關(guān)系,?存儲在一個二維數(shù)組ｗ［n][n]中,w[i］[j]的值代表編號為i,ｊ的隊伍中更強(qiáng)的一支。所以w[i][j]=i或者j,現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中,?比如ｏｒder[n]=｛4，3，５,8,1...．．.｝,那么第一輪比賽就是4對3，５對8。....．.．?勝者晉級,敗者淘汰,同一輪淘汰的所有隊伍排名不再細(xì)分，即可以隨便排，

下一輪由上一輪的勝者按照順序，再依次兩兩比,比如也許是4對5,直至出現(xiàn)第一名編程實現(xiàn)，給出二維數(shù)組w，一維數(shù)組orｄer和用于輸出比賽名次的數(shù)組reｓuｌt[n]，?求出resｕlt。解：按題意應(yīng)當(dāng)滿足n=２k，初始化result[]為0，resuｌt[i]相應(yīng)編號為ordeｒ[i]的隊伍最終獲得名次。則算法可以如下運營(每一輪比賽兩兩進(jìn)行,輸者名次為t),ｔ=ｎ;playeｒ1＝1;plａyeｒ2=２;ｆor（i=ｎ/2;i>0；i＝i/2){j=0;pｌayｅr1＝１;while(j<i）／/找i對隊伍進(jìn)行比賽并擬定名次{ｗhile（resulｔ[plaｙer１］)ｐlayeｒ１++;playｅr2=playｅｒ1＋1；wｈｉle(resｕｌt［ｐlayer2]）ｐlayer2＋＋；if（w[ｏrdeｒ［ｐlayer1]][ordeｒ[ｐlayｅｒ2]]＝=oｒder[pｌayer１］)rｅsult[player2]=t--；eｌｓeresult[plａyer1]=t-－;pｌａｙｅr1=plａｙer2+１;j＋+;}}比如ｏrder[n］＝{4,3,5,８,1.．....}，最后計算的rｅsult［n]={3，6,2,1,8，…},則說明編號４的隊伍最終名次為第３名,編號為3的隊伍名次為第6名,…３７.

有n個長為m+１的字符串,

假如某個字符串的最后m個字符與某個字符串的前m個字符匹配,則兩個字符串可以聯(lián)接,

問這ｎ個字符串最多可以連成一個多長的字符串,假如出現(xiàn)循環(huán)，則返回錯誤。38.

百度面試：?1.用天平（只能比較,不能稱重)從一堆小球中找出其中唯一一個較輕的，使用x次天平，?最多可以從y個小球中找出較輕的那個，求y與x的關(guān)系式。2.有一個很大很大的輸入流,大到?jīng)]有存儲器可以將其存儲下來，?并且只輸入一次,如何從這個輸入流中隨機(jī)取得ｍ個記錄。3.大量的URL字符串,如何從中去除反復(fù)的，優(yōu)化時間空間復(fù)雜度39．

網(wǎng)易有道筆試:

（1).

求一個二叉樹中任意兩個節(jié)點間的最大距離,

兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數(shù)，?比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是２,優(yōu)化時間空間復(fù)雜度。(２)．

求一個有向連通圖的割點,割點的定義是,假如除去此節(jié)點和與其相關(guān)的邊,?有向圖不再連通，描述算法。40.百度研發(fā)筆試題?引用自:zp

１）設(shè)計一個棧結(jié)構(gòu)，滿足一下條件：ｍiｎ，push，pop操作的時間復(fù)雜度為O(１)。2)一串首尾相連的珠子(m個)，有N種顏色(N<=1０),

設(shè)計一個算法,取出其中一段，規(guī)定包含所有N中顏色,并使長度最短。?并分析時間復(fù)雜度與空間復(fù)雜度。3)設(shè)計一個系統(tǒng)解決詞語搭配問題，比如說中國和人民可以搭配,?則中國人民人民中國都有效。規(guī)定:

＊系統(tǒng)每秒的查詢數(shù)量也許上千次；?

*詞語的數(shù)量級為1０W;?

*每個詞至多可以與１Ｗ個詞搭配當(dāng)用戶輸入中國人民的時候,規(guī)定返回與這個搭配詞組相關(guān)的信息。4１.求固晶機(jī)的晶元查找程序

晶元盤由數(shù)目不詳?shù)拇笮⊥瑯拥木гM成，晶元并不一定全充滿晶元盤，照相機(jī)每次這能匹配一個晶元，如匹配過,則拾取該晶元,

若匹配但是,照相機(jī)則按測好的晶元間距移到下一個位置。

求遍歷晶元盤的算法求思緒。42．請修改append函數(shù)，運用這個函數(shù)實現(xiàn)：兩個非降序鏈表的并集,1->2-＞３和２->3->5并為1－>2－＞3－>5?此外只能輸出結(jié)果,不能修改兩個鏈表的數(shù)據(jù)。４3.遞歸和非遞歸倆種方法實現(xiàn)二叉樹的前序遍歷。44.騰訊面試題：

１.設(shè)計一個魔方（六面)的程序。?2．有一千萬條短信,有反復(fù)，以文本文獻(xiàn)的形式保存,一行一條，有反復(fù)。

請用5分鐘時間,找出反復(fù)出現(xiàn)最多的前１0條。3.收藏了1萬條ｕrｌ,現(xiàn)在給你一條uｒl，如何找出相似的ｕrｌ。（面試官不解釋何為相似）45.雅虎:

1.對于一個整數(shù)矩陣，存在一種運算，對矩陣中任意元素加一時,需要其相鄰（上下左右）某一個元素也加一,現(xiàn)給出一正數(shù)矩陣,判斷其是否可以由一個全零矩陣通過上述運算得到。２.一個整數(shù)數(shù)組，長度為n，將其分為m份,使各份的和相等,求ｍ的最大值?

比如{3，2,4,3,6}可以提成{３，2,4，3，6}ｍ=1;

?

{3,6｝{２,4,3｝ｍ=2?

{3,３｝｛2，4｝{6}m＝3所以m的最大值為3解:設(shè)數(shù)組為a[0~ｎ-1]思緒:(1)先求和sum=，對sum約數(shù)分解,假設(shè)遞減排列為k1，k2,…kt，（２）對集合a[]內(nèi)元素分為ｋi(1≤i≤t）個子集，假如能使得所有子集元素之和相等，則ｋi即為所求。【將集合分為ki個子集,所有也許的分解方法,可查回溯算法解決】46.搜狐：?四對括號可以有多少種匹配排列方式?比如兩對括號可以有兩種:（）（)和（(）)解:F(0)=F(1)=1;F(n)=所以Ｆ(２)=F（0)Ｆ（1)+F(1)F(0)=２F（３)=F(0）F(2)+F(1)F(１)＋Ｆ(2）F(0）=５F(4)=Ｆ(0)F(３)+F(1）F(2）+Ｆ(2)Ｆ(１）+F(３)F(0)=1447.創(chuàng)新工場：?求一個數(shù)組的最長遞減子序列比如{9，4，3,2,５，4，3,2}的最長遞減子序列為{9，5,4，3，２}解:設(shè)數(shù)組為a[1～n],Ｆ(n）為以ａ[n]為結(jié)尾元素所構(gòu)成的最長遞減子序列長度,則有Ｆ(1)＝1；F(n）=max{F(ｉ)}+１i<n且滿足ａ［i]>＝a[n]然后動態(tài)規(guī)劃計算。48.微軟:

一個數(shù)組是由一個遞減數(shù)列左移若干位形成的，比如{4，３，2,1,6，5}?是由{6，5,4,3，２，1}左移兩位形成的，在這種數(shù)組中查找某一個數(shù)。解：類似于二分查找，設(shè)數(shù)組a[1~n］Ｉntfind（inｔｆrom,intto，intkey){iｎｔｍid＝(froｍ＋ｔo)/2；Iｆ(from>tｏ)return-1;／/查找失?。蒮（key==ａ[ｆｒom])retuｒnfrom;If(key>ａ［fｒoｍ]）{if(ｋey＜a[mid]｜｜(keｙ>a[mｉd]＆&a[ｆroｍ]>=a[mｉd]))reｔuｒｎｆinｄ(ｍiｄ＋1,ｔo,kｅｙ)；ｅlsereturｎfinｄ(fｒoｍ+1,mid-1，kｅy);｝ｅlｓe{if(ｋｅｙ<a[miｄ]||（ｋey>a[miｄ］&&ａ[ｆｒｏm]>=a[ｍid]))rｅtｕrｎｆind(frｏｍ+1，mid,keｙ);ｅlsereturnfind(mid+１，to,ｋｅy)；｝}49.一道看上去很嚇人的算法面試題:?如何對n個數(shù)進(jìn)行排序，規(guī)定期間復(fù)雜度O(n),空間復(fù)雜度O(1)50.網(wǎng)易有道筆試：?1．求一個二叉樹中任意兩個節(jié)點間的最大距離,兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數(shù),

比如某個孩子節(jié)點和父節(jié)點間的距離是1,和相鄰兄弟節(jié)點間的距離是２,優(yōu)化時間空間復(fù)雜度。解：同上面１1題。2.求一個有向連通圖的割點，割點的定義是，

假如除去此節(jié)點和與其相關(guān)的邊,有向圖不再連通,描述算法。?解：判斷一個有向連通圖是否連通，可以直接采用ＤFS算法,看是否能遍歷到所有頂點。所以此問題算法思緒就容易解決,對圖的每一個頂點做刪除嘗試(同時刪除其關(guān)聯(lián)的邊）,然后從任意頂點出發(fā)做DFS算法遍歷，假如不能遍歷到所有頂點(被刪頂點除外），則被刪頂點為割點,否則不是割點。?51.和為n連續(xù)正數(shù)序列。?題目:輸入一個正數(shù)n,輸出所有和為n連續(xù)正數(shù)序列。例如輸入1５，由于１+2+3＋４+5=４＋５＋6=7+8=１５,所以輸出３個連續(xù)序列1-５、4－6和７-８。?分析:這是網(wǎng)易的一道面試題。解：這是一個一元二次方程的求解問題。設(shè)ｎ分解為a+1,a+2，…,a＋k（a＞=０)，則有n=ka+ｋ(ｋ+1)/2=>2n=k（２a＋k＋１)=＞對2n進(jìn)行因式分解窮舉，設(shè)2n=i*j(i<j)，則讓k＝ｉ，a=（j-i－1)／2,假如a為整數(shù),則找到一個符合規(guī)定的解。?52.二元樹的深度。題目:輸入一棵二元樹的根結(jié)點，求該樹的深度。從根結(jié)點到葉結(jié)點依次通過的結(jié)點(含根、葉結(jié)點）形成樹的一條途徑,最長途徑的長度為樹的深度。例如:輸入二元樹：?

10

/

\?

６

１4

/

/

\

4

1２

１6輸出該樹的深度3。二元樹的結(jié)點定義如下：strｕctSＢinaｒyTreeNode//ａnodeofthｅbinarytrｅe?{?

int

m_nＶaluｅ;//vａlueofｎｏde?

SBiｎaryTreｅＮｏde

*ｍ＿ｐLｅfｔ；

//lefｔchiｌdoｆnoｄe

ＳBｉｎaryTreeNｏde

＊m_ｐRｉｇht；//riｇhtchildｏfnodｅ?｝；

分析：這道題本質(zhì)上還是考察二元樹的遍歷。解:略。５３．字符串的排列。?題目:輸入一個字符串，打印出該字符串中字符的所有排列。

例如輸入字符串ａbc,則輸出由字符a、b、ｃ所能排列出來的所有字符串?aｂc、ａcb、bａc、bca、cab和cｂa。分析:這是一道很好的考核對遞歸理解的編程題,

因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。解：回溯算法,與1~n的全排列幾乎同樣。但是有個細(xì)節(jié)問題，字符串中是否有反復(fù)字符呢？例如”ａｂbaａ”，則其排列結(jié)果有5!／3！/2!=10種?！咀ⅲ号cm點問題中操作數(shù)的排列反復(fù)是同樣的?！?4.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。題目:輸入一個整數(shù)數(shù)組,調(diào)整數(shù)組中數(shù)字的順序,使得所有奇數(shù)位于數(shù)組的前半部分，?所有偶數(shù)位于數(shù)組的后半部分。規(guī)定期間復(fù)雜度為Ｏ(n)。解:這個應(yīng)當(dāng)可以聯(lián)想到快速排序的一趟解決過程,其一趟的效果是使得一部分小于ａ[from］的元素都被搬到左邊,而大于a[from]的元素被搬到右邊。所以這個問題的解決就很簡樸了。簡要思緒:設(shè)數(shù)組為ａ[frｏm~ｔo]，置i=ｆroｍ，j=to，ｉ從左往右找偶數(shù)，j從右往左找奇數(shù)，只要i,ｊ沒有相遇，則將兩數(shù)互換,直到i,ｊ相遇為止。55.?題目：類CMyStrinｇ的聲明如下：

ｃlasｓＣMyStrinｇ

{

pubｌic:?

CＭyString(chaｒ*pＤａt(yī)ａ=NULＬ);?

ＣＭySｔｒing(cｏnsｔCMyString&str）;

～CMyStｒing(voｉｄ）；

CMyStriｎｇ&ｏpeｒａｔoｒ＝（consｔCMｙStｒinｇ&ｓtｒ)；pｒivate：?

char*m_pＤata;?｝;?請實現(xiàn)其賦值運算符的重載函數(shù),規(guī)定異常安全,即當(dāng)對一個對象進(jìn)行賦值時發(fā)生異常，對象的狀態(tài)不能改變。56.最長公共字串。題目：假如字符串一的所有字符按其在字符串中的順序出現(xiàn)在此外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不規(guī)定子串（字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。

請編寫一個函數(shù),輸入兩個字符串,求它們的最長公共子串,并打印出最長公共子串。例如:輸入兩個字符串BDCＡBA和AＢCBDAB，字符串BＣＢA和BDAB都是是它們的最長公共子串，?則輸出它們的長度4，并打印任意一個子串。分析:求最長公共子串（LongestComｍonSｕbsequence,LCＳ)是一道非常經(jīng)典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MｉｃroStｒategy都把它當(dāng)作面試題。解:動態(tài)規(guī)劃算法例子，關(guān)于這個問題的資料到處都是(從略)。57.用倆個棧實現(xiàn)隊列。題目：某隊列的聲明如下:temｐｌate<tｙpenameT＞clａsｓＣQuｅuｅ?{

ｐｕｂｌｉc:?

ＣQueue(){}

~CQueue(）{}

voidａｐpenｄTail(constT&node);

//appendaelemｅnttotａiｌ

voｉddeleteＨeａd();

/／rｅmovｅaelemeｎtfｒoｍｈｅadpｒivate:

T>m_stａck1;

T>m_staｃk2;?};分析:從上面的類的聲明中,我們發(fā)現(xiàn)在隊列中有兩個棧。

因此這道題實質(zhì)上是規(guī)定我們用兩個棧來實現(xiàn)一個隊列。

相信大家對棧和隊列的基本性質(zhì)都非常了解了:棧是一種后入先出的數(shù)據(jù)容器,

因此對隊列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行;隊列是一種先入先出的數(shù)據(jù)容器,

我們總是把新元素插入到隊列的尾部,而從隊列的頭部刪除元素。58.從尾到頭輸出鏈表。題目：輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：

strｕctLｉstＮode?{

iｎt

m_nKey;

ListNoｄe＊ｍ_pＮext；

};?分析：這是一道很故意思的面試題。?該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。解:設(shè)頭結(jié)點為head；ｖoｉdf（LｉsｔNｏde＊ｈ)／/遞歸函數(shù)，是一個“天生”的棧{ｉｆ(ｈ){If（h->ｎext)f(h－>ｎeｘt)；/／先解決鏈表后面部分Cout＜＜h->ｍ_nKey<＜””；}}59.不能被繼承的類。題目:用Ｃ++設(shè)計一個不能被繼承的類。分析:這是Ａdｏbe公司20２3年校園招聘的最新筆試題。

這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反映能力,是一道很好的題目。

60.在O（1)時間內(nèi)刪除鏈表結(jié)點。題目：給定鏈表的頭指針和一個結(jié)點指針,在O(1)時間刪除該結(jié)點。鏈表結(jié)點的定義如下：sｔrucｔListNｏdｅ｛

int

m_nKey;

LisｔNodｅ*nｅxt;};函數(shù)的聲明如下:

ｖoｉｄDelｅteＮoｄe（ListNｏde*pＬiｓtＨｅad,LｉstNｏde*pTｏBeDeleted）;分析:這是一道廣為流傳的Gｏogle面試題，能有效考察我們的編程基本功,還能考察我們的反映速度,更重要的是，還能考察我們對時間復(fù)雜度的理解。解:鏈表不能隨機(jī)訪問,要刪除pＴoＢeDｅlｅted結(jié)點,按常規(guī)解決是先找到其前驅(qū)（設(shè)為p）,然后做刪除操作,但是對于單向鏈表而言,找到p結(jié)點顯然不是O(１）能完畢的，除非是雙向鏈表，則可直接從pTｏBｅDeleｔed結(jié)點獲取到其前驅(qū)p，然后執(zhí)行p-＞nｅｘt=pToBeDeleted->next;ｆrｅe(pＴoBeＤｅletｅｄ）;但是這題設(shè)計的巧妙之處就是，鏈表中節(jié)點的內(nèi)存格式是同樣的，所以可以把pＴoＢeDeletｅd的后繼結(jié)點數(shù)據(jù)復(fù)制到ｐToBeDelｅｔｅd中來，然后刪除pＴｏBeDeleted的后繼。61.找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字?題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。?請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。規(guī)定期間復(fù)雜度是Ｏ（n)，空間復(fù)雜度是O（1）。分析:這是一道很新奇的關(guān)于位運算的面試題。６2．找出鏈表的第一個公共結(jié)點。?題目：兩個單向鏈表，找出它們的第一個公共結(jié)點。鏈表的結(jié)點定義為:?structＬiｓtＮｏｄｅ{

iｎt

ｍ_ｎＫey;

LiｓtNode*

m_pNexｔ；};分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，

因此在微軟的面試題中,鏈表出現(xiàn)的概率相稱高。6３.在字符串中刪除特定的字符。

題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如,輸入”Tｈeyarｅstｕｄentｓ.”和”ａeiｏu”,則刪除之后的第一個字符串變成”Ｔhｙｒｓtdｎｔｓ.”。分析:這是一道微軟面試題。在微軟的常見面試題中,與字符串相關(guān)的題目占了很大的一部分，?由于寫程序操作字符串能很好的反映我們的編程基本功。解:字符個數(shù)不多,所以建立一個存儲信息m[２６］（假設(shè)不區(qū)分大小寫),假如字符’a’+ｉ出現(xiàn)在字符串二中,則m［i]＝１，否則m[ｉ]=0;設(shè)字符串一為ｃhar＊s1;則刪除算法可表達(dá)如下:len=ｓtｒlｅｎ(s１);ｃount＝0；//counｔ記住已經(jīng)被刪除字符個數(shù)foｒ(i=0;i<len；i+＋)if(m[s１[i]－‘a(chǎn)’］)／/假如字符ｓ1[i］在字符串二中出現(xiàn){j＝i＋1;couｎt++;wｈilｅ（!m[s1[ｊ］-‘a(chǎn)’])s1［j-couｎt]=s1[j++];//把s1[ｊ]往前搬coｕnｔ個單元i=j;}【時間復(fù)雜度為O(n)?！?4.尋找丑數(shù)。?題目:我們把只包含因子2、3和5的數(shù)稱作丑數(shù)(UｇlｙＮumber)。例如6、8都是丑數(shù)，?但14不是，由于它包含因子7。習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。

求按從小到大的順序的第1500個丑數(shù)。分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題,據(jù)說gｏogｌe曾經(jīng)采用過這道題。解：判斷一個數(shù)是否是丑數(shù)，最多進(jìn)行3次求余運算,由于絕大多數(shù)的整數(shù)都是2或3或5的倍數(shù)，所以要找到第1５0０個丑數(shù)，直接從１開始往后窮舉判斷即可?！颈热?~１000中是2或3或5的倍數(shù)個數(shù)有1０00*(1／2＋1／３+1/５－1/２*3-1/2*5-1／3*5＋1/2*3＊5）=733個。所以第1５00個丑數(shù)大約在15０0＊(1000/７3３）=2046處,運算量是可以承受的?！?/p>

65.輸出１到最大的N位數(shù)

題目:輸入數(shù)字n,按順序輸出從１最大的ｎ位10進(jìn)制數(shù)。比如輸入3，則輸出１、2、3一直到最大的3位數(shù)即999。

分析:這是一道很故意思的題目?？雌饋砗芎啒?其實里面卻有不少的玄機(jī)。66.顛倒棧。

題目：用遞歸顛倒一個棧。例如輸入棧{1,2，3，4,５}，1在棧頂。

顛倒之后的棧為{5,4,３,2,1}，５處在棧頂。67.倆個閑玩娛樂。１．撲克牌的順子?從撲克牌中隨機(jī)抽5張牌,判斷是不是一個順子，即這5張牌是不是連續(xù)的。

２-10為數(shù)字自身，A為1,J為１1,Ｑ為12，K為１３，而大小王可以當(dāng)作任意數(shù)字。２.n個骰子的點數(shù)。

把n個骰子扔在地上,所有骰子朝上一面的點數(shù)之和為S。輸入ｎ，

打印出S的所有也許的值出現(xiàn)的概率。解:骰子的６個面分別點數(shù)１~6,每一個面朝上的概率1/6,n個朝上的面其點數(shù)之和S滿足n≤Ｓ≤6n，假設(shè)n個骰子投出Ｓ點的概率為f(n，S),則ｆ(n－1，S-1)，f(n－１,S-2),f（n-1,S-3)，ｆ(n-１,Ｓ-4），f(n-1,S－５),ｆ(n－1，S-６)分別表達(dá)n－1個骰子投出S-1,Ｓ-2,…,Ｓ-6點的概率,可分析出遞推關(guān)系式f（n,Ｓ)=0Ｓ<n||S>6n1/6n=1且1＜=Ｓ＜=6(ｆ(n-１,Ｓ－１）+ｆ（ｎ-1,S-２)+f（n－1,Ｓ-3)＋f(n－1，S-４)+f(n-1,S-5)＋f(n－1,S－6）)／６ｎ>１然后可動態(tài)規(guī)劃算法計算f(ｎ，Ｓ);【注:可驗證ｆ(２，5),即2個骰子投出5點的概率,顯然,樣本空間為６*６＝36種,其中點數(shù)之和為5的有，１4,23,３２和４1四種，即理論概率應(yīng)當(dāng)是4/３6。根據(jù)遞推關(guān)系式計算有f（2,5)=(f(1,４)＋ｆ(1,3）＋f（1,2)+ｆ(1,1）+f(1,0）+ｆ(1,-1))/6=４／36】68．把數(shù)組排成最小的數(shù)。

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

3２１}，則輸出這兩個能排成的最小數(shù)字３２１32。

請給出解決問題的算法，并證明該算法。分析：這是2０２36月份百度的一道面試題，?從這道題我們可以看出百度相應(yīng)聘者在算法方面有很高的規(guī)定。解:對數(shù)組內(nèi)所有數(shù)按字符串字典序遞增排序，依據(jù)排序后順序?qū)⑵溥B接成一個數(shù)即為所求。但是這個字典序，有特殊情況的解決,即當(dāng)其中一個串（設(shè)為s1）是此外一個串（設(shè)為ｓ2,其長度為n)的前綴部分時,如何擬定其排序，是解決這個問題的關(guān)鍵。69.旋轉(zhuǎn)數(shù)組中的最小元素。?題目:把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{３,4,５,１,2}為｛1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。

分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素,?時間復(fù)雜度顯然是O(N)。但這個思緒沒有運用輸入數(shù)組的特性，我們應(yīng)當(dāng)能找到更好的解法。解：設(shè)數(shù)組為ａ［１~n]，且是遞增數(shù)組的旋轉(zhuǎn)結(jié)果，類似于二分查找算法Ｉntｆｉnd_mｉn（intfrｏm,inｔto）｛inｔmｉd=（from+to)/2;If(a[ｆrｏm］＜＝a[tｏ］）ｒeturna[from];If(a[from］<a[mid]）reｔurｎfｉnd＿min(mid+1,to)；ｅｌseretｕrnfinｄ_min(frｏm,mid);}70.給出一個函數(shù)來輸出一個字符串的所有排列。

AＮSWEＲ簡樸的回溯就可以實現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法,去看看組合數(shù)學(xué),尚有逆序生成排列和一些不需要遞歸生成排列的方法。

印象中Knuｔh的<TAOＣP＞第一卷里面進(jìn)一步講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，?也需要一定的靈感，有愛好最佳看看。解：同53題。７1.數(shù)值的整數(shù)次方。題目:實現(xiàn)函數(shù)ｄoubｌePoｗｅr(ｄoubｌebａse，inｔexpｏnenｔ)，求bａse的ｅxｐonenｔ次方。

不需要考慮溢出。分析:這是一道看起來很簡樸的問題。也許有不少的人在看到題目后3０秒寫出如下的代碼：?dｏubｌeＰoｗer(dｏｕblebase，intexｐonenｔ)?{

ｄｏublerｅｓuｌt=1.０；

foｒ（inti=1;i<=ｅｘpoｎent;＋＋i)

resulｔ*＝base;?

returnresuｌt;

}解:上面算法代碼復(fù)雜度為O(expｏｎｅnt)，存在一個復(fù)雜度為Ｏ(logeｘponｅnｔ)的算法。算法思緒：【以下是求ｘy的函數(shù)中選取的關(guān)鍵代碼】設(shè)32位整型y的二進(jìn)制結(jié)果存放在數(shù)組ｙy［3１～0]中,ｙy[０]是最低位，則有y＝∑(yｙ[i]＝=1？2^i：0),0<=i<=３1 則x^ｙ=x^(∑(yy[i]==1?２＾i:0)) =x＾(∑2＾i)【相應(yīng)yｙ[i]==1，即非零二進(jìn)制位】?對于所有非零二進(jìn)制位yy[i]，相應(yīng)ｘ^(2^i）=?x^2^２^２．．．^2【共i次＾2】?假設(shè)tmp足夠存放x^ｙ(即不考慮溢出)，則可以如下方式計算?tmp=1;i=31;?whiｌe(i>＝0){ ｔｍp=tmp*tｍp;? ?if（yy[i])tmp＝tｍp＊ｘ; ?? i--; ? ?} 例如x=10,y=25,則yy[31]={0,0,..．,0,１,１，0，0,1}上述wｈile循環(huán)最后5次，ｔmp的值依次變化為1０,１０^３,1０＾６，10＾１2,1０^25,可以看出不管ｙ多大,這個whilｅ循環(huán)只執(zhí)行3２次。７2.

題目:設(shè)計一個類，我們只能生成該類的一個實例。?分析：只能生成一個實例的類是實現(xiàn)了Ｓｉnｇleton模式的類型。73．對稱字符串的最大長度。題目:輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。?比如輸入字符串“gｏogle”，由于該字符串里最長的對稱子字符串是“gｏog”，因此輸出4。分析:也許很多人都寫過判斷一個字符串是不是對稱的函數(shù),這個題目可以當(dāng)作是該函數(shù)的加強(qiáng)版。７4.數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半,找出這個數(shù)字。分析：這是一道廣為流傳的面試題，涉及百度、微軟和Ｇooglｅ在內(nèi)的多家公司都?曾經(jīng)采用過這個題目。要幾十分鐘的時間里很好地解答這道題,

除了較好的編程能力之外，還需要較快的反映和較強(qiáng)的邏輯思維能力。75.二叉樹兩個結(jié)點的最低共同父結(jié)點?題目:二叉樹的結(jié)點定義如下：

ｓtrｕｃｔTreeNodｅ?｛

inｔｍ_ｎvalue;

TreeNoｄe*ｍ_pLefｔ;?

TｒeeNode*m_pRiｇht；

};輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。

分析：求數(shù)中兩個結(jié)點的最低共同結(jié)點是面試中經(jīng)常出現(xiàn)的一個問題。這個問題至少有兩個變種。解:假設(shè)兩結(jié)點為A,B,【且其中任一結(jié)點不是此外一個結(jié)點的祖先】，按先根遍歷的方式，設(shè)立解向量(也可理解成棧)TｒeeNode＊X［];從樹根開始遍歷，遍歷到A結(jié)點時，一路遍歷過的結(jié)點依次存放在X[1～ｋ］【其中X［1]為樹的根,Ｘ[k]為A的父結(jié)點】,則依次取出結(jié)點X[k]，Ｘ[ｋ-1］,…,X［１],對其遍歷此外一棵子樹（即A不在其中的子樹）,假如能找到B,則取出的X[t］即為所求(其中1＜=ｔ<=k）；否則就返回ＮＵＬL，表達(dá)Ａ,B不在一棵樹中。

76．復(fù)雜鏈表的復(fù)制題目：有一個復(fù)雜鏈表,其結(jié)點除了有一個m＿pNext指針指向下一個結(jié)點外，

尚有一個m_pSｉblｉng指向鏈表中的任一結(jié)點或者ＮULL。其結(jié)點的C++定義如下：?

stｒuｃtCompｌexＮode?{?

intm_nVaｌue;?

CompｌｅxNode*ｍ_pNext;

ComｐlexＮode*m＿pＳiｂlｉｎg;?};下圖是一個具有5個結(jié)點的該類型復(fù)雜鏈表。

圖中實線箭頭表達(dá)m_pＮexｔ指針,虛線箭頭表達(dá)m_ｐＳibｌinｇ指針。為簡樸起見,

指向NULＬ的指針沒有畫出。請完畢函數(shù)CｏmpｌexNｏde＊Ｃlｏｎe(ＣomplｅxNｏｄｅ＊pHead),以復(fù)制一個復(fù)雜鏈表。

分析：在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化,這是一種很新奇的面試題。

要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反映能力，

對數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實的編程功底。77.關(guān)于鏈表問題的面試題目如下:1.給定單鏈表,檢測是否有環(huán)。使用兩個指針ｐ１,ｐ２從鏈表頭開始遍歷，p1每次前進(jìn)一步,p2每次前進(jìn)兩步。假如p2到達(dá)鏈表尾部，說明無環(huán),否則p１、ｐ2必然會在某個時刻相遇（p1==ｐ2）,從而檢測到鏈表中有環(huán)?！居协h(huán)的話,p２肯定會在環(huán)上追上p１】2.給定兩個單鏈表(heaｄ1,head2）,檢測兩個鏈表是否有交點，假如有返回第一個交點。假如ｈead１=＝heａd2,那么顯然相交，直接返回head1。

否則，分別從heaｄ1,ｈｅad2開始遍歷兩個鏈表獲得其長度leｎ1與len2,假設(shè)lｅn１>＝leｎ2，

那么指針p1由hｅad1開始向后移動leｎ1-len2步，指針ｐ2=heａｄ2，下面p１、p2每次向后前進(jìn)一步并比較p1p2是否相等，假如相等即返回該結(jié)點，否則說明兩個鏈表沒有交點。【完美】?3．給定單鏈表(heａd）,假如有環(huán)的話請返回從頭結(jié)點進(jìn)入環(huán)的第一個節(jié)點。?

運用題一,我們可以檢查鏈表中是否有環(huán)。

假如有環(huán)，那么p1p2重合點p必然在環(huán)中。從ｐ點斷開環(huán),

方法為:p1=p,p2=p-＞nｅxt，p－>next=NUＬL。此時,原單鏈表可以看作兩條單鏈表，?一條從ｈeaｄ開始，另一條從p2開始,于是運用題二的方法,我們找到它們的第一個交點即為所求?！厩擅睢?．只給定單鏈表中某個結(jié)點ｐ(并非最后一個結(jié)點，即ｐ－>nｅxｔ!=NULL)指針,刪除該結(jié)點。?辦法很簡樸,一方面是釋放p中數(shù)據(jù),然后將p－＞ｎext的數(shù)據(jù)coｐy入p中,接下來刪除p->next即可?！九c前面一題相同】5．只給定單鏈表中某個結(jié)點p(非空結(jié)點)，在ｐ前面插入一個結(jié)點。

辦法與前者類似,一方面分派一個結(jié)點q,將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。７8.鏈表和數(shù)組的區(qū)別在哪里?分析：重要在基本概念上的理解。

但是最佳能考慮的全面一點，現(xiàn)在公司招人的競爭也許就在細(xì)節(jié)上產(chǎn)生，?誰比較仔細(xì)，誰獲勝的機(jī)會就大。7９.?1.編寫實現(xiàn)鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？【直接插入排序,應(yīng)當(dāng)是最常用的,由于只需操作指針域】2.編寫實現(xiàn)數(shù)組排序的一種算法。說明為什么你會選擇用這樣的方法?【太多了】3.請編寫能直接實現(xiàn)strstｒ()函數(shù)功能的代碼。80．阿里巴巴一道筆試題問題描述:

12個高矮不同的人,排成兩排,每排必須是從矮到高排列,并且第二排比相應(yīng)的第一排的人高,問排列方式有多少種?這個筆試題,很YD,由于把某個遞歸關(guān)系隱藏得很深?！究蓞⒖肌肯葋韼捉M百度的面試題：===================81.第1組百度面試題?1.一個iｎt數(shù)組,里面數(shù)據(jù)無任何限制,規(guī)定求出所有這樣的數(shù)a［i],

其左邊的數(shù)都小于等于它,右邊的數(shù)都大于等于它。?能否只用一個額外數(shù)組和少量其它空間實現(xiàn)。2.一個文獻(xiàn),內(nèi)含一千萬行字符串,每個字符串在1K以內(nèi),

規(guī)定找出所有相反的串對，如ａｂc和cbａ。３.ＳＴＬ的set用什么實現(xiàn)的？為什么不用hａｓh？8２.第2組百度面試題

1.給出兩個集合A和B，其中集合A={name},

集合Ｂ={age、sex、sｃholａrshiｐ、addｒｅｓｓ、...}，

規(guī)定：

問題1、根據(jù)集合A中的naｍe查詢出集合Ｂ中相應(yīng)的屬性信息;?問題２、根據(jù)集合B中的屬性信息（單個屬性,如age<20等）,查詢出集合A中相應(yīng)的name。2．給出一個文獻(xiàn),里面包含兩個字段{url、size｝,

即ｕrl為網(wǎng)址,ｓｉze為相應(yīng)網(wǎng)址訪問的次數(shù),

規(guī)定:

問題1、運用LｉnuxSｈｅll命令或自己設(shè)計算法，

查詢出url字符串中包含“ｂaidu”子字符串相應(yīng)的ｓiｚe字段值；?問題2、根據(jù)問題1的查詢結(jié)果，對其按照size由大到小的排列。?(說明:url數(shù)據(jù)量很大，10０億級以上）

８３.第3組百度面試題?1.今年百度的一道題目?百度筆試：給定一個存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù),右邊為偶數(shù)。

規(guī)定：空間復(fù)雜度Ｏ(１),時間復(fù)雜度為O（n）。2．百度筆試題

用Ｃ語言實現(xiàn)函數(shù)void*memmove(ｖoid＊dest,constvoid*sｒc，size_ｔn）。

memmｏｖe函數(shù)的功能是拷貝sｒc所指的內(nèi)存內(nèi)容前n個字節(jié)到dｅst所指的地址上。

分析:

由于可以把任何類型的指針賦給voｉｄ類型的指針?這個函數(shù)重要是實現(xiàn)各種數(shù)據(jù)類型的拷貝。

84．第4組百度面試題

2023年3道百度面試題［相信,你懂其中的含金量］

１．a(chǎn)~z涉及大小寫與0~9組成的N個數(shù)?用最快的方式把其中反復(fù)的元素挑出來。?2.已知一隨機(jī)發(fā)生器，產(chǎn)生０的概率是ｐ，產(chǎn)生１的概率是1-ｐ，現(xiàn)在要你構(gòu)造一個發(fā)生器,?使得它構(gòu)造0和１的概率均為1/2；構(gòu)造一個發(fā)生器，使得它構(gòu)造１、2、3的概率均為1／３;..．,

構(gòu)造一個發(fā)生器，使得它構(gòu)造１、2、3、..．ｎ的概率均為1/n，規(guī)定復(fù)雜度最低。

３．有10個文獻(xiàn),每個文獻(xiàn)１Ｇ,?每個文獻(xiàn)的每一行都存放的是用戶的qｕery,每個文獻(xiàn)的query都也許反復(fù)。

規(guī)定按照quｅry的頻度排序.

85.又見字符串的問題

1.給出一個函數(shù)來復(fù)制兩個字符串A和B。?字符串A的后幾個字節(jié)和字符串B的前幾個字節(jié)重疊。

分析:記住,這種題目往往就是考你對邊界的考慮情況。

2.已知一個字符串，比如asderwｓde，尋找其中的一個子字符串比如sdｅ的個數(shù),

假如沒有返回0，有的話返回子字符串的個數(shù)。

?８6.

如何編寫一個程序,把一個有序整數(shù)數(shù)組放到二叉樹中？?分析:本題考察二叉搜索樹的建樹方法,簡樸的遞歸結(jié)構(gòu)。?關(guān)于樹的算法設(shè)計一定要聯(lián)想到遞歸，由于樹自身就是遞歸的定義。而，學(xué)會把遞歸改稱非遞歸也是一種必要的技術(shù)。?畢竟，遞歸會導(dǎo)致棧溢出,關(guān)于系統(tǒng)底層的程序中不到非不得以最佳不要用。?但是對某些數(shù)學(xué)問題，就一定要學(xué)會用遞歸去解決。

87.?１.大整數(shù)數(shù)相乘的問題。（這是２023年在一考研班上碰到的算法題）

２．求最大連續(xù)遞增數(shù)字串（如“ads３sl４5６789ＤF345６ld３45ＡＡ”中的“４56７８9”）

3.實現(xiàn)sｔrsｔr功能，即在父串中尋找子串初次出現(xiàn)的位置。?(筆試中常讓面試者實現(xiàn)標(biāo)準(zhǔn)庫中的一些函數(shù)）

8８.2０23年１1月金山筆試題。編碼完畢下面的解決函數(shù)。

函數(shù)將字符串中的字符'*＇移到串的前部分,前面的非'*'字符后移,但不能改變非＇*'字符的先后順序,函數(shù)返回串中字符'*＇的數(shù)量。

如原始串為：ab**ｃd＊*ｅ*1２,

解決后為**＊＊＊aｂcｄe1２，函數(shù)并返回值為5。(規(guī)定使用盡量少的時間和輔助空間）

８9.神州數(shù)碼、華為、東軟筆試題

1．２023年11月15日華為軟件研發(fā)筆試題。實現(xiàn)一單鏈表的逆轉(zhuǎn)。?2.編碼實現(xiàn)字符串轉(zhuǎn)整型的函數(shù)（實現(xiàn)函數(shù)atoi的功能），據(jù)說是神州數(shù)碼筆試題。如將字符?串”+123”１２３,”-０123”-１23，“123ＣＳ45”123，“１23.45CS”1２3,“CＳ12３.４5”０?3.快速排序（東軟喜歡考類似的算法填空題,又如堆排序的算法等)

４.刪除字符串中的數(shù)字并壓縮字符串。

如字符串”aｂｃ１23ｄ