數(shù)據(jù)結(jié)構(gòu)+算法面試題精選

1、數(shù)據(jù)結(jié)構(gòu)+算法面試100題-摘自CSDN作者July來源：高天的日志1 .把二元查找樹轉(zhuǎn)變成排序的雙向鏈表（樹）題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。10/614/481216轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。首先我們定義的二元查找樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：structBSTreeNode（intm_nValue;/valueofnodeBSTreeNode*m_pLeft;/leftchildofnodeBSTreeNode*m_pRight;/rightchildofnode;2 .設(shè)計(jì)包含min函數(shù)的棧（

2、棧）定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時間復(fù)雜度都是O（1）。3 .求子數(shù)組的最大和（數(shù)組）題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O（n）。例如輸入的數(shù)組為1,-2,3,10,-4,7,2,-5,和最大的子數(shù)組為3,10,-4,7,2因此輸出為該子數(shù)組的和18。4 .在二元樹中找出和為某一值的所有路徑（樹）題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入

3、整數(shù)相等的所有路徑。例如輸入整數(shù)22和如下二元樹10/512/4 7則打印出兩條路徑：10,12和10,5,7。二元樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：structBinaryTreeNode/anodeinthebinarytree（intm_nValue;/valueofnodeBinaryTreeNode*m_pLe化/leftchildofnodeBinaryTreeNode*m_pRight;/rightchildofnode;5 .查找最小的k個元素（數(shù)組）題目：輸入n個整數(shù)，輸出其中最小的k個。例如輸入1,2,3,4,5,6,7和8這8個數(shù)字，則最小的4個數(shù)字為1,2,3和4。第6題（數(shù)組）

4、騰訊面試題：給你10分鐘時間，根據(jù)上排給出十個數(shù)，在其下排填出對應(yīng)的十個數(shù)要求下排每個數(shù)都是先前上排那十個數(shù)在下排出現(xiàn)的次數(shù)。上排的十個數(shù)如下：0,1,2,3,4,5,6,7,8,9】舉一個例子，數(shù)值：0,1,2,3,4,5,6,7,8,9分配：6,2,1,0,0,0,1,0,0,00在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次.以此類推.第7題（鏈表）微軟亞院之編程判斷倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如h1,h2,判斷這倆個鏈表是否相交。為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。問題擴(kuò)展：1 .如果鏈表可能有環(huán)列？2 .如果需要求出倆個鏈表相交的第一

