算法面試題總結(jié)

算法面試題總結(jié)1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。

10

/\

6

14

/\/\

4

81216

轉(zhuǎn)換成雙向鏈表

4=6=8=10=12=14=16。解：首先我們定義的二元查找樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：typedefstructtree{

intdata;//valueofnode

structtree*left;//leftchildofnode

structtree*right;//rightchildofnode

}*ptree;ptreef(ptreeroot,intsign)//sign==0返回鏈頭，sign==1返回鏈尾{//main函數(shù)中調(diào)用f(root,0); ptreep=root; if(p->left)//如果左子樹非空 { p->left=f(p->left,1);//第4個(gè)參數(shù)為，表明f函數(shù)返回root左子樹中根的鏈尾 p->left->right=p;//雙鏈表中l(wèi)eft記錄前驅(qū)，right記錄后繼 } if(p->right) { p->right=f(p->right,0); p->right->left=p; } if(sign==0)while(p->left)p=p->left;//順著left找到雙鏈表首元素 elsewhile(p->right)p=p->right;//順著right找到雙鏈表尾元素 returnp;}2.設(shè)計(jì)包含min函數(shù)的棧。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。3.求子數(shù)組的最大和題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。例如輸入的數(shù)組為1,-2,3,10,-4,7,2,-5，和最大的子數(shù)組為3,10,-4,7,2，因此輸出為該子數(shù)組的和18。解：設(shè)數(shù)組元素為a[1~n]，f(i)表示以a[i]為尾元素的最大子段和，則有f(1)=a[1],f(i)=max{f(i-1)+a[i],a[i]}(i>1)動(dòng)態(tài)規(guī)劃求f(i),b[i]保存f(i)的值。Intf(inti){intj,max;max=b[1]=a[1];for(j=2;j<=I;j++){b[i]=a[i-1]>0?a[i-1]+a[i]:a[i];if(b[i]>max)max=b[i];}returnmax;//返回b[1]~b[i]中最大值}4.在二元樹中找出和為某一值的所有路徑題目：輸入一個(gè)整數(shù)和一棵二元樹。從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如輸入整數(shù)22和如下二元樹

10

/\

5

12

/

\

4

7

則打印出兩條路徑：10,12和10,5,7。解：首先我們定義的二元查找樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：typedefstructtree{

intdata;//valueofnode

structtree*left;//leftchildofnode

structtree*right;//rightchildofnode

}*ptree;ptreeX[MAX];//X記住路徑設(shè)樹的根為root;指定和為S，以下為回溯算法voidf(intk,ptreeroot,intsum)//sum為已訪問結(jié)點(diǎn)元素之和{intj,ss=sum+root->data;X[k]=root;if(ss==S){printf(“\n”);for(j=1;j<=k;j++)printf(“%d”,X[j]->data);}else{if(root->left&&ss<S)f(k+1,root->left,ss);if(root->right&&ss<S)f(k+1,root->right,ss);}}5.查找最小的k個(gè)元素題目：輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1，2，3和4。解：1：可以借用找第k小元素的辦法，當(dāng)找到第k小元素時(shí)，這一元素和它左邊的元素構(gòu)成最小的k個(gè)元素。2：可以考慮用小堆排序的辦法，每一次小堆調(diào)整得到最小的元素，進(jìn)行k次小堆調(diào)整即可得到k個(gè)最小元素的有序序列。第6題騰訊面試題：給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對應(yīng)的十個(gè)數(shù)要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。上排的十個(gè)數(shù)如下：【0，1，2，3，4，5，6，7，8，9】舉一個(gè)例子，數(shù)值:0,1,2,3,4,5,6,7,8,9

分配:6,2,1,0,0,0,1,0,0,0

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

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

以此類推..解：設(shè)X[0~9]分別為數(shù)字0~9出現(xiàn)次數(shù)，即回溯算法求解向量，同時(shí)用S[0~9]記住X[0~9]中數(shù)字0~9出現(xiàn)次數(shù)?！?，1，2，3，4，5，6，7，8，9】，X[]={}voidf(intk){intj;if(k==10)for(j=0;j<10;j++)cout<<X[j]<<””;elsefor(j=0;j<10;j++){X[k]=j;S[j]++;f(k+1);S[j]--;}}voidmain(){f(0);}第7題微軟亞院之編程判斷倆個(gè)鏈表是否相交給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。為了簡化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。解：無環(huán)且能相交，形狀應(yīng)該只能為簡單的處理，即對兩個(gè)單鏈表都訪問到尾結(jié)點(diǎn)，看最后訪問的尾結(jié)點(diǎn)是否相同。問題擴(kuò)展：

1.如果鏈表可能有環(huán)列?

2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?第8題

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

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

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

有什么辦法呢？解：燈的亮滅只有2種狀態(tài)，開關(guān)也只有2種狀態(tài)，但是需要區(qū)分3盞燈，增加一個(gè)新狀態(tài)量：加熱一定時(shí)間的燈泡會(huì)發(fā)熱。這樣的話，可以區(qū)分的燈可以增加到4盞，進(jìn)開關(guān)所在屋，閉合開關(guān)1,2，約5分鐘后，關(guān)閉1，閉合開關(guān)3，進(jìn)入燈所在屋，發(fā)光又發(fā)熱被2控制，發(fā)光不發(fā)熱的被3控制，不發(fā)光而發(fā)熱的被1控制，不發(fā)光不發(fā)熱的被4控制。2.你讓一些人為你工作了七天，你要用一根金條作為報(bào)酬。金條被分成七小塊，每天給出一塊。

