最新數(shù)據(jù)結(jié)構(gòu)+算法面試100題資料

1、精品文檔數(shù)據(jù)結(jié)構(gòu)+算法面試100題摘自CSDN,作者Julyl.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 (樹)題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。 要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。10/ /6 14/ / / /4 8 12 16轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right ch

2、ild of node;2. 設(shè)計(jì)包含 min 函數(shù)的棧(棧) 定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè) min 函數(shù)，能夠得到棧的最小元素。 要求函數(shù) min、push 以及 pop 的時(shí)間復(fù)雜度都是 O(1)。參見 C:UsersAdministratorDesktopdemoStack分析：min時(shí)間復(fù)雜度要達(dá)到0(1),需要我們?cè)跅Ｖ写鎯?chǔ)最小元素3. 求子數(shù)組的最大和(數(shù)組)題目： 輸入一個(gè)整形數(shù)組,數(shù)組里有正數(shù)也有負(fù)數(shù)。 數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組,每個(gè)子數(shù)組都有一個(gè)和。 求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為0(n)。例如輸入的數(shù)組為 1, -2, 3, 10, -4, 7

3、, 2, -5,和最大的子數(shù)組為 3, 10, -4, 7, 2, 因此輸出為該子數(shù)組的和18。分析：根據(jù) dp 思想#include <stdio.h>#define N 8int main()int i, aN = 1, -2, 3, 10, -4, 7, 2, -5;int fromN, resultN, max;max = 0;from0 = 0;result0 = a0;for (i = 1; i < N; +i)if (resulti - 1 > 0)fromi = fromi - 1;resulti = ai + resulti - 1;elsefromi

4、 = i;resulti = ai;if (resulti > resultmax)max = i;printf("%d->%d: %dn", frommax, max, resultmax);return 0;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)定義為：struct Binar

5、yTreeNode / a node in the binary treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of nodeBinaryTreeNode *m_pRight; / right child of node;5. 查找最小的 k 個(gè)元素（數(shù)組） 題目：輸入 n 個(gè)整數(shù)，輸出其中最小的 k 個(gè)。例如輸入 1，2，3，4，5，6，7和 8這8個(gè)數(shù)字，則最小的 4個(gè)數(shù)字為 1，2，3和 4。第 6 題（數(shù)組）騰訊面試題：給你 10 分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù) 要求

6、下排每個(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,00 在下排出現(xiàn)了 6 次， 1 在下排出現(xiàn)了 2 次，2 在下排出現(xiàn)了 1 次， 3 在下排出現(xiàn)了 0 次 以此類推 .第 7 題（鏈表）微軟亞院之編程判斷倆個(gè)鏈表是否相交給出倆個(gè)單向鏈表的頭指針，比如hl, h2,判斷這倆個(gè)鏈表是否相交。為了簡(jiǎn)化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。問題擴(kuò)展：1. 如果鏈表可能有環(huán)列 ?2. 如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?第 8 題（算法

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

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

9、用這種方式的算法嗎 ?不用乘法或加法增加 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 7 9 11 因此返回 true 。 如果輸入 7、4、 6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。第 10 題（字符串） 翻轉(zhuǎn)句子中單詞的順序。題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞

10、內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡(jiǎn)單起見，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。例如輸入 “ I am a student. ”,則輸出"student. a am I ”。第 11 題（樹） 求二叉樹中節(jié)點(diǎn)的最大距離 .如果我們把二叉樹看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的， 我們姑且定義 "距離 "為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫一個(gè)程序， 求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。第 12 題（語法）題目：求1+2+n,要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?BQ。第 13 題（鏈表）：題目

11、： 輸入一個(gè)單向鏈表， 輸出該鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn)。 鏈表的倒數(shù)第 0 個(gè)結(jié)點(diǎn)為鏈表的 尾指針。鏈表結(jié)點(diǎn)定義如下：struct ListNodeint m_nKey;ListNode* m_pNext;第 14 題（數(shù)組）：題目：輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字， 在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是 0（n）。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。 例如輸入數(shù)組 1 、 2、 4、 7、 11 、 15 和數(shù)字 15。由于 4+11=15，因此輸出 4 和 11 。第 15 題（樹）：題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，