5、個節(jié)點(diǎn)列？第8題（算法）此貼選一些比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。1 .有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關(guān)，這兩個房間是分割開的，從一間里不能看到另一問的情況?，F(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。有什么辦法呢？2 .你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人？3 .用一種算法來顛倒一個鏈接表的順序?，F(xiàn)在在不用遞歸式的情況下做一遍。 用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點(diǎn)，但不得穿越鏈接表。 用一種算法整

6、理一個數(shù)組。你為什么選擇這種方法？ 用一種算法使通用字符串相匹配。 顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實(shí)現(xiàn)速度最快，移動最少。 找到一個子字符串。優(yōu)化速度。優(yōu)化空間。 比較兩個字符串，用O（n）時間和恒量空間。假設(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000（包才51000）之間。此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次處理，用一種算法找出重復(fù)的那個數(shù)字。如果你在運(yùn)算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎？ 不用乘法或加

7、法增加8倍?，F(xiàn)在用同樣的方法增加7倍。第9題（樹）判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true,否則返回false。例如輸入5、7、6、9、11、10、8,由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：8/610/57911因此返回true。如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。第10題（字符串）翻轉(zhuǎn)句子中單詞的順序。題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標(biāo)點(diǎn)符號和普通字母一樣處理。例如輸入“Iamast

8、udent.”,則輸出“student.aamI0第11題（樹）求二叉樹中節(jié)點(diǎn)的最大距離.如果我們把二叉樹看成一個圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義“距離”為兩節(jié)點(diǎn)之間邊的個數(shù)。寫一個程序，求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點(diǎn)之間的距離。第12題（語法）題目：求1+2+,+n,要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。第13題（鏈表）：題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)。鏈表的倒數(shù)第0個結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下：structListNodeintm_nKey;ListNode*m_

9、pNext;一第14題（數(shù)組）：題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求時間復(fù)雜度是O（n）。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15,因此輸出4和11。第15題（樹）：題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。例如輸入：8/610/57911輸出：8/106/11975定義二元查找樹的結(jié)點(diǎn)為：structBSTreeNode/anodeintheb

10、inarysearchtree（BST）（intm_nValue;/valueofnodeBSTreeNode*m_pLeft;/leftchildofnodeBSTreeNode*m_pRight;/rightchildofnode;一第16題（樹）：題目（微軟）：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點(diǎn)，同一層中按照從左往右的順序打印。例如輸入8/610/57911輸出861057911。第17題（字符串）：題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff,則輸出bo分析：這道題是2006年google的一道筆試題。第18題（數(shù)組）：題目：n個數(shù)字（0,1,n-

11、1）形成一個圓圈，從數(shù)字0開始，每次從這個圓圈中刪除第m個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。m個數(shù)字當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第求出在這個圓圈中剩下的最后一個數(shù)字。July:我想，這個題目，不少人已經(jīng)見識過了第19題(數(shù)組、遞歸)：題目：定義Fibonacci數(shù)列如下：/0n=0f(n)=1n=1/f(n-1)+f(n-2)n=2輸入n,用最快的方法求該數(shù)列的第n項(xiàng)。分析：在很多C語言教科書中講到遞歸函數(shù)的時候，者B會用Fibonacci作為例子。因此很多程序員對這道題的遞歸解法非常熟悉，但.呵呵，你知道的。第20題(字符串)：題目：輸入一個表示整

12、數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。例如輸入字符串"345”,則輸出整數(shù)345。第21題(數(shù)組)2010年中興面試題編程求解：輸入兩個整數(shù)n和m,從數(shù)列1,2,3n中隨意取幾個數(shù)，使其和等于m,要求將其中所有的可能組合列出來.第22題(推理)：有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A說不知道，B說不知道，C說不知道，然后A說知道了。請教如何推理，A是怎么知道的。如果用程序，又怎么實(shí)現(xiàn)呢？第23題(算法)：用最簡單，最快速的方法計(jì)算出下面這個圓形

13、是否和正方形相交。"3D坐標(biāo)系原點(diǎn)(0.0,0.0,0.0)圓形：半徑r=3.0圓心o=(*.*,0.0,*.*)正方形：4個角坐標(biāo)；1:(*.*,0.0,*.*)2:(*.*,0.0,*.*)3:（*.*,0.0,*.*）4:（*.*,0.0,*.*）第24題（鏈表）：鏈表操作，單鏈表就地逆置，第25題（字符串）：寫一個函數(shù)，它的原形是intcontinumax（char*outputstr,char*intputstr）功能：在字符串中找出連續(xù)最長的數(shù)字用，并把這個用的長度返回，并把這個最長數(shù)字用付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。例如："abcd12345

14、ed125ss123456789”的首地址傳給intputstr后，函數(shù)將返回9,outputstr所指的值為12345678926 .左旋轉(zhuǎn)字符串（字符串）題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實(shí)現(xiàn)字符用左旋轉(zhuǎn)的函數(shù)。要求時間對長度為n的字符串操作的復(fù)雜度為O（n）,輔助內(nèi)存為0（1）。27 .跳臺階問題（遞歸）題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個

15、這道題作為面試題或者筆試題。28 .整數(shù)的二進(jìn)制表示中1的個數(shù)（運(yùn)算）題目：輸入一個整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個1。例如輸入10,由于其二進(jìn)制表示為1010,有兩個1,因此輸出2。分析：這是一道很基本的考查位運(yùn)算的面試題。包括微軟在內(nèi)的很多公司都曾采用過這道題。29 .棧的push、pop序列（棧）題目：輸入兩個整數(shù)序列。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應(yīng)的pop順序。為了簡單起見，我們假設(shè)push序列的任意兩個整數(shù)都是不相等的。比如輸入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一個pop系歹!J。因?yàn)榭梢杂腥缦碌膒ush和pop