如果你只能將金條切割兩次，你怎樣分給這些工人?解：7=1+2+43.★用一種算法來顛倒一個(gè)鏈接表的順序?，F(xiàn)在在不用遞歸式的情況下做一遍。解：用單鏈表的頭插法，把從頭到尾的結(jié)點(diǎn)依次重新插入依次。★用一種算法在一個(gè)循環(huán)的鏈接表里插入一個(gè)節(jié)點(diǎn)，但不得穿越鏈接表?！镉靡环N算法整理一個(gè)數(shù)組。你為什么選擇這種方法?★用一種算法使通用字符串相匹配?！镱嵉挂粋€(gè)字符串。優(yōu)化速度。優(yōu)化空間。★顛倒一個(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實(shí)現(xiàn)速度最快，移動(dòng)最少。詞？是“克麗絲叫我”還是“絲麗克叫我”？★找到一個(gè)子字符串。優(yōu)化速度。優(yōu)化空間。★比較兩個(gè)字符串，用O(n)時(shí)間和恒量空間。解：intstrcmp(char*s1,char*s2){while(*s1&&*s2&&*(s1++)==*(s2++));return*s1-*s2;}★假設(shè)你有一個(gè)用1001個(gè)整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個(gè)數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個(gè)數(shù)組做一次處理，用一種算法找出重復(fù)的那個(gè)數(shù)字。如果你在運(yùn)算中使用了輔助的存儲(chǔ)方式，那么你能找到不用這種方式的算法嗎?解：累加求和-（1+2+…+1000）★不用乘法或加法增加8倍?，F(xiàn)在用同樣的方法增加7倍。

第9題

判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果

題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。

如果是返回true，否則返回false。例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：8

/

\

6

10

/\

/\

5

79

11

因此返回true。

如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。解：設(shè)數(shù)組a[from~to]，函數(shù)f(from,to)判斷其是否可以為某二叉樹后序結(jié)果，intf(intfrom,intto){inti=from,j,s1,s2;while(i<to&&a[i]<a[to])i++;//找到第一個(gè)大于等于根a[to]的元素a[i]j=i-1;//a[from~j]為左子樹部分，a[j+1~to-1]為右子樹部分while(i<to)if(a[i]<a[to])return0;//右子樹中不可能還有小于根的值if(from>=j)s1=1;elses1=f(from,j);//對左子樹判斷if(j+1>=to-1)s2=1;elses2=f(j+1,to-1);//對右子樹判斷returns1&&s2;//返回左右子樹判斷與結(jié)果}第10題

翻轉(zhuǎn)句子中單詞的順序。

題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。

例如輸入“Iamastudent.”，則輸出“student.aamI”。解：假設(shè)句子存放在chars[MAX]中，voidf(){chartmp;Intlen=strlen(s),I,j,k;for(i=0,j=len-1;i<j;i++,j--)//整個(gè)句子顛倒{tmp=s[i];s[i]=s[j];s[j]=tmp;}//s[i]與s[j]交換for(k=0;k<len;k++){I=k;while(s[i]==‘’)i++;//定位單詞的頭j=i;while(s[j+1]!=‘’)j++;定位單詞的尾k=j+2;while(i<j)//單詞顛倒{tmp=s[i];s[i]=s[j];s[j]=tmp;//s[i]與s[j]交換I++;j--;}}}第11題

求二叉樹中節(jié)點(diǎn)的最大距離...如果我們把二叉樹看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，

我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。

寫一個(gè)程序，

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

intdata;//valueofnodeintlh,rh,h;//lh,rh為左、右子樹高度，h=max(lh,rh)+1structtree*left;//leftchildofnode

structtree*right;//rightchildofnode

}*ptree;假設(shè)樹的根為root求各非葉子節(jié)點(diǎn)的左右子樹高度inth(ptreeroot)//返回h{if(!root)return0;root->lh=h(root->left);root->rh=h(root->right);returnroot->h=(root->lh>root->rh?root->lh+1:root->rh+1);}//求最大距離，最大距離有3種可能，兩節(jié)點(diǎn)均在左子樹、右子樹，或一個(gè)在左，一個(gè)在右Intf(ptreeroot){intlen1,len2,len3;If(!root)return0;Else{len1=f(root->left);//左子樹中最大距離值len2=f(root->right);//右子樹中最大距離值len3=1;//一個(gè)頂點(diǎn)在左子樹，一個(gè)頂點(diǎn)在右子樹，最大距離值if(root->left)len3+=root->left->h;if(root->right)len3+=root->right->h;if(len1<len2)len1=len2;//len1保存len1，len2中較大者if(len1<len3)len1=len3;returnlen1;//返回最大值}}第12題

題目：求1+2+…+n，

要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。解：intf(intn){ints=0;n&&s=n+f(n-1);returns;}第13題：

題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。

鏈表結(jié)點(diǎn)定義如下：

structListNode

{

intm_nKey;

ListNode*m_pNext;

};第14題：

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

要求時(shí)間復(fù)雜度是O(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。

例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。解：假設(shè)數(shù)組為a[1~n]，輸入和的數(shù)字為S，算法思路for(i=1,j=n;i<j;)if(a[i]+a[j]==S){printf(“%d+%d=%d”,a[i],a[j],S);i++;j--;//break;}elseif(a[i]+a[j]<S)i++;elseif(a[i]+a[j]>S)j--;第15題：

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

8

/\

610/\/\57911輸出：

8

/\

106/\/\11975解：寫遞歸函數(shù)，左右子樹交換。首先我們定義的二元查找樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：typedefstructtree{

intdata;//valueofnode

structtree*left;//leftchildofnode

structtree*right;//rightchildofnode

}*ptree;voidf(ptreeroot){if(!root)return;f(root->left);//對左右子樹進(jìn)行鏡像處理f(root->right);if(root->left||root->right){ptreetmp=root->left;root->left=root->right;root->right=tmp;}}第16題：

題目（微軟）：

輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。

例如輸入

8

/\

610

/\/\

57911輸出861057911。解：用隊(duì)列實(shí)現(xiàn)。第17題：

題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。

分析：這道題是2006年google的一道筆試題。解：用數(shù)組a[26]存放個(gè)字符出現(xiàn)次數(shù){初始化為0}，用b[26]存放依次出現(xiàn)字符順序，對整個(gè)字符串掃描一次，設(shè)當(dāng)前掃描字符為c，則執(zhí)行a[c-‘a(chǎn)’]++;如果a[c-‘a(chǎn)’]==1，則b[k++]=c;其中k初始值為0；掃描結(jié)束后依次檢查b[0]~b[k-1]，如果a[b[t]-‘a(chǎn)’]==1則輸出b[t]。

第18題：

題目：n個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0開始，

每次從這個(gè)圓圈中刪除第k個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)字）。

當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第k個(gè)數(shù)字。

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

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

第19題：

題目：定義Fibonacci數(shù)列如下：

/0n=0

f(n)=1n=1

\f(n-1)+f(n-2)n=2輸入n，用最快的方法求該數(shù)列的第n項(xiàng)。

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

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

題目：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。

例如輸入字符串"345"，則輸出整數(shù)345。解：略。第21題

2023年中興面試題

編程求解：

輸入兩個(gè)整數(shù)n和m，從數(shù)列1，2，3.......n中隨意取幾個(gè)數(shù)，使其和等于m，要求將其中所有的可能組合列出來.解：回溯算法(子集和數(shù)問題)。IntX[MAX];voidf(intk,intsum)//sum=X[1]+X[2]+…+X[k-1]{inti;if(sum==m){printf(“\n”);for(i=1;i<k;i++)printf(“%d”,X[i]);}elsefor(i=X[k-1]+1;i<n;i++)if(sum+i<=m)//剪枝作用{X[k]=i;f(k+1,sum+i);}}voidmain(){f(1,0);}第22題：

有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，

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

A說不知道，B說不知道，C說不知道，然后A說知道了。

請教如何推理，A是怎么知道的。

如果用程序，又怎么實(shí)現(xiàn)呢？

第23題：

用最簡單，最快速的方法計(jì)算出下面這個(gè)圓形是否和正方形相交。"

3D坐標(biāo)系原點(diǎn)(0.0,0.0,0.0)

圓形:

半徑r=3.0

圓心o=(*.*,0.0,*.*)正方形:

4個(gè)角坐標(biāo);

1:(*.*,0.0,*.*)

2:(*.*,0.0,*.*)

3:(*.*,0.0,*.*)

4:(*.*,0.0,*.*)解：首先計(jì)算出正方形四條邊的直線方程，并依據(jù)點(diǎn)到直線距離公式，計(jì)算出圓心到四條邊的距離（設(shè)為d1,d2,d3,d4），且只要d1~d4有一個(gè)小于r，則相交，否則不相交。第24題：

鏈表操作，

（1）.單鏈表就地逆置，

（2）合并鏈表第25題：

寫一個(gè)函數(shù),它的原形是intcontinumax(char*outputstr,char*intputstr)

功能：

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

并把這個(gè)最長數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存。

例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，

outputstr所指的值為12345678926.左旋轉(zhuǎn)字符串題目：

定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。

要求時(shí)間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。27.跳臺(tái)階問題

題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。

求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司

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

題目：輸入一個(gè)整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個(gè)1。

例如輸入10，由于其二進(jìn)制表示為1010，有兩個(gè)1，因此輸出2。分析：

這是一道很基本的考查位運(yùn)算的面試題。

包括微軟在內(nèi)的很多公司都曾采用過這道題。29.棧的push、pop序列

題目：輸入兩個(gè)整數(shù)序列。其中一個(gè)序列表示棧的push順序，

判斷另一個(gè)序列有沒有可能是對應(yīng)的pop順序。

為了簡單起見，我們假設(shè)push序列的任意兩個(gè)整數(shù)都是不相等的。

比如輸入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一個(gè)pop系列。

因?yàn)榭梢杂腥缦碌膒ush和pop序列：

push1，push2，push3，push4，pop，push5，pop，pop，pop，pop，

這樣得到的pop序列就是4、5、3、2、1。

但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。解：為簡單起見，設(shè)push序列為遞增的，要判斷a[1~n]系列是否為可能的pop序列，對于任意a[i]只需檢查a[i]右側(cè)比a[i]小的數(shù)字是否構(gòu)成遞減序列。例如上面4、3、5、1、2，其中4右側(cè)比它小的數(shù)分別為3、1、2，不是遞減序列，所以它為不可能的pop序列。intf(){Inti,j,X[MAX],k;for(i=1;i<=n;i++){k=0;j=i+1;X[0]=a[i];while(j<=n)if(a[j]<a[i]){if(a[j]>X[k])return0;//不構(gòu)成遞減序列X[++k]=a[j];}}return1;//上面沒有碰到非遞減情況，則是可能的pop序列，時(shí)間復(fù)雜度O(n2)}30.在從1到n的正數(shù)中1出現(xiàn)的次數(shù)

題目：輸入一個(gè)整數(shù)n，求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。例如輸入12，從1到12這些整數(shù)中包含1的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。

分析：這是一道廣為流傳的google面試題。解：先對N各個(gè)數(shù)位進(jìn)行運(yùn)算分析，設(shè)N=an*10n+an-1*10n-1+…+a1*101+a0，即其個(gè)位數(shù)為a0,十位數(shù)為a1,…，用f(N)表示1到N的所有整數(shù)中1出現(xiàn)次數(shù)，則有：f(N)=0N=0an*n*10n-1+(an>1?10n:(N-10n+1))+f(N%10n)N>0例如當(dāng)N介于1~9時(shí)f(N)=1，可由上面遞推式驗(yàn)證。另外驗(yàn)證下面兩個(gè)：f(14)=1*1*1+(14-10+1)+f(14%10)=6+f(4)=7f(114)=1*2*10+(114-100+1)+f(114%100)=35+f(14)=42（分析另外展開）31.華為面試題：

一類似于蜂窩的結(jié)構(gòu)的圖，進(jìn)行搜索最短路徑（要求5分鐘）32.

有兩個(gè)序列a,b，大小都為n,序列元素的值任意整數(shù)，無序；

要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。

例如:

vara=[100,99,98,1,2,3];

varb=[1,2,3,4,5,40];解：回溯算法，與禮物分配算法接近。33.

實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法：

給一串很長字符串，要求找到符合要求的字符串，例如目的串：123

1******3***2,12*****3這些都要找出來

其實(shí)就是類似一些和諧系統(tǒng)。。。。。34.

實(shí)現(xiàn)一個(gè)隊(duì)列。

隊(duì)列的應(yīng)用場景為：

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

求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:

12034

23451

11530

中最大的是:

45

53

要求:(1)寫出算法;(2)分析時(shí)間復(fù)雜度;(3)用C寫出關(guān)鍵代碼解：假設(shè)矩陣為a[m][n]，用f(I,j)表示以a[i][j]為矩形右下角元素的最大子矩陣和，則求出所有f(I,j)后確定其中最大者即可。f(I,j)的計(jì)算方式為Intf(intI,intj){Inti1,j1,tmp[MAX]={0},max=-pow(2,31);for(i1=I;i1>=0;i1--){sum=0;for(j1=j;j1>=0;j1--)tmp[j1]+=a[i1][j1];//第一次執(zhí)行時(shí)，僅將矩陣i行值賦值到tmp[]for(j1=j;j1>=0;j1--){sum+=tmp[j1];If(sum>max)max=sum;}}Returnmax;//max即為以a[i][j]為矩形右下角元素的最大值}第36題-40題（有些題目搜集于CSDN上的網(wǎng)友，已標(biāo)明）：

36.引用自網(wǎng)友：longzuo

谷歌筆試：

n支隊(duì)伍比賽，分別編號(hào)為0，1，2。。。。n-1，已知它們之間的實(shí)力對比關(guān)系，

存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中，w[i][j]的值代表編號(hào)為i，j的隊(duì)伍中更強(qiáng)的一支。所以w[i][j]=i或者j，現(xiàn)在給出它們的出場順序，并存儲(chǔ)在數(shù)組order[n]中，

比如order[n]={4,3,5,8,1......}，那么第一輪比賽就是4對3，5對8。.......

勝者晉級(jí)，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，

下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order和用于輸出比賽名次的數(shù)組result[n]，

求出result。解：按題意應(yīng)該滿足n=2k，初始化result[]為0，result[i]對應(yīng)編號(hào)為order[i]的隊(duì)伍最終獲得名次。則算法可以如下運(yùn)行（每一輪比賽兩兩進(jìn)行，輸者名次為t），t=n;player1=1;player2=2;for(i=n/2;i>0;i=i/2){j=0;player1=1;while(j<i)//找i對隊(duì)伍進(jìn)行比賽并確定名次{while(result[player1])player1++;player2=player1+1;while(result[player2])player2++;if(w[order[player1]][order[player2]]==order[player1])result[player2]=t--;elseresult[player1]=t--;player1=player2+1;j++;}}比如order[n]={4,3,5,8,1......}，最后計(jì)算的result[n]={3,6,2,1,8,…}，則說明編號(hào)4的隊(duì)伍最終名次為第3名，編號(hào)為3的隊(duì)伍名次為第6名，…37.

有n個(gè)長為m+1的字符串，

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

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

百度面試：

1.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個(gè)較輕的，使用x次天平，

最多可以從y個(gè)小球中找出較輕的那個(gè)，求y與x的關(guān)系式。2.有一個(gè)很大很大的輸入流，大到?jīng)]有存儲(chǔ)器可以將其存儲(chǔ)下來，

而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m個(gè)記錄。3.大量的URL字符串，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度39.

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

(1).

求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，

兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，

比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度。(2).

求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，

有向圖不再連通，描述算法。40.百度研發(fā)筆試題

引用自：zp155334877

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

設(shè)計(jì)一個(gè)算法，取出其中一段，要求包含所有N中顏色，并使長度最短。

并分析時(shí)間復(fù)雜度與空間復(fù)雜度。3)設(shè)計(jì)一個(gè)系統(tǒng)處理詞語搭配問題，比如說中國和人民可以搭配，

則中國人民人民中國都有效。要求：

*系統(tǒng)每秒的查詢數(shù)量可能上千次；

*詞語的數(shù)量級(jí)為10W；

*每個(gè)詞至多可以與1W個(gè)詞搭配當(dāng)用戶輸入中國人民的時(shí)候，要求返回與這個(gè)搭配詞組相關(guān)的信息。41.求固晶機(jī)的晶元查找程序

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

若匹配不過，照相機(jī)則按測好的晶元間距移到下一個(gè)位置。

求遍歷晶元盤的算法求思路。42.請修改append函數(shù)，利用這個(gè)函數(shù)實(shí)現(xiàn)：兩個(gè)非降序鏈表的并集，1->2->3和2->3->5并為1->2->3->5

另外只能輸出結(jié)果，不能修改兩個(gè)鏈表的數(shù)據(jù)。43.遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷。44.騰訊面試題：

1.設(shè)計(jì)一個(gè)魔方（六面）的程序。

2.有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。

請用5分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前10條。3.收藏了1萬條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似）45.雅虎：

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

比如{3，2，4，3，6}可以分成{3，2，4，3，6}m=1;

{3,6}{2,4,3}m=2

{3,3}{2,4}{6}m=3所以m的最大值為3解：設(shè)數(shù)組為a[0~n-1]思路：（1）先求和sum=，對sum約數(shù)分解，假設(shè)遞減排列為k1,k2,…kt，（2）對集合a[]內(nèi)元素分為ki（1≤i≤t）個(gè)子集，如果能使得所有子集元素之和相等，則ki即為所求?！緦⒓戏譃閗i個(gè)子集，所有可能的分解方法，可查回溯算法解決】46.搜狐：

四對括號(hào)可以有多少種匹配排列方式？比如兩對括號(hào)可以有兩種：（）（）和（（））解：F(0)=F(1)=1;F(n)=所以F(2)=F(0)F(1)+F(1)F(0)=2F(3)=F(0)F(2)+F(1)F(1)+F(2)F(0)=5F(4)=F(0)F(3)+F(1)F(2)+F(2)F(1)+F(3)F(0)=1447.創(chuàng)新工場：

求一個(gè)數(shù)組的最長遞減子序列比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{9，5，4，3，2}解：設(shè)數(shù)組為a[1~n]，F(xiàn)(n)為以a[n]為結(jié)尾元素所構(gòu)成的最長遞減子序列長度，則有F(1)=1;F(n)=max{F(i)}+1i<n且滿足a[i]>=a[n]然后動(dòng)態(tài)規(guī)劃計(jì)算。48.微軟：

一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}

是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。解：類似于二分查找，設(shè)數(shù)組a[1~n]Intfind(intfrom,intto,intkey){intmid=(from+to)/2;If(from>to)return-1;//查找失敗If(key==a[from])returnfrom;If(key>a[from]){if(key<a[mid]||(key>a[mid]&&a[from]>=a[mid]))returnfind(mid+1,to,key);elsereturnfind(from+1,mid-1,key);}else{if(key<a[mid]||(key>a[mid]&&a[from]>=a[mid]))returnfind(from+1,mid,key);elsereturnfind(mid+1,to,key);}}49.一道看上去很嚇人的算法面試題：

如何對n個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)50.網(wǎng)易有道筆試：

1.求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，

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

如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。

解：判斷一個(gè)有向連通圖是否連通，可以直接采用DFS算法，看是否能遍歷到所有頂點(diǎn)。所以此問題算法思路就容易處理，對圖的每一個(gè)頂點(diǎn)做刪除嘗試（同時(shí)刪除其關(guān)聯(lián)的邊），然后從任意頂點(diǎn)出發(fā)做DFS算法遍歷，如果不能遍歷到所有頂點(diǎn)（被刪頂點(diǎn)除外），則被刪頂點(diǎn)為割點(diǎn)，否則不是割點(diǎn)。

51.和為n連續(xù)正數(shù)序列。

題目：輸入一個(gè)正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個(gè)連續(xù)序列1-5、4-6和7-8。

分析：這是網(wǎng)易的一道面試題。解：這是一個(gè)一元二次方程的求解問題。設(shè)n分解為a+1,a+2,…,a+k（a>=0），則有n=ka+k(k+1)/2=>2n=k(2a+k+1)=>對2n進(jìn)行因式分解窮舉，設(shè)2n=i*j（i<j），則讓k=i，a=(j-i-1)/2，如果a為整數(shù)，則找到一個(gè)符合要求的解。

52.二元樹的深度。題目：輸入一棵二元樹的根結(jié)點(diǎn)，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度。例如：輸入二元樹：

10

/

\

6

14

/

/

\

4

12

16輸出該樹的深度3。二元樹的結(jié)點(diǎn)定義如下：structSBinaryTreeNode//anodeofthebinarytree

{

int

m_nValue;//valueofnode

SBinaryTreeNode

*m_pLeft;

//leftchildofnode

SBinaryTreeNode

*m_pRight;//rightchildofnode

};

分析：這道題本質(zhì)上還是考查二元樹的遍歷。解：略。53.字符串的排列。

題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。

例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來的所有字符串

abc、acb、bac、bca、cab和cba。分析：這是一道很好的考查對遞歸理解的編程題，

因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。解：回溯算法，與1~n的全排列幾乎一樣。不過有個(gè)細(xì)節(jié)問題，字符串中是否有重復(fù)字符呢？例如”abbaa”，則其排列結(jié)果有5！/3!/2!=10種?！咀ⅲ号cm點(diǎn)問題中操作數(shù)的排列重復(fù)是一樣的?！?4.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，

所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。解：這個(gè)應(yīng)該可以聯(lián)想到快速排序的一趟處理過程，其一趟的效果是使得一部分小于a[from]的元素都被搬到左邊，而大于a[from]的元素被搬到右邊。所以這個(gè)問題的解決就很簡單了。簡要思路：設(shè)數(shù)組為a[from~to]，置i=from，j=to，i從左往右找偶數(shù)，j從右往左找奇數(shù)，只要i，j沒有相遇，則將兩數(shù)交換，直到i，j相遇為止。55.

題目：類CMyString的聲明如下：

classCMyString

{

public:

CMyString(char*pData=NULL);

CMyString(constCMyString&str);

~CMyString(void);

CMyString&operator=(constCMyString&str);private:

char*m_pData;

};

請實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)，要求異常安全，即當(dāng)對一個(gè)對象進(jìn)行賦值時(shí)發(fā)生異常，對象的狀態(tài)不能改變。56.最長公共字串。題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。

請編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，

則輸出它們的長度4，并打印任意一個(gè)子串。分析：求最長公共子串（LongestCommonSubsequence,LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。解：動(dòng)態(tài)規(guī)劃算法例子，關(guān)于這個(gè)問題的資料到處都是（從略）。57.用倆個(gè)棧實(shí)現(xiàn)隊(duì)列。題目：某隊(duì)列的聲明如下：template<typenameT>classCQueue

{

public:

CQueue(){}

~CQueue(){}

voidappendTail(constT&node);

//appendaelementtotail

voiddeleteHead();

//removeaelementfromheadprivate:

T>m_stack1;

T>m_stack2;

};分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。

因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。

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

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

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

structListNode

{

int

m_nKey;

ListNode*m_pNext;

};

分析：這是一道很有意思的面試題。

該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。解：設(shè)頭結(jié)點(diǎn)為head;voidf(ListNode*h)//遞歸函數(shù)，是一個(gè)“天生”的棧{if(h){If(h->next)f(h->next);//先處理鏈表后面部分Cout<<h->m_nKey<<””;}}59.不能被繼承的類。題目：用C++設(shè)計(jì)一個(gè)不能被繼承的類。分析：這是Adobe公司2007年校園招聘的最新筆試題。

這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。60.在O（1）時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)。題目：給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：structListNode{

int

m_nKey;

ListNode*next;};函數(shù)的聲明如下：

voidDeleteNode(ListNode*pListHead,ListNode*pToBeDeleted);分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，更重要的是，還能考察我們對時(shí)間復(fù)雜度的理解。解：鏈表不能隨機(jī)訪問，要?jiǎng)h除pToBeDeleted結(jié)點(diǎn)，按常規(guī)處理是先找到其前驅(qū)（設(shè)為p），然后做刪除操作，但是對于單向鏈表而言，找到p結(jié)點(diǎn)顯然不是O(1)能完成的，除非是雙向鏈表，則可直接從pToBeDeleted結(jié)點(diǎn)獲取到其前驅(qū)p，然后執(zhí)行p->next=pToBeDeleted->next;free(pToBeDeleted);但是這題設(shè)計(jì)的巧妙之處就是，鏈表中節(jié)點(diǎn)的內(nèi)存格式是一樣的，所以可以把pToBeDeleted的后繼結(jié)點(diǎn)數(shù)據(jù)復(fù)制到pToBeDeleted中來，然后刪除pToBeDeleted的后繼。61.找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字

題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。

請寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。分析：這是一道很新穎的關(guān)于位運(yùn)算的面試題。62.找出鏈表的第一個(gè)公共結(jié)點(diǎn)。

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

structListNode{

int

m_nKey;

ListNode*

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

因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。63.在字符串中刪除特定的字符。

題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入”Theyarestudents.”和”aeiou”，則刪除之后的第一個(gè)字符串變成”Thyrstdnts.”。分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，

因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟?。解：字符個(gè)數(shù)不多，所以建立一個(gè)存儲(chǔ)信息m[26](假設(shè)不區(qū)分大小寫)，如果字符’a’+i出現(xiàn)在字符串二中，則m[i]=1，否則m[i]=0;設(shè)字符串一為char*s1;則刪除算法可表達(dá)如下：len=strlen(s1);count=0;//count記住已經(jīng)被刪除字符個(gè)數(shù)for(i=0;i<len;i++)if(m[s1[i]-‘a(chǎn)’])//如果字符s1[i]在字符串二中出現(xiàn){j=i+1;count++;while(!m[s1[j]-‘a(chǎn)’])s1[j-count]=s1[j++];//把s1[j]往前搬count個(gè)單元i=j;}【時(shí)間復(fù)雜度為O(n)。】64.尋找丑數(shù)。

題目：我們把只包含因子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ù)是否是丑數(shù)，最多進(jìn)行3次求余運(yùn)算，因?yàn)榻^大多數(shù)的整數(shù)都是2或3或5的倍數(shù)，所以要找到第1500個(gè)丑數(shù)，直接從1開始往后窮舉判斷即可?！颈热?~1000中是2或3或5的倍數(shù)個(gè)數(shù)有1000*（1/2+1/3+1/5-1/2*3-1/2*5-1/3*5+1/2*3*5）=733個(gè)。所以第1500個(gè)丑數(shù)大概在1500*(1000/733)=2046處，運(yùn)算量是可以承受的?！?/p>

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

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

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

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

顛倒之后的棧為{5,4,3,2,1}，5處在棧頂。67.倆個(gè)閑玩娛樂。1.撲克牌的順子

從撲克牌中隨機(jī)抽5張牌，判斷是不是一個(gè)順子，即這5張牌是不是連續(xù)的。

2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。2.n個(gè)骰子的點(diǎn)數(shù)。

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

打印出S的所有可能的值出現(xiàn)的概率。解：骰子的6個(gè)面分別點(diǎn)數(shù)1~6，每一個(gè)面朝上的概率1/6，n個(gè)朝上的面其點(diǎn)數(shù)之和S滿足n≤S≤6n，假設(shè)n個(gè)骰子投出S點(diǎn)的概率為f(n,S)，則f(n-1,S-1),f(n-1,S-2),f(n-1,S-3),f(n-1,S-4),f(n-1,S-5),f(n-1,S-6)分別表示n-1個(gè)骰子投出S-1,S-2,…,S-6點(diǎn)的概率，可分析出遞推關(guān)系式f(n,S)=0S<n||S>6n1/6n=1且1<=S<=6（f(n-1,S-1)+f(n-1,S-2)+f(n-1,S-3)+f(n-1,S-4)+f(n-1,S-5)+f(n-1,S-6)）/6n>1然后可動(dòng)態(tài)規(guī)劃算法計(jì)算f(n,S);【注：可驗(yàn)證f(2,5),即2個(gè)骰子投出5點(diǎn)的概率，顯然，樣本空間為6*6=36種，其中點(diǎn)數(shù)之和為5的有，14,23,32和41四種，即理論概率應(yīng)該是4/36。根據(jù)遞推關(guān)系式計(jì)算有f(2,5)=（f(1,4)+f(1,3)+f(1,2)+f(1,1)+f(1,0)+f(1,-1)）/6=4/36】68.把數(shù)組排成最小的數(shù)。

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

例如輸入數(shù)組{32,

321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。

請給出解決問題的算法，并證明該算法。分析：這是09年6月份百度的一道面試題，

從這道題我們可以看出百度對應(yīng)聘者在算法方面有很高的要求。解：對數(shù)組內(nèi)所有數(shù)按字符串字典序遞增排序，依據(jù)排序后順序?qū)⑵溥B接成一個(gè)數(shù)即為所求。但是這個(gè)字典序，有特殊情況的處理，即當(dāng)其中一個(gè)串（設(shè)為s1）是另外一個(gè)串（設(shè)為s2，其長度為n）的前綴部分時(shí)，如何確定其排序，是解決這個(gè)問題的關(guān)鍵。69.旋轉(zhuǎn)數(shù)組中的最小元素。

題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，

時(shí)間復(fù)雜度顯然是O(N)。但這個(gè)思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。解：設(shè)數(shù)組為a[1~n]，且是遞增數(shù)組的旋轉(zhuǎn)結(jié)果，類似于二分查找算法Intfind_min(intfrom,intto){intmid=(from+to)/2;If(a[from]<=a[to])returna[from];If(a[from]<a[mid])returnfind_min(mid+1,to);elsereturnfind_min(from,mid);}70.給出一個(gè)函數(shù)來輸出一個(gè)字符串的所有排列。

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

印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，

也需要一定的靈感，有興趣最好看看。解：同53題。71.數(shù)值的整數(shù)次方。題目：實(shí)現(xiàn)函數(shù)doublePower(doublebase,intexponent)，求base的exponent次方。

不需要考慮溢出。分析：這是一道看起來很簡單的問題?？赡苡胁簧俚娜嗽诳吹筋}目后30秒寫出如下的代碼：