12、 即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。 用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。例如輸入：8/ /6 10/ /5 7 9 11輸出：8/ /10 6/ /11 9 7 5定義二元查找樹的結(jié)點(diǎn)為：struct BSTreeNode / a node in the binary search tree (BST) int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;第 16 題（樹）： 題目（微軟） ：

13、 輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。 例如輸入8/ /6 10/ / / /5 7 9 11輸出 8 6 10 5 7 9 11。abaccdeff ，則輸出 b。第 17 題（字符串） ： 題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入 分析：這道題是 2006 年 google 的一道筆試題。第 18 題（數(shù)組）：題目 n個(gè)數(shù)字（0,1,n-1）形成一個(gè)圓圈，從數(shù)字0開始, 每次從這個(gè)圓圈中刪除第 m 個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè) 數(shù)字）。當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第 m 個(gè)數(shù)字。 求出在這個(gè)

14、圓圈中剩下的最后一個(gè)數(shù)字。July:我想，這個(gè)題目，不少人已經(jīng)見識(shí)過了。第 19 題（數(shù)組、遞歸） ： 題目：定義 Fibonacci 數(shù)列如下：/ 0 n=0 f(n)= 1 n=1/ f(n-1)+f(n-2) n=2輸入n,用最快的方法求該數(shù)列的第n項(xiàng)。分析：在很多C語言教科書中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fib on acci作為例子。因此很多程序員對(duì)這道題的遞歸解法非常熟悉,但 呵呵,你知道的。 。第 20 題（字符串） ： 題目：輸入一個(gè)表示整數(shù)的字符串,把該字符串轉(zhuǎn)換成整數(shù)并輸出。 例如輸入字符串 "345" ,則輸出整數(shù) 345。第 21 題（數(shù)組）2010

15、年中興面試題編程求解：輸入兩個(gè)整數(shù) n和m，從數(shù)列1，2，3n中隨意取幾個(gè)數(shù) 使其和等于 m ,要求將其中所有的可能組合列出來.第 22 題（推理） ：有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B C三人額頭上貼任意兩張牌，A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A說不知道，B說不知道，C說不知道，然后 A說知道了。 請(qǐng)教如何推理， A 是怎么知道的。如果用程序，又怎么實(shí)現(xiàn)呢？第 23 題(算法)： 用最簡(jiǎn)單，最快速的方法計(jì)算出下面這個(gè)圓形是否和正方形相交。 3D 坐標(biāo)系 原點(diǎn) (0.0,0.0,0.0)圓形:半徑 r = 3.0

16、圓心 o = (*.*, 0.0, *.*)正方形 : 4 個(gè)角坐標(biāo) ;(*.*, 0.0, *.*) 2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)(*.*, 0.0, *.*)第 24 題(鏈表)： 鏈表操作，單鏈表就地逆置，第 25 題(字符串) ：寫一個(gè)函數(shù) ,它的原形是 int continumax(char *outputstr,char *intputstr) 功能：在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回， 并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù) outputstr 所指內(nèi)存。例如： "abcd12345ed125ss12345678

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

18、視算法的公司 都曾先后選用過個(gè)這道題作為面試題或者筆試題。28. 整數(shù)的二進(jìn)制表示中 1 的個(gè)數(shù)（運(yùn)算） 題目：輸入一個(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è)序列有沒有可能是對(duì)應(yīng)的 pop 順序。 為了簡(jiǎn)單起見，我們假設(shè) push 序列的任意兩個(gè)整數(shù)都是不相等的。比如輸入的 push 序列是 1、2、 3、4、5，那么

