.把二元查詢樹轉變成排序的雙向鍊錶
題目：輸入一棵二元查詢樹，將該二元查詢樹轉換成乙個排序的雙向鍊錶。
要求不能建立任何新的結點，只調整指標的指向。
10 / \
6 14
/ \ / \
4 8 12 16
轉換成雙向鍊錶
4=6=8=10=12=14=16。
首先我們定義的二元查詢樹節點的資料結構如下：
struct bstreenode
;2.設計包含min函式的棧。
定義棧的資料結構，要求新增乙個min函式，能夠得到棧的最小元素。
要求函式min、push以及pop的時間複雜度都是o(1)。
3.求子陣列的最大和
題目：輸入乙個整形陣列，陣列裡有正數也有負數。
陣列中連續的乙個或多個整數組成乙個子陣列，每個子陣列都有乙個和。
求所有子陣列的和的最大值。要求時間複雜度為o(n)。
例如輸入的陣列為1, -2, 3, 10, -4, 7, 2, -5，和最大的子陣列為3, 10, -4, 7, 2，
因此輸出為該子陣列的和18。
4.在二元樹中找出和為某一值的所有路徑
題目：輸入乙個整數和一棵二元樹。
從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
列印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
10/ \5 12
/ \4 7則列印出兩條路徑：10, 12和10, 5, 7。
二元樹節點的資料結構定義為：
struct binarytreenode // a node in the binary tree
;5.查詢最小的k個元素
題目：輸入n個整數，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。
第6題騰訊面試題：
給你10分鐘時間，根據上排給出十個數，在其下排填出對應的十個數
要求下排每個數都是先前上排那十個數在下排出現的次數。
上排的十個數如下：
【0，1，2，3，4，5，6，7，8，9】
舉乙個例子，
數值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出現了6次，1在下排出現了2次，
2在下排出現了1次，3在下排出現了0次....
以此類推..
第7題微軟亞院之程式設計判斷倆個鍊錶是否相交
給出倆個單向鍊錶的頭指標，比如h1，h2，判斷這倆個鍊錶是否相交。
為了簡化問題，我們假設倆個鍊錶均不帶環。
問題擴充套件：
1.如果鍊錶可能有環列?
2.如果需要求出倆個鍊錶相交的第乙個節點列?
第8題此貼選一些比較怪的題，，由於其中題目本身與演算法關係不大，僅考考思維。特此並作一題。
1.有兩個房間，一間房裡有三盞燈，另一間房有控制著三盞燈的三個開關，
這兩個房間是分割開的，從一間裡不能看到另一間的情況。
現在要求受訓者分別進這兩房間一次，然後判斷出這三盞燈分別是由哪個開關控制的。
有什麼辦法呢？
2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。
如果你只能將金條切割兩次，你怎樣分給這些工人?
3. ★用一種演算法來顛倒乙個鏈結表的順序。現在在不用遞迴式的情況下做一遍。
★用一種演算法在乙個迴圈的鏈結表裡插入乙個節點，但不得穿越鏈結表。
★用一種演算法整理乙個陣列。你為什麼選擇這種方法?
★用一種演算法使通用字串相匹配。
★顛倒乙個字串。優化速度。優化空間。
★顛倒乙個句子中的詞的順序，比如將「我叫克麗絲」轉換為「克麗絲叫我」，
實現速度最快，移動最少。
★找到乙個子字串。優化速度。優化空間。
★比較兩個字串，用o(n)時間和恒量空間。
★假設你有乙個用1001個整數組成的陣列，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除乙個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個陣列做一次處理，用一種演算法找出重複的那個數字。
如果你在運算中使用了輔助的儲存方式，那麼你能找到不用這種方式的演算法嗎?
★不用乘法或加法增加8倍。現在用同樣的方法增加7倍。
第9題判斷整數序列是不是二元查詢樹的後序遍歷結果
題目：輸入乙個整數陣列，判斷該陣列是不是某二元查詢樹的後序遍歷的結果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由於這一整數序列是如下樹的後序遍歷結果：
8 / \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的後序遍歷的結果是這個序列，因此返回false。
第10題
翻轉句子中單詞的順序。
題目：輸入乙個英文句子，翻轉句子中單詞的順序，但單詞內字元的順序不變。
句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入「i am a student.」，則輸出「student. a am i」。
第11題
求二叉樹中節點的最大距離...
如果我們把二叉樹看成乙個圖，父子節點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節點之間邊的個數。
寫乙個程式，
求一棵二叉樹中相距最遠的兩個節點之間的距離。
第12題
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（a?b:c）。
第13題：
題目：輸入乙個單向鍊錶，輸出該鍊錶中倒數第k個結點。鍊錶的倒數第0個結點為鍊錶的尾指標。
鍊錶結點定義如下：
struct listnode
;第14題：
題目：輸入乙個已經按公升序排序過的陣列和乙個數字，
在陣列中查詢兩個數，使得它們的和正好是輸入的那個數字。
要求時間複雜度是o(n)。如果有多對數字的和等於輸入的數字，輸出任意一對即可。
例如輸入陣列1、2、4、7、11、15和數字15。由於4+11=15，因此輸出4和11。
第15題：
題目：輸入一顆二元查詢樹，將該樹轉換為它的映象，
即在轉換後的二元查詢樹中，左子樹的結點都大於右子樹的結點。
用遞迴和迴圈兩種方法完成樹的映象轉換。
例如輸入：
8 / \
6 10
/\ /\
5 7 9 11
輸出： 8
/ \10 6
/\ /\
11 9 7 5
定義二元查詢樹的結點為：
struct bstreenode // a node in the binary search tree (bst)
;第16題：
題目（微軟）：
輸入一顆二元樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印。
例如輸入
8 / \
6 10
/ \ / \
5 7 9 11
輸出8 6 10 5 7 9 11。
第17題：
題目：在乙個字串中找到第乙個只出現一次的字元。如輸入abaccdeff，則輸出b。
分析：這道題是2023年google的一道筆試題。
第18題：
題目：n個數字（0,1,…,n-1）形成乙個圓圈，從數字0開始，
每次從這個圓圈中刪除第m個數字（第乙個為當前數字本身，第二個為當前數字的下乙個數字）。
當乙個數字刪除後，從被刪除數字的下乙個繼續刪除第m個數字。
求出在這個圓圈中剩下的最後乙個數字。
july：我想，這個題目，不少人已經見識過了。
第19題：
題目：定義fibonacci數列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數列的第n項。
分析：在很多c語言教科書中講到遞迴函式的時候，都會用fibonacci作為例子。
因此很多程式設計師對這道題的遞迴解法非常熟悉，但....呵呵，你知道的。。
第20題：
題目：輸入乙個表示整數的字串，把該字串轉換成整數並輸出。
例如輸入字串"345"，則輸出整數345。
第21題
2023年中興面試題
程式設計求解：
輸入兩個整數 n 和 m，從數列1，2，3.......n 中隨意取幾個數,
使其和等於 m ,要求將其中所有的可能組合列出來.
第22題：
有4張紅色的牌和4張藍色的牌，主持人先拿任意兩張，再分別在a、b、c三人額頭上貼任意兩張牌，
a、b、c三人都可以看見其餘兩人額頭上的牌，看完後讓他們猜自己額頭上是什麼顏色的牌，
a說不知道，b說不知道，c說不知道，然後a說知道了。
請教如何推理，a是怎麼知道的。
如果用程式，又怎麼實現呢？
第23題：
用最簡單，最快速的方法計算出下面這個圓形是否和正方形相交。"
3d座標系原點(0.0,0.0,0.0)
圓形:半徑r = 3.0
圓心o = (*.*, 0.0, *.*)
正方形:
4個角座標;
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
第24題：
鍊錶操作，
（1）.單鏈表就地逆置，
（2）合併鍊錶
第25題：
寫乙個函式,它的原形是int continumax(char *outputstr,char *intputstr)
功能：在字串中找出連續最長的數字串，並把這個串的長度返回，
並把這個最長數字串付給其中乙個函式引數outputstr所指記憶體。
例如："abcd12345ed125ss123456789"的首位址傳給intputstr後，函式將返回9，
outputstr所指的值為123456789
26.左旋轉字串
題目：定義字串的左旋轉操作：把字串前面的若干個字元移動到字串的尾部。
如把字串abcdef左旋轉2位得到字串cdefab。請實現字串左旋轉的函式。
要求時間對長度為n的字串操作的複雜度為o(n)，輔助記憶體為o(1)。
27.跳台階問題
題目：乙個台階總共有n級，如果一次可以跳1級，也可以跳2級。
求總共有多少總跳法，並分析演算法的時間複雜度。
這道題最近經常出現，包括microstrategy等比較重視演算法的公司
都曾先後選用過個這道題作為面試題或者筆試題。
28.整數的二進位制表示中1的個數
題目：輸入乙個整數，求該整數的二進位制表達中有多少個1。
例如輸入10，由於其二進位制表示為1010，有兩個1，因此輸出2。
演算法筆試或面試題
試題序號 1 題型演算法填空題 難度級別 4 知識點排序 分值 13分 所需時間 15分鐘 試題關鍵字直接插入排序 試題內容 直接插入排序 void insertsort int r 按遞增序對r 1 r n 進行直接插入排序 r j 1 5插入第i個記錄 答案內容 評分細則本題13分,全對得滿分,...
資料結構演算法面試題
微軟的22道資料結構演算法面試題 含答案 1 反轉乙個鍊錶。迴圈演算法。1 list reverse list l 13 return tmp 14 2 反轉乙個鍊錶。遞迴演算法。1 list resverse list l 8 return n 9 3 廣度優先遍歷二叉樹。1 void bst t...
資料結構 演算法面試題
資料結構 演算法面試100題 摘自csdn，作者july 高天的日誌 1.把二元查詢樹轉變成排序的雙向鍊錶 樹 題目 輸入一棵二元查詢樹，將該二元查詢樹轉換成乙個排序的雙向鍊錶。要求不能建立任何新的結點，只調整指標的指向。10 6 14 4 8 12 16 轉換成雙向鍊錶 4 6 8 10 12 1...