doublePower(doublebase,intexponent)

{

doubleresult=1.0;

for(inti=1;i<=exponent;++i)

result*=base;

returnresult;

}解：上面算法代碼復(fù)雜度為O(exponent)，存在一個(gè)復(fù)雜度為O(logexponent)的算法。算法思路：【以下是求xy的函數(shù)中選取的關(guān)鍵代碼】設(shè)32位整型y的二進(jìn)制結(jié)果存放在數(shù)組yy[31~0]中，yy[0]是最低位，則有y=∑(yy[i]==1?2^i:0),0<=i<=31 則x^y=x^(∑(yy[i]==1?2^i:0)) =x^(∑2^i)【對應(yīng)yy[i]==1，即非零二進(jìn)制位】 對于所有非零二進(jìn)制位yy[i]，對應(yīng)x^(2^i)= x^2^2^2...^2【共i次^2】 假設(shè)tmp足夠存放x^y（即不考慮溢出），則可以如下方式計(jì)算 tmp=1;i=31; while(i>=0){ tmp=tmp*tmp; if(yy[i])tmp=tmp*x; i--; } 例如x=10，y=25，則yy[31]={0,0,...,0,1,1,0,0,1}上述while循環(huán)最后5次，tmp的值依次變化為10,10^3,10^6,10^12,10^25，可以看出不管y多大，這個(gè)while循環(huán)只執(zhí)行32次。72.