19、 4、5、3、 2、1 就有可能是一個(gè) pop 系列。 因?yàn)榭梢杂腥缦碌?push 和 pop 序列：push 1， push 2，push 3 ， push 4， pop ，push 5，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ù)組）題目：輸入一個(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

20、次。 分析：這是一道廣為流傳的 google 面試題。31. 華為面試題（搜索） ：一類似于蜂窩的結(jié)構(gòu)的圖,進(jìn)行搜索最短路徑（要求 5分鐘）32. （數(shù)組、規(guī)劃）有兩個(gè)序列a,b，大小都為n,序列元素的值任意整數(shù)，無序；要求：通過交換 a,b中的元素，使序列a元素的和與序列b元素的和之間的差最小。 例如 :var a=100,99,98,1,2, 3;var b=1, 2, 3, 4,5,40;33.（字符串） 實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法： 給一串很長(zhǎng)字符串，要求找到符合要求的字符串，例如目的串： 123*3*2 ,12*3這些都要找出來其實(shí)就是類似一些和諧系統(tǒng)。34.（隊(duì)列）實(shí)現(xiàn)一個(gè)隊(duì)列。

21、隊(duì)列的應(yīng)用場(chǎng)景為：一個(gè)生產(chǎn)者線程將 int 類型的數(shù)入列，一個(gè)消費(fèi)者線程將 int 類型的數(shù)出列35.（矩陣） 求一個(gè)矩陣中最大的二維矩陣（元素和最大 ）.如 :1 2 0 3 42 3 4 5 11 1 5 3 0 中最大的是 :4 55 3要求：（1）寫出算法；（2）分析時(shí)間復(fù)雜度；（3）用C寫出關(guān)鍵代碼第36題-40題（有些題目搜集于CSDN上的網(wǎng)友，已標(biāo)明）：36.引用自網(wǎng)友： longzuo （運(yùn)算） 谷歌筆試：n支隊(duì)伍比賽，分別編號(hào)為0, 1, 2。n-1，已知它們之間的實(shí)力對(duì)比關(guān)系，存儲(chǔ)在一個(gè)二維數(shù)組 wnn 中， wij 的值代表編號(hào)為 i， j 的隊(duì)伍中更強(qiáng)的一支。所以wij

22、=i或者j，現(xiàn)在給出它們的出場(chǎng)順序，并存儲(chǔ)在數(shù)組ordern中，比如 ordern = 4,3,5,8,1 ,那么第一輪比賽就是 4對(duì)3,5對(duì)8。 勝者晉級(jí),敗者淘汰,同一輪淘汰的所有隊(duì)伍排名不再細(xì)分,即可以隨便排, 下一輪由上一輪的勝者按照順序,再依次兩兩比,比如可能是 4對(duì) 5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order和用于輸出比賽名次的數(shù)組resultn，求出 result。37. （字符串） 有 n 個(gè)長(zhǎng)為 m+1 的字符串，如果某個(gè)字符串的最后 m個(gè)字符與某個(gè)字符串的前 m個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接, 問這 n 個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循

23、環(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）. 求一

24、個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊， 有向圖不再連通，描述算法。40. 百度研發(fā)筆試題（棧、算法）引用自： zp1553348771）設(shè)計(jì)一個(gè)棧結(jié)構(gòu)，滿足一下條件：min， push， pop 操作的時(shí)間復(fù)雜度為 O（1）。2）串首尾相連的珠子（m個(gè)），有N種顏色（N<=10）,設(shè)計(jì)一個(gè)算法，取出其中一段，要求包含所有N中顏色，并使長(zhǎng)度最短。并分析時(shí)間復(fù)雜度與空間復(fù)雜度。3）設(shè)計(jì)一個(gè)系統(tǒng)處理詞語搭配問題，比如說中國(guó) 和人民可以搭配，則中國(guó)人民 人民中國(guó)都有效。要求：*系統(tǒng)每秒的查詢數(shù)量可能上千次；* 詞語的數(shù)量級(jí)為 10W ；* 每個(gè)詞至多可以與 1W 個(gè)詞搭

25、配當(dāng)用戶輸入中國(guó)人民的時(shí)候，要求返回與這個(gè)搭配詞組相關(guān)的信息。41. 求固晶機(jī)的晶元查找程序（匹配、算法） 晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤，照相機(jī)每次這能匹配一個(gè)晶元，如匹配過，則拾取該晶元， 若匹配不過，照相機(jī)則按測(cè)好的晶元間距移到下一個(gè)位置。 求遍歷晶元盤的算法 求思路。42. 請(qǐng)修改 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.騰

26、訊面試題（算法） ：1.設(shè)計(jì)一個(gè)魔方（六面）的程序。2.有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。 請(qǐng)用 5 分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前 10 條。3收藏了 1萬條url，現(xiàn)在給你一條url，如何找出相似的 url。（面試官不解釋何為相似）45 .雅虎（運(yùn)算、矩陣） ：1對(duì)于一個(gè)整數(shù)矩陣，存在一種運(yùn)算，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）某一個(gè)元素也加一， 現(xiàn)給出一正數(shù)矩陣， 判斷其是否能夠由一個(gè)全零矩陣經(jīng)過上述運(yùn)算得到。2一個(gè)整數(shù)數(shù)組，長(zhǎng)度為 n,將其分為m份，使各份的和相等，求 m的最大值比如 3， 2， 4， 3， 6 可以分成 3， 2， 4， 3，

27、 6 m=1;3,62,4,3 m=23,32,46 m=3 所以 m 的最大值為 346. 搜狐（運(yùn)算）： 四對(duì)括號(hào)可以有多少種匹配排列方式？比如兩對(duì)括號(hào)可以有兩種： （）（）和（）47. 創(chuàng)新工場(chǎng)（算法） ：求一個(gè)數(shù)組的最長(zhǎng)遞減子序列比如 9，4，3，2，5，4，3，2的最長(zhǎng)遞減子序列為 9，5，4，3，248. 微軟（運(yùn)算）：一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如4，3， 2，1，6，5是由 6，5，4，3，2， 1左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。49. 一道看上去很嚇人的算法面試題（排序、算法）：如何對(duì)n個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度0（n）,空間復(fù)雜度0（1）50.網(wǎng)

28、易有道筆試（sorry，與第39題重復(fù)）：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)的邊,有向圖不再連通,描述算法。51. 和為 n 連續(xù)正數(shù)序列（數(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)易的一道面試題。52. 二元樹的深度（樹）

29、題目：輸入一棵二元樹的根結(jié)點(diǎn)，求該樹的深度。形成樹的一條路徑， 最長(zhǎng)路徑的長(zhǎng)度為從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)） 樹的深度。例如：輸入二元樹：10/ /6 14/ / /4 12 16輸出該樹的深度 3。二元樹的結(jié)點(diǎn)定義如下：struct SBinaryTreeNode / a node of the binary treeintm_nValue; / value of nodeSBinaryTreeNode *m_pLeft; / left child of node SBinaryTreeNode *m_pRight; / right child of node ;分析：這道

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