16、序列：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序歹限30 .在從1到n的正數(shù)中1出現(xiàn)的次數(shù)（數(shù)組）題目：輸入一個整數(shù)n,求從1到n這n個整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。例如輸入12,從1到12這些整數(shù)中包含1的數(shù)字有1,10,11和12,1一共出現(xiàn)了5次。分析：這是一道廣為流傳的google面試題。31 .華為面試題（搜索）：一類似于蜂窩的結(jié)構(gòu)的圖，進(jìn)行搜索最短路徑（要求5分鐘）32 .（數(shù)組、規(guī)劃）有兩個序列a,b,大

17、小都為n,序列元素的值任意整數(shù)，無序；要求：通過交換a,b中的元素，使序列a元素的和與序列b元素的和之間的差最小。例如：vara=100,99,98,1,2,3;varb=1,2,3,4,5,40;33 .（字符串）實(shí)現(xiàn)一個挺高級的字符匹配算法:給一審很長字符用，要求找到符合要求的字符串，例如目的用：123*3*2,12*3這些都要找出來其實(shí)就是類似一些和諧系統(tǒng)34 .（隊(duì)列）實(shí)現(xiàn)一個隊(duì)列。隊(duì)列的應(yīng)用場景為：一個生產(chǎn)者線程將int類型的數(shù)入列，一個消費(fèi)者線程將int類型的數(shù)出列35 .（矩陣）求一個矩陣中最大的二維矩陣（元素和最大）.如：1 20342 345111530中最大的是：4 55

18、3要求：（1）寫出算法;（2）分析時間復(fù)雜度;（3）用C寫出關(guān)鍵代碼第36題-40題（有些題目搜集于CSDNt的網(wǎng)友，已標(biāo)明）：36.引用自網(wǎng)友：longzuo（運(yùn)算）谷歌筆試：n支隊(duì)伍比賽，分別編號為0,1,2。n-1,已知它們之間的實(shí)力對比關(guān)系，存儲在一個二維數(shù)組wnn中，wij的值代表編號為i,j的隊(duì)伍中更強(qiáng)的一支。所以wij=i或者j,現(xiàn)在給出它們的出場順序，并存儲在數(shù)組ordern中,比如ordern=4,3,5,8,1.，那么第一輪比賽就是4對3,5對8 。.勝者晉級，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4

19、對5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w,一維數(shù)組order和用于輸出比賽名次的數(shù)組resultn,求出result。37 .（字符串）有n個長為m+1的字符串，如果某個字符串的最后m個字符與某個字符串的前m個字符匹配，則兩個字符串可以聯(lián)接，問這n個字符串最多可以連成一個多長的字符串，如果出現(xiàn)循環(huán)，則返回錯誤。38 .（算法）百度面試：1 .用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用x次天平，最多可以從y個小球中找出較輕的那個，求y與x的關(guān)系式。2 .有一個很大很大的輸入流，大到?jīng)]有存儲器可以將其存儲下來，而且只輸入一次，如何從這個輸入流中隨機(jī)取得m個記錄。3 .

20、大量的URL字符串，如何從中去除重復(fù)的，優(yōu)化時間空間復(fù)雜度39 .（樹、圖、算法）網(wǎng)易有道筆試：（1） .求一個二叉樹中任意兩個節(jié)點(diǎn)間的最大距離，兩個節(jié)點(diǎn)的距離的定義是這兩個節(jié)點(diǎn)間邊的個數(shù)，比如某個孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1,和相鄰兄弟節(jié)點(diǎn)間的距離是2,優(yōu)化時間空間復(fù)雜度。（2） .求一個有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。40 .百度研發(fā)筆試題（棧、算法）引用自：zp1553348771）設(shè)計(jì)一個棧結(jié)構(gòu)，滿足一下條件：min,push,pop操作的時間復(fù)雜度為0（1）2）一用首尾相連的珠子（m個），有N種顏色（N<=10）,設(shè)計(jì)一個