題目：設(shè)計(jì)一個(gè)類，我們只能生成該類的一個(gè)實(shí)例。

分析：只能生成一個(gè)實(shí)例的類是實(shí)現(xiàn)了Singleton模式的類型。73.對稱字符串的最大長度。題目：輸入一個(gè)字符串，輸出該字符串中對稱的子字符串的最大長度。

比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。分析：可能很多人都寫過判斷一個(gè)字符串是不是對稱的函數(shù)，這個(gè)題目可以看成是該函數(shù)的加強(qiáng)版。74.數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個(gè)數(shù)字。分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內(nèi)的多家公司都

曾經(jīng)采用過這個(gè)題目。要幾十分鐘的時(shí)間里很好地解答這道題，

除了較好的編程能力之外，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力。75.二叉樹兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)

題目：二叉樹的結(jié)點(diǎn)定義如下：

structTreeNode

{

intm_nvalue;

TreeNode*m_pLeft;

TreeNode*m_pRight;

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

分析：求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問題。這個(gè)問題至少有兩個(gè)變種。解：假設(shè)兩結(jié)點(diǎn)為A，B，【且其中任一結(jié)點(diǎn)不是另外一個(gè)結(jié)點(diǎn)的祖先】，按先根遍歷的方式，設(shè)置解向量（也可理解成棧）TreeNode*X[];從樹根開始遍歷，遍歷到A結(jié)點(diǎn)時(shí)，一路遍歷過的結(jié)點(diǎn)依次存放在X[1~k]【其中X[1]為樹的根，X[k]為A的父結(jié)點(diǎn)】，則依次取出結(jié)點(diǎn)X[k],X[k-1],…,X[1]，對其遍歷另外一棵子樹（即A不在其中的子樹），如果能找到B，則取出的X[t]即為所求（其中1<=t<=k）；否則就返回NULL，表示A，B不在一棵樹中。

76.復(fù)雜鏈表的復(fù)制題目：有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外，

還有一個(gè)m_pSibling指向鏈表中的任一結(jié)點(diǎn)或者NULL。其結(jié)點(diǎn)的C++定義如下：

structComplexNode

{

intm_nValue;

ComplexNode*m_pNext;

ComplexNode*m_pSibling;

};下圖是一個(gè)含有5個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。

圖中實(shí)線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，

指向NULL的指針沒有畫出。請完成函數(shù)ComplexNode*Clone(ComplexNode*pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。

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

要在不到一個(gè)小時(shí)的時(shí)間里解決這種類型的題目，我們需要較快的反應(yīng)能力，

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

否則，分別從head1,head2開始遍歷兩個(gè)鏈表獲得其長度len1與len2，假設(shè)len1>=len2，

那么指針p1由head1開始向后移動(dòng)len1-len2步，指針p2=head2，下面p1、p2每次向后前進(jìn)一步并比較p1p2是否相等，如果相等即返回該結(jié)點(diǎn)，否則說明兩個(gè)鏈表沒有交點(diǎn)。【完美】

3.給定單鏈表(head)，如果有環(huán)的話請返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。

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

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

方法為：p1=p,p2=p->next,p->next=NULL。此時(shí)，原單鏈表可以看作兩條單鏈表，

一條從head開始，另一條從p2開始，于是運(yùn)用題二的方法，我們找到它們的第一個(gè)交點(diǎn)即為所求。【巧妙】4.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)。

辦法很簡單，首先是釋放p中數(shù)據(jù)，然后將p->next的數(shù)據(jù)copy入p中，接下來刪除p->next即可?！九c前面一題相同】5.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。

辦法與前者類似，首先分配一個(gè)結(jié)點(diǎn)q，將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。78.鏈表和數(shù)組的區(qū)別在哪里？分析：主要在基本概念上的理解。

但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競爭可能就在細(xì)節(jié)上產(chǎn)生，

誰比較仔細(xì)，誰獲勝的機(jī)會(huì)就大。79.

1.編寫實(shí)現(xiàn)鏈表排序的一種算法。說明為什么你會(huì)選擇用這樣的方法？【直接插入排序，應(yīng)該是最常用的，因?yàn)橹恍璨僮髦羔樣颉?.編寫實(shí)現(xiàn)數(shù)組排序的一種算法。說明為什么你會(huì)選擇用這樣的方法？【太多了】3.請編寫能直接實(shí)現(xiàn)strstr()函數(shù)功能的代碼。80.阿里巴巴一道筆試題問題描述:

12個(gè)高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應(yīng)的第一排的人高,問排列方式有多少種?這個(gè)筆試題,很YD,因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深?！究蓞⒖肌肯葋韼捉M百度的面試題：===================81.第1組百度面試題

1.一個(gè)int數(shù)組，里面數(shù)據(jù)無任何限制，要求求出所有這樣的數(shù)a[i]，

其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。

能否只用一個(gè)額外數(shù)組和少量其它空間實(shí)現(xiàn)。2.一個(gè)文件，內(nèi)含一千萬行字符串，每個(gè)字符串在1K以內(nèi)，

要求找出所有相反的串對，如abc和cba。3.STL的set用什么實(shí)現(xiàn)的？為什么不用hash？82.第2組百度面試題

1.給出兩個(gè)集合A和B，其中集合A={name}，

集合B={age、sex、scholarship、address、...}，

要求：

問題1、根據(jù)集合A中的name查詢出集合B中對應(yīng)的屬性信息；

問題2、根據(jù)集合B中的屬性信息（單個(gè)屬性，如age<20等），查詢出集合A中對應(yīng)的name。2.給出一個(gè)文件，里面包含兩個(gè)字段{url、size}，

即url為網(wǎng)址，size為對應(yīng)網(wǎng)址訪問的次數(shù)，