31、MyStringpublic:CMyString(char* pData = NULL);CMyString(const CMyString& str); CMyString(void);CMyString& operator = (const CMyString& str);private:char* m_pData;請(qǐng)實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)， 要求異常安全， 即當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行賦值時(shí)發(fā)生異常， 對(duì) 象的狀態(tài)不能改變。56. 最長(zhǎng)公共字串（算法、字符串） 。 題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中， 則字符串一稱之為字符串二的子串

32、。 注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。 請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。例如：輸入兩個(gè)字符串 BDCABA和ABCBDAB字符串BCBA和BDAB都是是它們的最長(zhǎng)公共 子串， 則輸出它們的長(zhǎng)度 4，并打印任意一個(gè)子串。分析：求最長(zhǎng)公共子串（Lon gest Com mon Subseque nee, LCS是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題， 因此一些重視算法的公司像 MicroStrategy 都把它當(dāng)作面試題。57. 用倆個(gè)棧實(shí)現(xiàn)隊(duì)列（棧、隊(duì)列） 。 題目：某隊(duì)列的聲明如下： template<typename T>

33、; elass CQueuepublic:CQueue() CQueue() void appendTail(const T& node); / append a element to tail void deleteHead(); / remove a element from headprivate:T> m_stack1;T> m_stack2; ;分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。 相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器， 因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行