21、算法，取出其中一段，要求包含所有N中顏色，并使長度最短。并分析時間復(fù)雜度與空間復(fù)雜度。3）設(shè)計(jì)一個系統(tǒng)處理詞語搭配問題，比如說中國和人民可以搭配，則中國人民人民中國都有效。要求：* 系統(tǒng)每秒的查詢數(shù)量可能上千次；* 詞語的數(shù)量級為10W* 每個詞至多可以與1WS司搭配當(dāng)用戶輸入中國人民的時候，要求返回與這個搭配詞組相關(guān)的信息。41 .求固晶機(jī)的晶元查找程序（匹配、算法）晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤,照相機(jī)每次這能匹配一個晶元，如匹配過，則拾取該晶元，若匹配不過，照相機(jī)則按測好的晶元間距移到下一個位置。求遍歷晶元盤的算法求思路。42 .請修改append函數(shù)，利

22、用這個函數(shù)實(shí)現(xiàn)（鏈表）：兩個非降序鏈表的并集，1->2->3和2->3->5并為1->2->3->5另外只能輸出結(jié)果，不能修改兩個鏈表的數(shù)據(jù)。43 .遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷。44 .騰訊面試題（算法）：1 .設(shè)計(jì)一個魔方（六面）的程序。2 .有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。請用5分鐘時間，找出重復(fù)出現(xiàn)最多的前10條。3 .收藏了1萬條url,現(xiàn)在給你一條url,如何找出相似的url。（面試官不解釋何為相似）45 .雅虎（運(yùn)算、矩陣）：1 .對于一個整數(shù)矩陣，存在一種運(yùn)算，對矩陣中任意元素加一時，需要其相

23、鄰（上下左右）某一個元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個全零矩陣經(jīng)過上述運(yùn)算得到。2 .一個整數(shù)數(shù)組，長度為n,將其分為m份，使各份的和相等，求m的最大值比如3,2,4,3,6可以分成3,2,4,3,6m=1;3,62,4,3m=23,32,46m=3所以m的最大值為346 .搜狐（運(yùn)算）：四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（）47 .創(chuàng)新工場（算法）：求一個數(shù)組的最長遞減子序列比如9,4,3,2,5,4,3,2的最長遞減子序列為9,5,4,3,248 .微軟（運(yùn)算）：一個數(shù)組是由一個遞減數(shù)列左移若干位形成的，比如4,3,2,1,6,5是由6,5

24、,4,3,2,1左移兩位形成的，在這種數(shù)組中查找某一個數(shù)。49 .一道看上去很嚇人的算法面試題（排序、算法）：如何對n個數(shù)進(jìn)行排序，要求時間復(fù)雜度O（n）,空間復(fù)雜度0（1）50 .網(wǎng)易有道筆試（sorry,與第39題重復(fù)）：1 .求一個二叉樹中任意兩個節(jié)點(diǎn)間的最大距離，兩個節(jié)點(diǎn)的距離的定義是這兩個節(jié)點(diǎn)間邊的個數(shù)，比如某個孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1,和相鄰兄弟節(jié)點(diǎn)間的距離是2,優(yōu)化時間空間復(fù)雜度。2 .求一個有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。51 .和為n連續(xù)正數(shù)序列（數(shù)組）題目：輸入一個正數(shù)n,輸出所有和為n連續(xù)正數(shù)序列。例如輸入15,