要求：

問題1、利用LinuxShell命令或自己設(shè)計(jì)算法，

查詢出url字符串中包含“baidu”子字符串對應(yīng)的size字段值；

問題2、根據(jù)問題1的查詢結(jié)果，對其按照size由大到小的排列。

（說明：url數(shù)據(jù)量很大，100億級(jí)以上）83.第3組百度面試題

1.今年百度的一道題目

百度筆試：給定一個(gè)存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。

要求：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度為O（n）。2.百度筆試題

用C語言實(shí)現(xiàn)函數(shù)void*memmove(void*dest,constvoid*src,size_tn)。

memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個(gè)字節(jié)到dest所指的地址上。

分析：

由于可以把任何類型的指針賦給void類型的指針

這個(gè)函數(shù)主要是實(shí)現(xiàn)各種數(shù)據(jù)類型的拷貝。84.第4組百度面試題

2023年3道百度面試題[相信，你懂其中的含金量]

1.a~z包括大小寫與0~9組成的N個(gè)數(shù)

用最快的方式把其中重復(fù)的元素挑出來。

2.已知一隨機(jī)發(fā)生器，產(chǎn)生0的概率是p，產(chǎn)生1的概率是1-p，現(xiàn)在要你構(gòu)造一個(gè)發(fā)生器，