34、；隊(duì)列是一種先入先出的數(shù)據(jù)容器， 我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。58. 從尾到頭輸出鏈表（鏈表） 。題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過來輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下： struct ListNodeint m_nKey;ListNode* m_pNext;分析：這是一道很有意思的面試題。 該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。59. 不能被繼承的類（語法） 。題目：用C+設(shè)計(jì)一個(gè)不能被繼承的類。分析：這是 Adobe 公司 2007 年校園招聘的最新筆試題。這道題除了考察應(yīng)聘者的 C+基本功底外，還能考察反應(yīng)能力，是一道很好的題目。60.

35、在O (1)時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)(鏈表、算法) 。題目 給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在0(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下:struct ListNodeint m_nKey;ListNode* m_pNext;函數(shù)的聲明如下:void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);分析:這是一道廣為流傳的 Google 面試題，能有效考察我們的編程基本功，還能考察我們 的反應(yīng)速度，更重要的是，還能考察我們對(duì)時(shí)間復(fù)雜度的理解。61. 找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字(數(shù)組) 題目:一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字

36、都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是0(n),空間復(fù)雜度是 0(1)。分析:這是一道很新穎的關(guān)于位運(yùn)算的面試題。62. 找出鏈表的第一個(gè)公共結(jié)點(diǎn)(鏈表)。題目:兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。鏈表的結(jié)點(diǎn)定義為:struct ListNodeint m_nKey;ListNode* m_pNext;分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。63. 在字符串中刪除特定的字符（字符串） 。 題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入” They are students

37、. ”和” aeiou ”，則刪除之后的第一個(gè)字符串變成” Thy r stdnts.”。分析： 這是一道微軟面試題。 在微軟的常見面試題中， 與字符串相關(guān)的題目占了很大的一部 分， 因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟Α?4. 尋找丑數(shù)（運(yùn)算） 。題目：我們把只包含因子 2、 3 和 5 的數(shù)稱作丑數(shù)（ Ugly Number ）。例如 6、 8 都是丑數(shù)， 但 14 不是，因?yàn)樗蜃?7 。習(xí)慣上我們把 1 當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第 1500 個(gè)丑數(shù)。分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google 曾經(jīng)采用過這道題。65. 輸出 1 到最大的 N

38、位數(shù)（運(yùn)算）題目：輸入數(shù)字n,按順序輸出從1最大的n位10進(jìn)制數(shù)。比如輸入 3,則輸出 1 、 2、3 一直到最大的 3 位數(shù)即 999。 分析：這是一道很有意思的題目?？雌饋砗芎?jiǎn)單,其實(shí)里面卻有不少的玄機(jī)。66. 顛倒棧（棧） 。題目：用遞歸顛倒一個(gè)棧。例如輸入棧1, 2, 3, 4, 5， 1 在棧頂。顛倒之后的棧為 5, 4, 3, 2, 1，5 處在棧頂。67. 倆個(gè)閑玩娛樂（運(yùn)算） 。1. 撲克牌的順子 從撲克牌中隨機(jī)抽 5 張牌，判斷是不是一個(gè)順子，即這 5 張牌是不是連續(xù)的。2-10為數(shù)字本身，A為1 , J為11, Q為12, K為13,而大小王可以看成任意數(shù)字。2.n 個(gè)骰子