25、由于1+2+3+4+5=4+5+6=7+8=15所以輸出3個連續(xù)序列1-5、4-6和7-80分析：這是網(wǎng)易的一道面試題。52 .二元樹的深度（樹）。題目：輸入一棵二元樹的根結(jié)點(diǎn)，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度。例如：輸入二元樹：10/614/41216輸出該樹的深度3。二元樹的結(jié)點(diǎn)定義如下：structSBinaryTreeNode/anodeofthebinarytree(intm_nValue;/valueofnodeSBinaryTreeNode*m_pLeft;/leftchildofnodeSBinaryTree

26、Node*m_pRight;/rightchildofnode;一分析：這道題本質(zhì)上還是考查二元樹的遍歷。53 .字符串的排列(字符串)。題目：輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則輸出由字符a、b、c所能排列出來的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。分析：這是一道很好的考查對遞歸理解的編程題，因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。54 .調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面(數(shù)組)。題目：輸入一個整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分。要求時間復(fù)雜度為O(n)。55 .(語法)

27、題目：類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)對一個對象進(jìn)行賦值時發(fā)生異常，對象的狀態(tài)不能改變。56 .最長公共字串(算法、字符串)題目：如果字符申一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符用一稱之為字

28、符串二的子用。注意，并不要求子用(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子用，并打印出最長公共子用。例如：輸入兩個字符串BDCAB相ABCBDAB字符串BCB符口BDAEB是是它們的最長公共子用，則輸出它們的長度4,并打印任意一個子用。分析：求最長公共子用(LongestCommonSubsequence,LCS>)是一道非常經(jīng)典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。57 .用倆個棧實(shí)現(xiàn)隊(duì)列(棧、隊(duì)列)。題目：某隊(duì)列的聲明如下：template<typenameT>classCQu

29、euepublic:CQueue()CQueue()voidappendTail(constT&node);/appendaelementtotailvoiddeleteHead();removeaelementfromheadprivate:T>m_stack1;T>m_stack2;分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個棧。因此這道題實(shí)質(zhì)上是要求我們用兩個棧來實(shí)現(xiàn)一個隊(duì)列。相信大家對棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列

30、的頭部刪除元素。58 .從尾到頭輸出鏈表(鏈表)。題目：輸入一個鏈表的頭結(jié)點(diǎn)，從尾到頭反過來輸出每個結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：structListNodeintm_nKey;ListNode*m_pNext;)；一分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。59 .不能被繼承的類(語法)。題目：用C+般計(jì)一個不能被繼承的類。分析：這是Adobe公司2007年校園招聘的最新筆試題。這道題除了考察應(yīng)聘者的C+叫本功底外，還能考察反應(yīng)能力，是一道很好的題目。60 .在O(1)時間內(nèi)刪除鏈表結(jié)點(diǎn)(鏈表、算法)。題目：給定鏈表的頭指針和一個結(jié)點(diǎn)指針，在O(1)時

31、間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：structListNodeintm_nKey;ListNode*m_pNext;);一函數(shù)的聲明如下：voidDeleteNode(ListNode*pListHead,ListNode*pToBeDeleted);分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，更重要的是，還能考察我們對時間復(fù)雜度的理解。61 .找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字(數(shù)組)題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n),空間復(fù)雜度是O(1)。分析：這是一道很

32、新穎的關(guān)于位運(yùn)算的面試題。62 .找出鏈表的第一個公共結(jié)點(diǎn)(鏈表)。題目：兩個單向鏈表，找出它們的第一個公共結(jié)點(diǎn)鏈表的結(jié)點(diǎn)定義為：structListNodeintm_nKey;ListNode*m_pNext;）；一分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目,因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。63 .在字符串中刪除特定的字符（字符串）。題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入“Theyarestudents."和“aeiou”,則刪除之后的第一個字符串變成"Thyrstdnts.”。分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟Α?4 .尋找丑數(shù)（運(yùn)算）。題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（UglyNumber）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第1500個丑數(shù)。分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。65 .輸出1到最大的N位