使得它構(gòu)造0和1的概率均為1/2；構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造1、2、3的概率均為1/3；...，

構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造1、2、3、...n的概率均為1/n，要求復(fù)雜度最低。

3.有10個(gè)文件，每個(gè)文件1G，

每個(gè)文件的每一行都存放的是用戶的query，每個(gè)文件的query都可能重復(fù)。

要求按照query的頻度排序.85.又見字符串的問題

1.給出一個(gè)函數(shù)來復(fù)制兩個(gè)字符串A和B。

字符串A的后幾個(gè)字節(jié)和字符串B的前幾個(gè)字節(jié)重疊。

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

2.已知一個(gè)字符串，比如asderwsde,尋找其中的一個(gè)子字符串比如sde的個(gè)數(shù)，

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

86.

怎樣編寫一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹中？

分析:本題考察二叉搜索樹的建樹方法，簡單的遞歸結(jié)構(gòu)。

關(guān)于樹的算法設(shè)計(jì)一定要聯(lián)想到遞歸，因?yàn)闃浔旧砭褪沁f歸的定義。而，學(xué)會(huì)把遞歸改稱非遞歸也是一種必要的技術(shù)。

畢竟，遞歸會(huì)造成棧溢出，關(guān)于系統(tǒng)底層的程序中不到非不得以最好不要用。