39、的點(diǎn)數(shù)。把n個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n,打印出S的所有可能的值出現(xiàn)的概率。68. 把數(shù)組排成最小的數(shù)（數(shù)組、算法） 。題目： 輸入一個(gè)正整數(shù)數(shù)組, 將它們連接起來排成一個(gè)數(shù),輸出能排出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組 32, 321,則輸出這兩個(gè)能排成的最小數(shù)字32132。請(qǐng)給出解決問題的算法,并證明該算法。分析：這是 09 年 6 月份百度的一道面試題, 從這道題我們可以看出百度對(duì)應(yīng)聘者在算法方面有很高的要求。69. 旋轉(zhuǎn)數(shù)組中的最小元素（數(shù)組、算法） 。題目： 把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾, 我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè) 排好序的數(shù)組的一個(gè)

40、旋轉(zhuǎn),輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組3, 4, 5, 1, 2為1, 2, 3, 4, 5的一個(gè)旋轉(zhuǎn),該數(shù)組的最小值為 1 。分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次,就能找出最小的元素, 時(shí)間復(fù)雜度顯然是 0（N）。但這個(gè)思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解 法。70. 給出一個(gè)函數(shù)來輸出一個(gè)字符串的所有排列（經(jīng)典字符串問題） 。ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)， 還有逆序生成排列和一些不需要遞歸生成排列的方法。印象中Knuth的TAOCP第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué) 功底，也需要一定

41、的靈感，有興趣最好看看。71. 數(shù)值的整數(shù)次方（數(shù)字、運(yùn)算） 。題目：實(shí)現(xiàn)函數(shù) double Power（double base, int exponent） ，求 base 的 exponent 次方。 不需要考慮溢出。30 秒寫出如下的代碼：分析：這是一道看起來很簡(jiǎn)單的問題。 可能有不少的人在看到題目后 double Power（double base, int exponent）double result= 1.0;for(int i = 1; i<= exponent; +i)result*= base;return result;72.（語法） 題目：設(shè)計(jì)一個(gè)類，我們只能生成該

42、類的一個(gè)實(shí)例。 分析：只能生成一個(gè)實(shí)例的類是實(shí)現(xiàn)了 Singleton 模式的類型。73. 對(duì)稱字符串的最大長(zhǎng)度（字符串） 。題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串"google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是"goog”，因此輸出4。分析：可能很多人都寫過判斷一個(gè)字符串是不是對(duì)稱的函數(shù)， 這個(gè)題目可以看成是該函數(shù)的 加強(qiáng)版。74. 數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字（數(shù)組）題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長(zhǎng)度的一半，找出這個(gè)數(shù)字。分析：這是一道廣為流傳的面試題，包括百度、微軟和 Google 在內(nèi)的多家公司都 曾經(jīng)采用過

43、這個(gè)題目。要幾十分鐘的時(shí)間里很好地解答這道題， 除了較好的編程能力之外，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力。75. 二叉樹兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)（樹）題目：二叉樹的結(jié)點(diǎn)定義如下：struct TreeNodeint m_nvalue;TreeNode* m_pLeft;TreeNode* m_pRight;這個(gè)問題至少有兩個(gè)輸入二叉樹中的兩個(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è)問題。 變種。76. 復(fù)雜鏈表的復(fù)制（鏈表、算法）題目：有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè) m_pNext 指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibl

44、ing指向鏈表中的任一結(jié)點(diǎn)或者NULL。其結(jié)點(diǎn)的C+定義如下:struct ComplexNodeint m_nValue;ComplexNode* m_pNext;ComplexNode* m_pSibling;下圖是一個(gè)含有 5 個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。圖中實(shí)線箭頭表示 m_pNext 指針，虛線箭頭表示 m_pSibling 指針。為簡(jiǎn)單起見， 指向 NULL 的指針沒有畫出。請(qǐng)完成函數(shù) ComplexNode* Clone(ComplexNode* pHead) ，以復(fù)制一個(gè)復(fù)雜鏈表。 分析：在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化，這是一種很新穎的面試題。要在不到一個(gè)小時(shí)的時(shí)間里解決這種類型的題目

