数据结构与算法面试题
轉(zhuǎn)自：http://hi.baidu.com/geogre_jsj/blog/item/e4b98fd2aab5aa3611df9b92.html
?
由于這些題，實在太火了。所以，應(yīng)廣大網(wǎng)友建議要求，在此把之前已整理公布的前80題，
?
現(xiàn)在，一次性分享出來。此也算是前80題第一次集體亮相。
?
此些題，已有上萬人，看到或見識到，若私自據(jù)為己有，必定為有知之人識破，付出代價。
?
所以，作者聲明：
?
本人July對以上所有任何內(nèi)容和資料享有版權(quán)，轉(zhuǎn)載請注明作者本人July出處。
向你的厚道致敬。謝謝。
?
----------------------------------------------------------------------------------------------------------------
?
?
?
1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
?題目：
輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。
?? 10
?/ \
?6?14
?/ \ / \
4?8 12 16
?轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
?
?首先我們定義的二元查找樹 節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：
?struct BSTreeNode
{
?int m_nValue; // value of node
?BSTreeNode *m_pLeft; // left child of node
?BSTreeNode *m_pRight; // right child of node
};
?
?
2.設(shè)計包含min函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
?
3.求子數(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。
?
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
4.在二元樹中找出和為某一值的所有路徑
?
題目：輸入一個整數(shù)和一棵二元樹。
從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如 輸入整數(shù)22和如下二元樹
?10?
?/ \??
?5?12??
?/?? \??
4???? 7
則打印出兩條路徑：10, 12和10, 5, 7。
?
二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
?
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
5.查找最小的k個元素
題目：輸入n個整數(shù)，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。
https://blog.csdn.net/worn_xiao/article/details/70432613
?
?
?
第6題
騰訊面試題：
給你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,0
0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，
2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....
以此類推..
?
?
第7題
微軟亞院之編程判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。
?
問題擴展：
1.如果鏈表可能有環(huán)列?
2.如果需要求出倆個鏈表相交的第一個節(jié)點列?
?
?
第8題
此貼選一些 比較怪的題，，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。
1.有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關(guān)，
?
這兩個房間是 分割開的，從一間里不能看到另一間的情況。
現(xiàn)在要求受訓(xùn)者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。
有什么辦法呢？
?
2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。
如果你只能將金條切割兩次，你怎樣分給這些工人?
?
3. ★用一種算法來顛倒一個鏈接表的順序。現(xiàn)在在不用遞歸式的情況下做一遍。
★用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。
★用一種算法整理一個數(shù)組。你為什么選擇這種方法?
★用一種算法使通用字符串相匹配。
★顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。
★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，
?
實現(xiàn)速度最快，移動最少。
★找到一個子字符串。優(yōu)化速度。優(yōu)化空間。
★比較兩個字符串，用O(n)時間和恒量空間。
★假設(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個數(shù)字出現(xiàn) 兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次處理，用一種算法找出重復(fù)的那個數(shù)字。如果你在運算中使用了輔助的存儲方式，那么你能找到不 用這種方式的算法嗎?
★不用乘法或加法增加8倍。現(xiàn)在用同樣的方法增加7倍。
?
?
?
?
第9題
判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果
題目：輸入一個整數(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é)果是這個序列，因此返回false。
?
?
?
第10題
翻轉(zhuǎn)句子中單詞的順序。
題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。
?
句子中單詞以空格符隔開。為簡單起見，標(biāo)點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
?
?
第11題
求二叉樹中節(jié)點的最大距離...
?
如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。
寫一個程序，
求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。
?
?
?
第12題
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。
?
?
?
第13題：
題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。
鏈表結(jié)點定義如下：?
struct ListNode
{
?int m_nKey;
?ListNode* m_pNext;
};
?
?
?
第14題：
題目：輸入一個已經(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é)點都大于右子樹的結(jié)點。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。?
例如輸入：
?8
?/ \
?6 10
?/\ /\
5 7 9 11
?
輸出：
?8
?/ \
?10 6
?/\ /\
11 9 7 5
?
定義二元查找樹的結(jié)點為：
struct BSTreeNode // a node in the binary search tree (BST)
{
?int m_nValue; // value of node
?BSTreeNode *m_pLeft; // left child of node
?BSTreeNode *m_pRight; // right child of node
};
?
?
?
第16題：
題目（微軟）：
輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。?
例如輸入
?8
?/ \
?6 10
/ \ / \
5 7 9 11
?
輸出8 6 10 5 7 9 11。
?
?
?
第17題：
題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。?
分析：這道題是2006年google的一道筆試題。
?
?
?
?
第18題：
題目：n個數(shù)字（0,1,…,n-1）形成一個圓圈，從數(shù)字0開始，
每次從這個圓圈中刪除第m個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。
當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。
求出在這個圓圈中剩下的最后一個數(shù)字。
July：我想，這個題目，不少人已經(jīng) 見識過了。
?
?
?
?
第19題：
題目：定義Fibonacci數(shù)列如下：?
?/ 0 n=0
f(n)= 1 n=1
?\ f(n-1)+f(n-2) n=2
?
輸入n，用最快的方法求該數(shù)列的第n項。
分析：在很多C語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci作為例子。
因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。
?
?
?
第20題：
題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。
例如輸入字符串"345"，則輸出整數(shù)345。
?
?
?
?
第21題
2010年中興面試題
編程求解：
輸入兩個整數(shù) n 和 m，從數(shù)列1，2，3.......n 中 隨意取幾個數(shù),
使其和等于 m ,要求將其中所有的可能組合列出來.
?
?
?
第22題：
有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，
A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，
A說不知道，B說不知道，C說不知道，然后A說知道了。
請教如何推理，A是怎么知道的。
如果用程序，又怎么實現(xiàn)呢？
?
?
?
?
第23題：
用最簡單，最快速的方法計算出下面這個圓形是否和正方形相交。"?
3D坐標(biāo)系 原點(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題：
鏈表操作，
（1）.單鏈表就地逆置，
（2）合并鏈表
?
?
?
第25題：
寫一個函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，
并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，
outputstr所指的值為123456789
?
?
?
26.左旋轉(zhuǎn)字符串
?
題目：
定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。
?
如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
?
?
?
27.跳臺階問題
題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。
求總共有多少總跳法，并分析算法的時間復(fù)雜度。
?
這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司
都曾先后選用過個這道題作為面試題或者筆試題。
?
?
?
?
?
28.整數(shù)的二進制表示中1的個數(shù)
題目：輸入一個整數(shù)，求該整數(shù)的二進制表達(dá)中有多少個1。
例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。
?
分析：
這是一道很基本的考查位運算的面試題。
包括微軟在內(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系列。
因為可以有如下的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ù)n，求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。
?
例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。
分析：這是一道廣為流傳的google面試題。
?
?
?
31.華為面試題：
一類似于蜂窩的結(jié)構(gòu)的圖，進行搜索最短路徑（要求5分鐘）
?
?
?
32.
有兩個序列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.
實現(xiàn)一個挺高級的字符匹配算法：
給一串很長字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3這些都要找出來
其實就是類似一些和諧系統(tǒng)。。。。。
?
?
?
?
34.
實現(xiàn)一個隊列。
隊列的應(yīng)用場景為：
一個生產(chǎn)者線程將int類型的數(shù)入列，一個消費者線程將int類型的數(shù)出列
?
?
?
?
35.
求一個矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時間復(fù)雜度;(3)用C寫出關(guān)鍵代碼
?
?
?
?
第36題-40題（有些題目搜集于CSDN上的網(wǎng)友，已標(biāo)明）：
36.引用自網(wǎng)友：longzuo
谷歌筆試：
n支隊伍比賽，分別編號為0，1，2。。。。n-1，已知它們之間的實力對比關(guān)系，
存儲在一個二維數(shù)組w[n][n]中，w[i][j] 的值代表編號為i，j的隊伍中更強的一支。
?
所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是 4對3， 5對8。.......
勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細(xì)分，即可以隨便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對5,直至出現(xiàn)第一名
?
編程實現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和 用于輸出比賽名次的數(shù)組result[n]，
求出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)]有存儲器可以將其存儲下來，
而且只輸入一次，如何從這個輸入流中隨機取得m個記錄。
?
3.大量的URL字符串，如何從中去除重復(fù)的，優(yōu)化時間空間復(fù)雜度
?
?
?
?
39.
網(wǎng)易有道筆試：
(1).
求一個二叉樹中任意兩個節(jié)點間的最大距離，
兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數(shù)，
比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。
?
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關(guān)的邊，
有向圖不再連通，描述算法。
?
40.百度研發(fā)筆試題
引用自：zp155334877
1)設(shè)計一個棧結(jié)構(gòu)，滿足一下條件：min，push，pop操作的時間復(fù)雜度為O(1)。
?
2)一串首尾相連的珠子(m個)，有N種顏色(N<=10)，
設(shè)計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。
并分析時間復(fù)雜度與空間復(fù)雜度。
?
3)設(shè)計一個系統(tǒng)處理詞語搭配問題，比如說 中國 和人民可以搭配，
則中國人民 人民中國都有效。要求：
?
?*系統(tǒng)每秒的查詢數(shù)量可能上千次；
?*詞語的數(shù)量級為10W；
?*每個詞至多可以與1W個詞搭配
?
當(dāng)用戶輸入中國人民的時候，要求返回與這個搭配詞組相關(guān)的信息。
?
?
?
?
41.求固晶機的晶元查找程序
晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤，
?
照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，
若匹配不過，照相機則按測好的晶元間距移到下一個位置。
求遍歷晶元盤的算法 求思路。
?
?
?
?
42.請修改append函數(shù)，利用這個函數(shù)實現(xiàn)：
?
兩個非降序鏈表的并集，1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結(jié)果，不能修改兩個鏈表的數(shù)據(jù)。
?
?
?
43.遞歸和非遞歸倆種方法實現(xiàn)二叉樹的前序遍歷。
?
?
?
44.騰訊面試題：
1.設(shè)計一個魔方（六面）的程序。
2.有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。
請用5分鐘時間，找出重復(fù)出現(xiàn)最多的前10條。
?
3.收藏了1萬條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似）
?
?
?
45.雅虎：
1.對于一個整數(shù)矩陣，存在一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）
?
某一個元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個全零矩陣經(jīng)過上述運算得到。
2.一個整數(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
?
?
?
?
46.搜狐：
四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（（））
?
?
?
47.創(chuàng)新工場：
求一個數(shù)組的最長遞減子序列 比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{9，5，4，3，2}
?
?
?
48.微軟：
一個數(shù)組是由一個遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個數(shù)。
?
?
?
49.一道看上去很嚇人的算法面試題：
如何對n個數(shù)進行排序，要求時間復(fù)雜度O(n)，空間復(fù)雜度O(1)
?
?
?
50.網(wǎng)易有道筆試：
1.求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數(shù)，
比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。
?
2.求一個有向連通圖的割點，割點的定義是，
如果除去此節(jié)點和與其相關(guān)的邊，有向圖不再連通，描述算法。
-------------------------------------------------------------------
?
?
51.和為n連續(xù)正數(shù)序列。
題目：輸入一個正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。
?
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個連續(xù)序列1-5、4-6和7-8。
分析：這是網(wǎng)易的一道面試題。
?
?
?
?
52.二元樹的深度。
?
題目：輸入一棵二元樹的根結(jié)點，求該樹的深度。
?
從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。
?
例如：輸入二元樹：
??????????????????????????????????????????? 10
????????????????????????????????????????? /???? \
??????????????????????????????????????? 6??????? 14
????????????????????????????????????? /???????? /?? \
??????????????????????????????????? 4????? ???12???? 16
?
輸出該樹的深度3。
?
二元樹的結(jié)點定義如下：
?
struct SBinaryTreeNode // a node of the binary tree
{
????? int?????????????? m_nValue; // value of node
????? SBinaryTreeNode?*m_pLeft;?// left child of node
????? SBinaryTreeNode?*m_pRight; // right child of node
};
分析：這道題本質(zhì)上還是考查二元樹的遍歷。
?
?
?
?
?
53.字符串的排列。
題目：輸入一個字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來的所有字符串
abc、acb、bac、bca、cab和cba。
?
分析：這是一道很好的考查對遞歸理解的編程題，
因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。
?
?
?
54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。
?
題目：輸入一個整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
?
所有偶數(shù)位于數(shù)組的后半部分。要求時間復(fù)雜度為O(n)。
?
?
?
?
55.
?
題目：類CMyString的聲明如下：
class CMyString
{
public:
????? CMyString(char* pData = NULL);
????? CMyString(const CMyString& str);
????? ~CMyString(void);
????? CMyString& operator = (const CMyString& str);
?
private:
????? char* m_pData;
};
請實現(xiàn)其賦值運算符的重載函數(shù)，要求異常安全，即當(dāng)對一個對象進行賦值時發(fā)生異常，對象的狀態(tài)不能改變。
?
?
?
56.最長公共字串。
?
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，
?
則字符串一稱之為字符串二的子串。
?
注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。
請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
?
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，
則輸出它們的長度4，并打印任意一個子串。
?
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動態(tài)規(guī)劃題，
?
因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
?
?
?
?
57.用倆個棧實現(xiàn)隊列。
?
題目：某隊列的聲明如下：
?
template<typename T> class CQueue
{
public:
????? CQueue() {}
????? ~CQueue() {}
?
????? void appendTail(const T& node);?// append a element to tail
????? void deleteHead();?????????????? // remove a element from head
?
private:
???? T> m_stack1;
???? T> m_stack2;
};
?
分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊列中有兩個棧。
因此這道題實質(zhì)上是要求我們用兩個棧來實現(xiàn)一個隊列。
相信大家對棧和隊列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，
因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數(shù)據(jù)容器，
我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。
?
?
?
?
58.從尾到頭輸出鏈表。
?
題目：輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：
struct ListNode
{
?
????? int?????? m_nKey;
????? ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。
該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。
?
?
?
?
59.不能被繼承的類。
題目：用C++設(shè)計一個不能被繼承的類。
?
分析：這是Adobe公司2007年校園招聘的最新筆試題。
這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。
?
?
?
?
?
60.在O（1）時間內(nèi)刪除鏈表結(jié)點。
?
題目：給定鏈表的頭指針和一個結(jié)點指針，在O(1)時間刪除該結(jié)點。鏈表結(jié)點的定義如下：
?
struct ListNode
?
{
?
????? int??????? m_nKey;
?
????? ListNode*?m_pNext;
?
};
?
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
?
分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，
?
更重要的是，還能考察我們對時間復(fù)雜度的理解。
-------------------------------------------------------------------------
?
?
?
61.找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字
題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。
請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
?
分析：這是一道很新穎的關(guān)于位運算的面試題。
?
?
?
?
62.找出鏈表的第一個公共結(jié)點。
題目：兩個單向鏈表，找出它們的第一個公共結(jié)點。
?
鏈表的結(jié)點定義為：
struct ListNode
?
{
?
????? int???????? m_nKey;
?
????? ListNode*?? m_pNext;
?
};
?
分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，
因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。
?
?
?
?
63.在字符串中刪除特定的字符。
題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，
?
則刪除之后的第一個字符串變成”Thy r stdnts.”。
?
分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，
因為寫程序操作字符串能很好的反映我們的編程基本功。
?
?
?
?
64. 尋找丑數(shù)。
題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，
但14不是，因為它包含因子7。習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。
求按從小到大的順序的第1500個丑數(shù)。
?
分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。
?
?
?
?
65.輸出1到最大的N位數(shù)
題目：輸入數(shù)字n，按順序輸出從1最大的n位10進制數(shù)。比如輸入3，
?
則輸出1、2、3一直到最大的3位數(shù)即999。
分析：這是一道很有意思的題目。看起來很簡單，其實里面卻有不少的玄機。
?
?
?
66.顛倒棧。
題目：用遞歸顛倒一個棧。例如輸入棧{1, 2, 3, 4, 5}，1在棧頂。
顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。
?
?
?
?
67.倆個閑玩娛樂。
?
1.撲克牌的順子
從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。
2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。
?
2.n個骰子的點數(shù)。
把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，
打印出S的所有可能的值出現(xiàn)的概率。
?
?
?
?
68.把數(shù)組排成最小的數(shù)。
題目：輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。
例如輸入數(shù)組{32,?321}，則輸出這兩個能排成的最小數(shù)字32132。
請給出解決問題的算法，并證明該算法。
?
分析：這是09年6月份百度的一道面試題，
從這道題我們可以看出百度對應(yīng)聘者在算法方面有很高的要求。
?
?
?
?
69.旋轉(zhuǎn)數(shù)組中的最小元素。
題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，
?
輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。
?
????分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，
時間復(fù)雜度顯然是O(N)。但這個思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。
?
?
?
?
70.給出一個函數(shù)來輸出一個字符串的所有排列。
ANSWER 簡單的回溯就可以實現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)，
?
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，
也需要一定的靈感，有興趣最好看看。
?
?
?
?
71.數(shù)值的整數(shù)次方。
?
題目：實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。
不需要考慮溢出。
?
分析：這是一道看起來很簡單的問題。可能有不少的人在看到題目后30秒寫出如下的代碼：
double Power(double base, int exponent)
{
?
????? double result = 1.0;
????? for(int i = 1; i <= exponent; ++i)
??????????? result *= base;
????? return result;
}
?
?
?
?
?
72.
題目：設(shè)計一個類，我們只能生成該類的一個實例。
分析：只能生成一個實例的類是實現(xiàn)了Singleton模式的類型。
?
?
?
?
73.對策字符串的最大長度。
?
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。
?
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。
?
?
?
?
?
?
74.數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字
?
題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。
?
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內(nèi)的多家公司都
曾經(jīng)采用過這個題目。要幾十分鐘的時間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應(yīng)和較強的邏輯思維能力。
?
?
?
?
?
75.二叉樹兩個結(jié)點的最低共同父結(jié)點
題目：二叉樹的結(jié)點定義如下：
struct TreeNode
{
?
??? int m_nvalue;
??? TreeNode* m_pLeft;
??? TreeNode* m_pRight;
};
?
輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。
分析：求數(shù)中兩個結(jié)點的最低共同結(jié)點是面試中經(jīng)常出現(xiàn)的一個問題。這個問題至少有兩個變種。
?
?
?
?
76.復(fù)雜鏈表的復(fù)制
?
題目：有一個復(fù)雜鏈表，其結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外，
還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。其結(jié)點的C++定義如下：
?struct ComplexNode
{
??? int m_nValue;
??? ComplexNode* m_pNext;
??? ComplexNode* m_pSibling;
};
?
下圖是一個含有5個結(jié)點的該類型復(fù)雜鏈表。
圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，
指向NULL的指針沒有畫出。????????????????????????????????
請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個復(fù)雜鏈表。
?
分析：在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化，這是一種很新穎的面試題。
要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應(yīng)能力，
對數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實的編程功底。
?
?
?
?
?
?
77.關(guān)于鏈表問題的面試題目如下：
?
1.給定單鏈表，檢測是否有環(huán)。
?
?使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達(dá)鏈表尾部，
?
說明無環(huán)，否則p1、p2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環(huán)。
?
?
?
2.給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。
?
????????如果head1==head2，那么顯然相交，直接返回head1。
?
否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2，假設(shè)len1>=len2，
那么指針p1由head1開始向后移動len1-len2步，指針p2=head2，
下面p1、p2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結(jié)點，
否則說明兩個鏈表沒有交點。
?
?
3.給定單鏈表(head)，如果有環(huán)的話請返回從頭結(jié)點進入環(huán)的第一個節(jié)點。
????????運用題一，我們可以檢查鏈表中是否有環(huán)。
????????如果有環(huán)，那么p1p2重合點p必然在環(huán)中。從p點斷開環(huán)，
方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，
一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。
?
?
4.只給定單鏈表中某個結(jié)點p(并非最后一個結(jié)點，即p->next!=NULL)指針，刪除該結(jié)點。
?辦法很簡單，首先是放p中數(shù)據(jù),然后將p->next的數(shù)據(jù)copy入p中，接下來刪除p->next即可。
?
5.只給定單鏈表中某個結(jié)點p(非空結(jié)點)，在p前面插入一個結(jié)點。
??辦法與前者類似，首先分配一個結(jié)點q，將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，
然后再將要插入的數(shù)據(jù)記錄在p中。
?
?
?
?
78.鏈表和數(shù)組的區(qū)別在哪里？
?
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點，現(xiàn)在公司招人的競爭可能就在細(xì)節(jié)上產(chǎn)生，
誰比較仔細(xì)，誰獲勝的機會就大。
?
?
?
?
79.
1.編寫實現(xiàn)鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？
2.編寫實現(xiàn)數(shù)組排序的一種算法。說明為什么你會選擇用這樣的方法？
3.請編寫能直接實現(xiàn)strstr()函數(shù)功能的代碼。
?
?
?
?
80.阿里巴巴一道筆試題
?
問題描述:
12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應(yīng)的第一排的人高,問排列方式有多少種?
這個筆試題,很YD,因為把某個遞歸關(guān)系隱藏得很深。
轉(zhuǎn)自：http://hi.baidu.com/geogre_jsj/blog/item/e4b98fd2aab5aa3611df9b92.html
?
由于這些題，實在太火了。所以，應(yīng)廣大網(wǎng)友建議要求，在此把之前已整理公布的前80題，
?
現(xiàn)在，一次性分享出來。此也算是前80題第一次集體亮相。
?
此些題，已有上萬人，看到或見識到，若私自據(jù)為己有，必定為有知之人識破，付出代價。
?
所以，作者聲明：
?
本人July對以上所有任何內(nèi)容和資料享有版權(quán)，轉(zhuǎn)載請注明作者本人July出處。
向你的厚道致敬。謝謝。
?
----------------------------------------------------------------------------------------------------------------
?
?
?
1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
?題目：
輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。
?? 10
?/ \
?6?14
?/ \ / \
4?8 12 16
?轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
?
?首先我們定義的二元查找樹 節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：
?struct BSTreeNode
{
?int m_nValue; // value of node
?BSTreeNode *m_pLeft; // left child of node
?BSTreeNode *m_pRight; // right child of node
};
?
?
2.設(shè)計包含min函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
?
3.求子數(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。
?
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
4.在二元樹中找出和為某一值的所有路徑
?
題目：輸入一個整數(shù)和一棵二元樹。
從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如 輸入整數(shù)22和如下二元樹
?10?
?/ \??
?5?12??
?/?? \??
4???? 7
則打印出兩條路徑：10, 12和10, 5, 7。
?
二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
?
答案
https://blog.csdn.net/worn_xiao/article/details/70432613
?
5.查找最小的k個元素
題目：輸入n個整數(shù)，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。
https://blog.csdn.net/worn_xiao/article/details/70432613
?
?
?
第6題
騰訊面試題：
給你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,0
0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，
2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....
以此類推..
?
?
第7題
微軟亞院之編程判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。
?
問題擴展：
1.如果鏈表可能有環(huán)列?
2.如果需要求出倆個鏈表相交的第一個節(jié)點列?
?
?
第8題
此貼選一些 比較怪的題，，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。
1.有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關(guān)，
?
這兩個房間是 分割開的，從一間里不能看到另一間的情況。
現(xiàn)在要求受訓(xùn)者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。
有什么辦法呢？
?
2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。
如果你只能將金條切割兩次，你怎樣分給這些工人?
?
3. ★用一種算法來顛倒一個鏈接表的順序。現(xiàn)在在不用遞歸式的情況下做一遍。
★用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。
★用一種算法整理一個數(shù)組。你為什么選擇這種方法?
★用一種算法使通用字符串相匹配。
★顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。
★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，
?
實現(xiàn)速度最快，移動最少。
★找到一個子字符串。優(yōu)化速度。優(yōu)化空間。
★比較兩個字符串，用O(n)時間和恒量空間。
★假設(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個數(shù)字出現(xiàn) 兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次處理，用一種算法找出重復(fù)的那個數(shù)字。如果你在運算中使用了輔助的存儲方式，那么你能找到不 用這種方式的算法嗎?
★不用乘法或加法增加8倍。現(xiàn)在用同樣的方法增加7倍。
?
?
?
?
第9題
判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果
題目：輸入一個整數(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é)果是這個序列，因此返回false。
?
?
?
第10題
翻轉(zhuǎn)句子中單詞的順序。
題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。
?
句子中單詞以空格符隔開。為簡單起見，標(biāo)點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
?
?
第11題
求二叉樹中節(jié)點的最大距離...
?
如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。
寫一個程序，
求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。
?
?
?
第12題
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。
?
?
?
第13題：
題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。
鏈表結(jié)點定義如下：?
struct ListNode
{
?int m_nKey;
?ListNode* m_pNext;
};
?
?
?
第14題：
題目：輸入一個已經(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é)點都大于右子樹的結(jié)點。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。?
例如輸入：
?8
?/ \
?6 10
?/\ /\
5 7 9 11
?
輸出：
?8
?/ \
?10 6
?/\ /\
11 9 7 5
?
定義二元查找樹的結(jié)點為：
struct BSTreeNode // a node in the binary search tree (BST)
{
?int m_nValue; // value of node
?BSTreeNode *m_pLeft; // left child of node
?BSTreeNode *m_pRight; // right child of node
};
?
?
?
第16題：
題目（微軟）：
輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。?
例如輸入
?8
?/ \
?6 10
/ \ / \
5 7 9 11
?
輸出8 6 10 5 7 9 11。
?
?
?
第17題：
題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。?
分析：這道題是2006年google的一道筆試題。
?
?
?
?
第18題：
題目：n個數(shù)字（0,1,…,n-1）形成一個圓圈，從數(shù)字0開始，
每次從這個圓圈中刪除第m個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。
當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。
求出在這個圓圈中剩下的最后一個數(shù)字。
July：我想，這個題目，不少人已經(jīng) 見識過了。
?
?
?
?
第19題：
題目：定義Fibonacci數(shù)列如下：?
?/ 0 n=0
f(n)= 1 n=1
?\ f(n-1)+f(n-2) n=2
?
輸入n，用最快的方法求該數(shù)列的第n項。
分析：在很多C語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci作為例子。
因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。
?
?
?
第20題：
題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。
例如輸入字符串"345"，則輸出整數(shù)345。
?
?
?
?
第21題
2010年中興面試題
編程求解：
輸入兩個整數(shù) n 和 m，從數(shù)列1，2，3.......n 中 隨意取幾個數(shù),
使其和等于 m ,要求將其中所有的可能組合列出來.
?
?
?
第22題：
有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，
A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，
A說不知道，B說不知道，C說不知道，然后A說知道了。
請教如何推理，A是怎么知道的。
如果用程序，又怎么實現(xiàn)呢？
?
?
?
?
第23題：
用最簡單，最快速的方法計算出下面這個圓形是否和正方形相交。"?
3D坐標(biāo)系 原點(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題：
鏈表操作，
（1）.單鏈表就地逆置，
（2）合并鏈表
?
?
?
第25題：
寫一個函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，
并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，
outputstr所指的值為123456789
?
?
?
26.左旋轉(zhuǎn)字符串
?
題目：
定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。
?
如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
?
?
?
27.跳臺階問題
題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。
求總共有多少總跳法，并分析算法的時間復(fù)雜度。
?
這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司
都曾先后選用過個這道題作為面試題或者筆試題。
?
?
?
?
?
28.整數(shù)的二進制表示中1的個數(shù)
題目：輸入一個整數(shù)，求該整數(shù)的二進制表達(dá)中有多少個1。
例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。
?
分析：
這是一道很基本的考查位運算的面試題。
包括微軟在內(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系列。
因為可以有如下的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ù)n，求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。
?
例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。
分析：這是一道廣為流傳的google面試題。
?
?
?
31.華為面試題：
一類似于蜂窩的結(jié)構(gòu)的圖，進行搜索最短路徑（要求5分鐘）
?
?
?
32.
有兩個序列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.
實現(xiàn)一個挺高級的字符匹配算法：
給一串很長字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3這些都要找出來
其實就是類似一些和諧系統(tǒng)。。。。。
?
?
?
?
34.
實現(xiàn)一個隊列。
隊列的應(yīng)用場景為：
一個生產(chǎn)者線程將int類型的數(shù)入列，一個消費者線程將int類型的數(shù)出列
?
?
?
?
35.
求一個矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時間復(fù)雜度;(3)用C寫出關(guān)鍵代碼
?
?
?
?
第36題-40題（有些題目搜集于CSDN上的網(wǎng)友，已標(biāo)明）：
36.引用自網(wǎng)友：longzuo
谷歌筆試：
n支隊伍比賽，分別編號為0，1，2。。。。n-1，已知它們之間的實力對比關(guān)系，
存儲在一個二維數(shù)組w[n][n]中，w[i][j] 的值代表編號為i，j的隊伍中更強的一支。
?
所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是 4對3， 5對8。.......
勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細(xì)分，即可以隨便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對5,直至出現(xiàn)第一名
?
編程實現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和 用于輸出比賽名次的數(shù)組result[n]，
求出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)]有存儲器可以將其存儲下來，
而且只輸入一次，如何從這個輸入流中隨機取得m個記錄。
?
3.大量的URL字符串，如何從中去除重復(fù)的，優(yōu)化時間空間復(fù)雜度
?
?
?
?
39.
網(wǎng)易有道筆試：
(1).
求一個二叉樹中任意兩個節(jié)點間的最大距離，
兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數(shù)，
比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。
?
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關(guān)的邊，
有向圖不再連通，描述算法。
?
40.百度研發(fā)筆試題
引用自：zp155334877
1)設(shè)計一個棧結(jié)構(gòu)，滿足一下條件：min，push，pop操作的時間復(fù)雜度為O(1)。
?
2)一串首尾相連的珠子(m個)，有N種顏色(N<=10)，
設(shè)計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。
并分析時間復(fù)雜度與空間復(fù)雜度。
?
3)設(shè)計一個系統(tǒng)處理詞語搭配問題，比如說 中國 和人民可以搭配，
則中國人民 人民中國都有效。要求：
?
?*系統(tǒng)每秒的查詢數(shù)量可能上千次；
?*詞語的數(shù)量級為10W；
?*每個詞至多可以與1W個詞搭配
?
當(dāng)用戶輸入中國人民的時候，要求返回與這個搭配詞組相關(guān)的信息。
?
?
?
?
41.求固晶機的晶元查找程序
晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤，
?
照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，
若匹配不過，照相機則按測好的晶元間距移到下一個位置。
求遍歷晶元盤的算法 求思路。
?
?
?
?
42.請修改append函數(shù)，利用這個函數(shù)實現(xiàn)：
?
兩個非降序鏈表的并集，1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結(jié)果，不能修改兩個鏈表的數(shù)據(jù)。
?
?
?
43.遞歸和非遞歸倆種方法實現(xiàn)二叉樹的前序遍歷。
?
?
?
44.騰訊面試題：
1.設(shè)計一個魔方（六面）的程序。
2.有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。
請用5分鐘時間，找出重復(fù)出現(xiàn)最多的前10條。
?
3.收藏了1萬條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似）
?
?
?
45.雅虎：
1.對于一個整數(shù)矩陣，存在一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）
?
某一個元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個全零矩陣經(jīng)過上述運算得到。
2.一個整數(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
?
?
?
?
46.搜狐：
四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（（））
?
?
?
47.創(chuàng)新工場：
求一個數(shù)組的最長遞減子序列 比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{9，5，4，3，2}
?
?
?
48.微軟：
一個數(shù)組是由一個遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個數(shù)。
?
?
?
49.一道看上去很嚇人的算法面試題：
如何對n個數(shù)進行排序，要求時間復(fù)雜度O(n)，空間復(fù)雜度O(1)
?
?
?
50.網(wǎng)易有道筆試：
1.求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數(shù)，
比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。
?
2.求一個有向連通圖的割點，割點的定義是，
如果除去此節(jié)點和與其相關(guān)的邊，有向圖不再連通，描述算法。
-------------------------------------------------------------------
?
?
51.和為n連續(xù)正數(shù)序列。
題目：輸入一個正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。
?
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個連續(xù)序列1-5、4-6和7-8。
分析：這是網(wǎng)易的一道面試題。
?
?
?
?
52.二元樹的深度。
?
題目：輸入一棵二元樹的根結(jié)點，求該樹的深度。
?
從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。
?
例如：輸入二元樹：
??????????????????????????????????????????? 10
????????????????????????????????????????? /???? \
??????????????????????????????????????? 6??????? 14
????????????????????????????????????? /???????? /?? \
??????????????????????????????????? 4????? ???12???? 16
?
輸出該樹的深度3。
?
二元樹的結(jié)點定義如下：
?
struct SBinaryTreeNode // a node of the binary tree
{
????? int?????????????? m_nValue; // value of node
????? SBinaryTreeNode?*m_pLeft;?// left child of node
????? SBinaryTreeNode?*m_pRight; // right child of node
};
分析：這道題本質(zhì)上還是考查二元樹的遍歷。
?
?
?
?
?
53.字符串的排列。
題目：輸入一個字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來的所有字符串
abc、acb、bac、bca、cab和cba。
?
分析：這是一道很好的考查對遞歸理解的編程題，
因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。
?
?
?
54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。
?
題目：輸入一個整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
?
所有偶數(shù)位于數(shù)組的后半部分。要求時間復(fù)雜度為O(n)。
?
?
?
?
55.
?
題目：類CMyString的聲明如下：
class CMyString
{
public:
????? CMyString(char* pData = NULL);
????? CMyString(const CMyString& str);
????? ~CMyString(void);
????? CMyString& operator = (const CMyString& str);
?
private:
????? char* m_pData;
};
請實現(xiàn)其賦值運算符的重載函數(shù)，要求異常安全，即當(dāng)對一個對象進行賦值時發(fā)生異常，對象的狀態(tài)不能改變。
?
?
?
56.最長公共字串。
?
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，
?
則字符串一稱之為字符串二的子串。
?
注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。
請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
?
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，
則輸出它們的長度4，并打印任意一個子串。
?
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動態(tài)規(guī)劃題，
?
因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
?
?
?
?
57.用倆個棧實現(xiàn)隊列。
?
題目：某隊列的聲明如下：
?
template<typename T> class CQueue
{
public:
????? CQueue() {}
????? ~CQueue() {}
?
????? void appendTail(const T& node);?// append a element to tail
????? void deleteHead();?????????????? // remove a element from head
?
private:
???? T> m_stack1;
???? T> m_stack2;
};
?
分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊列中有兩個棧。
因此這道題實質(zhì)上是要求我們用兩個棧來實現(xiàn)一個隊列。
相信大家對棧和隊列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，
因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數(shù)據(jù)容器，
我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。
?
?
?
?
58.從尾到頭輸出鏈表。
?
題目：輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：
struct ListNode
{
?
????? int?????? m_nKey;
????? ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。
該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。
?
?
?
?
59.不能被繼承的類。
題目：用C++設(shè)計一個不能被繼承的類。
?
分析：這是Adobe公司2007年校園招聘的最新筆試題。
這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。
?
?
?
?
?
60.在O（1）時間內(nèi)刪除鏈表結(jié)點。
?
題目：給定鏈表的頭指針和一個結(jié)點指針，在O(1)時間刪除該結(jié)點。鏈表結(jié)點的定義如下：
?
struct ListNode
?
{
?
????? int??????? m_nKey;
?
????? ListNode*?m_pNext;
?
};
?
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
?
分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，
?
更重要的是，還能考察我們對時間復(fù)雜度的理解。
-------------------------------------------------------------------------
?
?
?
61.找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字
題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。
請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
?
分析：這是一道很新穎的關(guān)于位運算的面試題。
?
?
?
?
62.找出鏈表的第一個公共結(jié)點。
題目：兩個單向鏈表，找出它們的第一個公共結(jié)點。
?
鏈表的結(jié)點定義為：
struct ListNode
?
{
?
????? int???????? m_nKey;
?
????? ListNode*?? m_pNext;
?
};
?
分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，
因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。
?
?
?
?
63.在字符串中刪除特定的字符。
題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，
?
則刪除之后的第一個字符串變成”Thy r stdnts.”。
?
分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，
因為寫程序操作字符串能很好的反映我們的編程基本功。
?
?
?
?
64. 尋找丑數(shù)。
題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，
但14不是，因為它包含因子7。習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。
求按從小到大的順序的第1500個丑數(shù)。
?
分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。
?
?
?
?
65.輸出1到最大的N位數(shù)
題目：輸入數(shù)字n，按順序輸出從1最大的n位10進制數(shù)。比如輸入3，
?
則輸出1、2、3一直到最大的3位數(shù)即999。
分析：這是一道很有意思的題目。看起來很簡單，其實里面卻有不少的玄機。
?
?
?
66.顛倒棧。
題目：用遞歸顛倒一個棧。例如輸入棧{1, 2, 3, 4, 5}，1在棧頂。
顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。
?
?
?
?
67.倆個閑玩娛樂。
?
1.撲克牌的順子
從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。
2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。
?
2.n個骰子的點數(shù)。
把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，
打印出S的所有可能的值出現(xiàn)的概率。
?
?
?
?
68.把數(shù)組排成最小的數(shù)。
題目：輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。
例如輸入數(shù)組{32,?321}，則輸出這兩個能排成的最小數(shù)字32132。
請給出解決問題的算法，并證明該算法。
?
分析：這是09年6月份百度的一道面試題，
從這道題我們可以看出百度對應(yīng)聘者在算法方面有很高的要求。
?
?
?
?
69.旋轉(zhuǎn)數(shù)組中的最小元素。
題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，
?
輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。
?
????分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，
時間復(fù)雜度顯然是O(N)。但這個思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。
?
?
?
?
70.給出一個函數(shù)來輸出一個字符串的所有排列。
ANSWER 簡單的回溯就可以實現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)，
?
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，
也需要一定的靈感，有興趣最好看看。
?
?
?
?
71.數(shù)值的整數(shù)次方。
?
題目：實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。
不需要考慮溢出。
?
分析：這是一道看起來很簡單的問題。可能有不少的人在看到題目后30秒寫出如下的代碼：
double Power(double base, int exponent)
{
?
????? double result = 1.0;
????? for(int i = 1; i <= exponent; ++i)
??????????? result *= base;
????? return result;
}
?
?
?
?
?
72.
題目：設(shè)計一個類，我們只能生成該類的一個實例。
分析：只能生成一個實例的類是實現(xiàn)了Singleton模式的類型。
?
?
?
?
73.對策字符串的最大長度。
?
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。
?
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。
?
?
?
?
?
?
74.數(shù)組中超過出現(xiàn)次數(shù)超過一半的數(shù)字
?
題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。
?
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內(nèi)的多家公司都
曾經(jīng)采用過這個題目。要幾十分鐘的時間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應(yīng)和較強的邏輯思維能力。
?
?
?
?
?
75.二叉樹兩個結(jié)點的最低共同父結(jié)點
題目：二叉樹的結(jié)點定義如下：
struct TreeNode
{
?
??? int m_nvalue;
??? TreeNode* m_pLeft;
??? TreeNode* m_pRight;
};
?
輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。
分析：求數(shù)中兩個結(jié)點的最低共同結(jié)點是面試中經(jīng)常出現(xiàn)的一個問題。這個問題至少有兩個變種。
?
?
?
?
76.復(fù)雜鏈表的復(fù)制
?
題目：有一個復(fù)雜鏈表，其結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外，
還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。其結(jié)點的C++定義如下：
?struct ComplexNode
{
??? int m_nValue;
??? ComplexNode* m_pNext;
??? ComplexNode* m_pSibling;
};
?
下圖是一個含有5個結(jié)點的該類型復(fù)雜鏈表。
圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，
指向NULL的指針沒有畫出。????????????????????????????????
請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個復(fù)雜鏈表。
?
分析：在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化，這是一種很新穎的面試題。
要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應(yīng)能力，
對數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實的編程功底。
?
?
?
?
?
?
77.關(guān)于鏈表問題的面試題目如下：
?
1.給定單鏈表，檢測是否有環(huán)。
?
?使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達(dá)鏈表尾部，
?
說明無環(huán)，否則p1、p2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環(huán)。
?
?
?
2.給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。
?
????????如果head1==head2，那么顯然相交，直接返回head1。
?
否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2，假設(shè)len1>=len2，
那么指針p1由head1開始向后移動len1-len2步，指針p2=head2，
下面p1、p2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結(jié)點，
否則說明兩個鏈表沒有交點。
?
?
3.給定單鏈表(head)，如果有環(huán)的話請返回從頭結(jié)點進入環(huán)的第一個節(jié)點。
????????運用題一，我們可以檢查鏈表中是否有環(huán)。
????????如果有環(huán)，那么p1p2重合點p必然在環(huán)中。從p點斷開環(huán)，
方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，
一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。
?
?
4.只給定單鏈表中某個結(jié)點p(并非最后一個結(jié)點，即p->next!=NULL)指針，刪除該結(jié)點。
?辦法很簡單，首先是放p中數(shù)據(jù),然后將p->next的數(shù)據(jù)copy入p中，接下來刪除p->next即可。
?
5.只給定單鏈表中某個結(jié)點p(非空結(jié)點)，在p前面插入一個結(jié)點。
??辦法與前者類似，首先分配一個結(jié)點q，將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，
然后再將要插入的數(shù)據(jù)記錄在p中。
?
?
?
?
78.鏈表和數(shù)組的區(qū)別在哪里？
?
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點，現(xiàn)在公司招人的競爭可能就在細(xì)節(jié)上產(chǎn)生，
誰比較仔細(xì)，誰獲勝的機會就大。
?
?
?
?
79.
1.編寫實現(xiàn)鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？
2.編寫實現(xiàn)數(shù)組排序的一種算法。說明為什么你會選擇用這樣的方法？
3.請編寫能直接實現(xiàn)strstr()函數(shù)功能的代碼。
?
?
?
?
80.阿里巴巴一道筆試題
?
問題描述:
12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應(yīng)的第一排的人高,問排列方式有多少種?
這個筆試題,很YD,因為把某個遞歸關(guān)系隱藏得很深。
?
總結(jié)
以上是生活随笔為你收集整理的数据结构与算法面试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Character类的常用方法
- 下一篇： 打地鼠小游戏代码