但是對某些數(shù)學(xué)問題，就一定要學(xué)會(huì)用遞歸去解決。87.

1.大整數(shù)數(shù)相乘的問題。（這是2002年在一考研班上遇到的算法題）

2.求最大連續(xù)遞增數(shù)字串（如“ads3sl456789DF3456ld345AA”中的“456789”）

3.實(shí)現(xiàn)strstr功能，即在父串中尋找子串首次出現(xiàn)的位置。

（筆試中常讓面試者實(shí)現(xiàn)標(biāo)準(zhǔn)庫中的一些函數(shù)）

88.2005年11月金山筆試題。編碼完成下面的處理函數(shù)。

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

如原始串為：ab**cd**e*12，

處理后為*****abcde12，函數(shù)并返回值為5。（要求使用盡量少的時(shí)間和輔助空間）89.神州數(shù)碼、華為、東軟筆試題

1.2005年11月15日華為軟件研發(fā)筆試題。實(shí)現(xiàn)一單鏈表的逆轉(zhuǎn)。

2.編碼實(shí)現(xiàn)字符串轉(zhuǎn)整型的函數(shù)（實(shí)現(xiàn)函數(shù)atoi的功能），據(jù)說是神州數(shù)碼筆試題。如將字符

串”+123”123,”-0123”-123,“123CS45”123,“123.45CS”123,“CS123.45”0

3.快速排序（東軟喜歡考類似的算法填空題，又如堆排序的算法等）

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

如字符串”abc123de4fg56”處理