45、，我們需要較快的反應(yīng)能力， 對(duì)數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實(shí)的編程功底。77. 關(guān)于鏈表問題的面試題目如下(鏈表) ：1. 給定單鏈表，檢測(cè)是否有環(huán)。使用兩個(gè)指針 p1,p2 從鏈表頭開始遍歷， p1 每次前進(jìn)一步， p2 每次前進(jìn)兩步。如果 p2 到 達(dá)鏈表尾部，說明無環(huán)，否則pl、p2必然會(huì)在某個(gè)時(shí)刻相遇(p1=p2),從而檢測(cè)到鏈表中有環(huán)。2.給定兩個(gè)單鏈表 (head1, head2) ，檢測(cè)兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)。如果 head1=head2 ，那么顯然相交，直接返回 head1 。否則，分別從 head1,head2 開始遍歷兩個(gè)鏈表獲得其長(zhǎng)度 len1 與 len2

46、 ，假設(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)的話請(qǐng)返回從頭結(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)，方法為：p仁p, p2=p-> next, p-> next=NULL。此時(shí)，原單鏈表可以看作兩條單鏈表，一條從 head 開始，另一條從 p2 開始，于是運(yùn)

47、用題二的方法，我們找到它們的第一個(gè)交點(diǎn) 即為所求。4只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即 p-> next!=NULL)指針，刪除該結(jié)點(diǎn)。辦法很簡(jiǎn)單，首先是放 p 中數(shù)據(jù) ,然后將 p->next 的數(shù)據(jù) copy 入 p 中，接下來刪除 p->next 即可。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ū)別在哪里（鏈表、數(shù)組）？分析：主要在基本概念上的理解。但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能

48、就在細(xì)節(jié)上產(chǎn)生， 誰比較仔細(xì)，誰獲勝的機(jī)會(huì)就大。79. （鏈表、字符串）1. 編寫實(shí)現(xiàn)鏈表排序的一種算法。說明為什么你會(huì)選擇用這樣的方法？2. 編寫實(shí)現(xiàn)數(shù)組排序的一種算法。說明為什么你會(huì)選擇用這樣的方法？3請(qǐng)編寫能直接實(shí)現(xiàn) strstr（）函數(shù)功能的代碼。80. 阿里巴巴一道筆試題（運(yùn)算、算法）問題描述 :12 個(gè)高矮不同的人 ,排成兩排 ,每排必須是從矮到高排列 ,而且第二排比對(duì)應(yīng)的第一排的人高 問排列方式有多少種 ?這個(gè)筆試題，很YD因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深。先來幾組百度的面試題：81.第1組百度面試題1. 一個(gè)int數(shù)組，里面數(shù)據(jù)無任何限制，要求求出所有這樣的數(shù)ai， 其左邊的數(shù)都小

49、于等于它，右邊的數(shù)都大于等于它。能否只用一個(gè)額外數(shù)組和少量其它空間實(shí)現(xiàn)。2. 一個(gè)文件，內(nèi)含一千萬行字符串，每個(gè)字符串在1K以內(nèi)， 要求找出所有相反的串對(duì)，如 abc 和 cba。3.STL的set用什么實(shí)現(xiàn)的？為什么不用hash?82. 第 2 組百度面試題1. 給出兩個(gè)集合 A和B,其中集合 A=name,集合 B=age、 sex、 scholarship、 address、 . . .，要求：?jiǎn)栴}1、根據(jù)集合 A中的name查詢出集合B中對(duì)應(yīng)的屬性信息；問題2、根據(jù)集合B中的屬性信息(單個(gè)屬性，如age<20等)，查詢出集合A中對(duì)應(yīng)的name。2. 給出一個(gè)文件，里面包含兩個(gè)字段

50、url、 size，即url為網(wǎng)址，size為對(duì)應(yīng)網(wǎng)址訪問的次數(shù)，要求：?jiǎn)栴}1、利用Linux Shell命令或自己設(shè)計(jì)算法，查詢出url字符串中包含"baidu”子字符串對(duì)應(yīng)的 size字段值；問題2、根據(jù)問題1的查詢結(jié)果，對(duì)其按照size由大到小的排列。(說明：url數(shù)據(jù)量很大，100億級(jí)以上)83. 第 3 組百度面試題1. 今年百度的一道題目 百度筆試：給定一個(gè)存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。 要求：空間復(fù)雜度 0(1),時(shí)間復(fù)雜度為 0 (n)。2. 百度筆試題用 C 語言實(shí)現(xiàn)函數(shù) void * memmove(void *dest, const

51、 void *src, size_t n) 。memmove函數(shù)的功能是拷貝 src所指的內(nèi)存內(nèi)容前 n個(gè)字節(jié)到dest所指的地址上。 分析：由于可以把任何類型的指針賦給 void 類型的指針 這個(gè)函數(shù)主要是實(shí)現(xiàn)各種數(shù)據(jù)類型的拷貝。84. 第 4 組百度面試題2010 年 3 道百度面試題 相信,你懂其中的含金量 1. az 包括大小寫與 09 組成的 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)

52、造一個(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é)重疊。 分析：記住，這種題目往往就是考你對(duì)邊界的考慮情況。2.已知一個(gè)字符串，比如 asderwsde, 尋找其中的一個(gè)子字符串比如 sde 的個(gè)數(shù)， 如果沒有返回 0，有的話返回子字符串的個(gè)數(shù)。86. 怎樣編寫一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹中？ 分析 :

53、本題考察二叉搜索樹的建樹方法，簡(jiǎn)單的遞歸結(jié)構(gòu)。 關(guān)于樹的算法設(shè)計(jì)一定要聯(lián)想到遞歸，因?yàn)闃浔旧砭褪沁f歸的定義。而，學(xué)會(huì)把遞歸改稱非遞歸也是一種必要的技術(shù)。 畢竟，遞歸會(huì)造成棧溢出，關(guān)于系統(tǒng)底層的程序中不到非不得以最好不要用。 但是對(duì)某些數(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)庫(kù)中的一些函數(shù)）88.2005 年 11 月金山

54、筆試題。編碼完成下面的處理函數(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, ”-0

55、123”-123, “123CS45”123, “123.45CS”123, “ CS123.45”03. 快速排序（東軟喜歡考類似的算法填空題，又如堆排序的算法等）4. 刪除字符串中的數(shù)字并壓縮字符串。如字符串” abc123de4fg56 ”處理后變?yōu)椤?abcdefg”。注意空間和效率。（下面的算法只需要一次遍歷，不需要開辟新空間，時(shí)間復(fù)雜度為O（N）5. 求兩個(gè)串中的第一個(gè)最長(zhǎng)子串（神州數(shù)碼以前試題）。如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。90.1. 不開辟用于交換數(shù)據(jù)的臨時(shí)空間

56、，如何完成字符串的逆序（在技術(shù)一輪面試中，有些面試官會(huì)這樣問）。2. 刪除串中指定的字符 （做此題時(shí)，千萬不要開辟新空間，否則面試官可能認(rèn)為你不適合做嵌入式開發(fā)）3. 判斷單鏈表中是否存在環(huán)。91.1. 一道著名的毒酒問題有 1000 桶酒，其中 1 桶有毒。而一旦吃了，毒性會(huì)在 1 周后發(fā)作。 現(xiàn)在我們用小老鼠做實(shí)驗(yàn)，要在 1 周內(nèi)找出那桶毒酒，問最少需要多少老鼠。2. 有趣的石頭問題有一堆 1 萬個(gè)石頭和 1 萬個(gè)木頭，對(duì)于每個(gè)石頭都有 1 個(gè)木頭和它重量一樣， 把配對(duì)的石頭和木頭找出來。92.1 .多人排成一個(gè)隊(duì)列 ,我們認(rèn)為從低到高是正確的序列 ,但是總有部分人不遵守秩序。 如果說 ,前面的人比后面的人高