微軟、谷歌等公司經(jīng)典面試100題第101-170

1、全新整理：微軟、谷歌、等公司經(jīng)典面試 100 題第 101-170 題整理:July、二零一一年三月九日。應(yīng)網(wǎng)友承諾與要求，全新整理。，請注明出處。博主說明：此 100 題V0.2 版，本人不再保證，還會提供。因為之前整理的微軟 100 題，已經(jīng)基本上，把題目都出盡了。見諒。微軟十五道面試題1、有一個整數(shù)數(shù)組，請求出兩兩之差絕對值最小的值,記住，只要得出最小值即可，不需要求出是哪兩個數(shù)。2、寫一個函數(shù)，檢查字符是否是整數(shù)，如果是，返回其整數(shù)值。（或者：怎樣只用 4 行代碼編寫出一個從字符串到長整形的函數(shù)？）3、給出一個函數(shù)來輸出一個字符串的所有排列。4、（a）請編寫實現(xiàn)malloc()內(nèi)存分配

2、函數(shù)功能一樣的代碼。（b）給出一個函數(shù)來兩個字符串 A 和B。字符串 A 的后幾個字節(jié)和字符串 B 的前幾個字節(jié)。5、怎樣編寫一個程序，把一個有序整數(shù)數(shù)組放到二叉樹中？6、怎樣從頂部開始逐層打印二叉樹結(jié)點數(shù)據(jù)？請編程。7、怎樣把一個鏈表掉個順序（也就是反序，注意鏈表的邊界條件并考慮空鏈表）？8、請編寫能直接實現(xiàn)atoi(const char * pstr)函數(shù)功能的代碼。9、編程實現(xiàn)兩個正整數(shù)的除法編程實現(xiàn)兩個正整數(shù)的除法，當(dāng)然不能用除法操作符。/ return x/y.div(constx, consty).10、在排序數(shù)組中，找出給定數(shù)字的出現(xiàn)次數(shù)比如 1, 2, 2, 2, 3 中 2

3、的出現(xiàn)次數(shù)是 3 次。11、平面上N 個點，每兩個點都確定一條直線，求出斜率最大的那條直線所通過的兩個點（斜率不存在的情況不考慮）。時間效率越高越好。12、一個整數(shù)數(shù)列，元素取值可能是 065535 中的任意一個數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。0 是例外，可以反復(fù)出現(xiàn)。請設(shè)計一個算法，當(dāng)你從該數(shù)列中隨意選取 5 個數(shù)值，判斷這 5 個數(shù)值是否連續(xù)相鄰。注意：5 個數(shù)值允許是亂序的。比如： 8 7 5 0 60 可以通配任意數(shù)值。比如：8 7 5 0 6 中的 0 可以通配成 9 或者 40 可以多次出現(xiàn)。復(fù)雜度如果是 O(n2)則不得分。13、設(shè)計一個算法，找出二叉樹上任意兩個結(jié)點的最近共同父結(jié)點。

4、復(fù)雜度如果是O(n2)則不得分。14、一棵排序二叉樹，令 f=(最大值+最小值)/2，設(shè)計一個算法，找出距離f 值最近、大于f 值的結(jié)點。復(fù)雜度如果是O(n2)則不得分。15、一個整數(shù)數(shù)列，元素取值可能是 1N（N 是一個較大的正整數(shù)）中的任意一個數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。設(shè)計一個算法，找出數(shù)列中符合條件的數(shù)對的個數(shù)，滿足數(shù)對中兩數(shù)的和等于 N+1。復(fù)雜度最好是O(n)，如果是 O(n2)則不得分。谷歌八道面試題16、正整數(shù)序列 Q 中的每個元素都至少能被正整數(shù)a 和b 中的一個整除，現(xiàn)給定a 和b，需要計算出Q 中的前幾項，例如，當(dāng) a=3，b=5，N=6 時，序列為 3，5，6，9，10，

5、12(1)、設(shè)計一個函數(shù) void generate（a,b,N ,* Q）計算 Q 的前幾項(2)、設(shè)計測試數(shù)據(jù)來驗證函數(shù)程序在各種輸入下的正確性。17、有一個由大小寫組成的字符串，現(xiàn)在需要對他進行修改，將其中的所有小寫字母排在答謝字母的前面（大寫或小寫字母之間不要求保持原來次序），可能盡量選擇時間和空間效率高的算法 c 語言函數(shù)原型void proc（char *str） 也可以采用你自己熟悉的語言18、如何隨機選取 1000 個關(guān)鍵字給定一個數(shù)據(jù)流，其中包含無窮盡的搜索關(guān)鍵字（比如，人們在谷歌搜索時不斷輸入的關(guān)鍵字）。如何才能從這個無窮盡的流中隨機的選取 1000 個關(guān)鍵字？19、判斷一

6、個自然數(shù)是否是某個數(shù)的平方說明：當(dāng)然不能使用開方運算。20、給定能隨機生成整數(shù) 1 到 5 的函數(shù)，寫出能隨機生成整數(shù) 1 到 7 的函數(shù)。21、1024! 末尾有多少個 0？22、有 5 個海盜，按照等級從 5 到 1 排列，最大的海盜提議他們?nèi)绾?00 枚金幣。但其他人要對此表決，如果多數(shù)，那他就會被殺死。他應(yīng)該提出怎樣的方案，既讓自己拿到盡可能多的金幣又不會被殺死？（提示：有一個海盜能拿到 98%的金幣）23、2009 華南地區(qū)筆試題給定一個集合A=0,1,3,8(該集合中的元素都是在 0，9 之間的數(shù)字，但未必全部包含)，指定任意一個正整數(shù) K，請用A 中的元素組成一個大于K 的最小正

7、整數(shù)。比如，A=1,0 K=21 那么輸出結(jié)構(gòu)應(yīng)該為 100。三道面試題24、用C 語言實現(xiàn)一個 revert 函數(shù)，它的功能是將輸入的字符串在原串上倒序后返回。25、用 C 語言實現(xiàn)函數(shù) void * memmove(void *dest, const void *src, size_t n)。memmove函數(shù)的功能是拷貝 src 所指的內(nèi)存內(nèi)容前 n 個字節(jié)到 dest 所指的地址上。分析：由于可以把任何類型的指針賦給 void 類型的指針，這個函數(shù)主要是實現(xiàn)各種數(shù)據(jù)類型的拷貝。26、有一根 27 厘米的細木桿，在第 3 厘米、7 厘米、11 厘米、17 厘米、23 厘米這五個位置上各有

8、一只螞蟻。木桿很細，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調(diào)頭，但不會后退。當(dāng)任意兩只螞蟻碰頭時，兩只螞蟻會同時調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。騰訊七道面試題27、請定義一個宏，比較兩個數(shù) a、b 的大小，不能使用大于、小于、if 語句28、兩個數(shù)相乘，小數(shù)點后位數(shù)沒有限制，請寫一個高精度算法29、有A、B、C、D 四個人，要在夜里過一座橋。他們通過這座橋分別需要耗時 1、2、5、10 分鐘，只有一支手電，并且同時最多只能兩個人一起過橋。請問，如何安排，能夠在 17分鐘內(nèi)這四個人都過橋

9、？30、有 12 個小球,外形相同,其中一個小球的質(zhì)量與其他 11 個不同，給一個天平,問如何用 3 次把這個小球找出來，并且求出這個小球是比其他的輕還是重31、在一個文件中有 10G 個整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。只寫出思路即可。32、一個文件中有 40 億個整數(shù)，每個整數(shù)為這個文件里的整數(shù)里不包含的一個整數(shù)節(jié)，內(nèi)存為 1GB，寫出一個算法：求出33、騰訊服務(wù)器每秒有 2w 個同時上線，找出 5min 內(nèi)重新登入的并打印出來。雅虎三道面試題34、編程實現(xiàn)：把十進制數(shù)(long 型)分別以二進制和十六進制形式輸出，不能使用 prf 系列35、編程實現(xiàn)：找出兩個字符串中最大

10、公共子字符串,如abccade,dgcadde的最大子串為cad36、有雙向循環(huán)鏈表結(jié)點定義為：struct nodedata;struct node *front,*next;有兩個雙向循環(huán)鏈表 A，B，知道其頭指針為：pHeadA,pHeadB，請寫一函數(shù)將兩鏈表中data 值相同的結(jié)點刪除。聯(lián)想五道筆試題37、1)、設(shè)計函數(shù)atoi(char *s)。2)、i=(j=4,k=8,l=16,m=32); prf(“%d”, i); 輸出是多少？、解釋局部變量、全局變量和靜態(tài)變量的含義。、解釋堆和棧的區(qū)別。、論述含參數(shù)的宏與函數(shù)的優(yōu)缺點。38、順時針打印矩陣題目：輸入一個矩陣，按照從外向里以

11、順時針的順序依次打印出每一個數(shù)字。例如：如果輸入如下矩陣：15913261014371115481216則依次打印出數(shù)字 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。分析：包括Autodesk、EMC 在內(nèi)的多家公司在面試或者筆試?yán)锊捎眠^這道題。39、對稱子字符串的最大長度題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出 4。分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。40、用 1、2、2、3、4、

12、5 這六個數(shù)字，寫一個main 函數(shù)，打印出所有不同的排列，如：512234、412345 等，要求：4不能在第三位，3與5不能相連.41、微軟面試題一個有序數(shù)列，序列中的每一個值都能夠被 2 或者 3 或者 5 所整除，1 是這個序列的第一個元素。求第 1500 個值是多少？網(wǎng)易五道筆試題42、兩個圓相交，交點是A1，A2?，F(xiàn)在過 A1 點做一直線與兩個圓分別相交另外一點B1，B2。B1B2 可以繞著A1 點旋轉(zhuǎn)。問在什么情況下，B1B2 最長43、Smith 夫婦召開宴會，并邀請其他 4 對夫婦參加宴會。在宴會上，他們彼此握手，并且滿足沒有一個人同自己握手，沒有兩個人握手一次以上，并且夫妻

13、之間不握手。然后 Mr. Smith 問其它客人握手的次數(shù)，每個人的是不一樣的。求 Mrs Smith 握手的次數(shù)44、有 6 種不同顏色的球，分別記為 1,2,3,4,5,6，每種球有無數(shù)個。現(xiàn)在取 5 個球，求在一下的條件下：1、5 種不同顏色，2、4 種不同顏色的球，3、3 種不同顏色的球，4、2 種不同顏色的球，它們的概率。45、有一次數(shù)學(xué)比賽，共有 A，B 和C 三道題目。所有人都至少解答出一道題目，總共有25 人。在沒有答出A 的人中，答出 B 的人數(shù)是答出C 的人數(shù)的兩倍；單單答出 A 的人，比其他答出 A 的人總數(shù)多 1；在所有只有答出一道題目的人當(dāng)中，答出 B 和C 的人數(shù)剛

14、好是一半。求只答出B 的人數(shù)。46、從尾到頭輸出鏈表題目：輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：struct ListNodem_nKey; ListNode* m_pNext;分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。47、金幣概率問題（威盛筆試題）題目：10 個房間里放著隨機數(shù)量的金幣。每個房間只能進入一次，并只能在一個房間中拿金幣。一個人采取如下策略：前四個房間只看不拿。隨后的房間只要看到比前四個房間都多的金幣數(shù)，就拿。否則就拿最后一個房間的金幣。?編程計算這種策略拿到最多金幣的概率。48、找出數(shù)組中唯一的重復(fù)元

15、素1-1000 放在含有 1001 個元素的數(shù)組中，只有唯一的一個元素值重復(fù)，其它均只出現(xiàn)一次每個數(shù)組元素只能一次，設(shè)計一個算法，將它找出來；不用輔助空間，能否設(shè)計一個算法實現(xiàn)？49、08校園招聘的一道筆試題題目大意如下：一排N（最大）個正整數(shù)+1 遞增，亂序排列，第一個不是最小的，把它換成-1，最小數(shù)為且未知求第一個被-1 替換掉的數(shù)原來的值，并分析算法復(fù)雜度。50、一道 SPSS 筆試題求解題目：輸入四個點的坐標(biāo)，求證四個點是不是一個矩形關(guān)鍵點：1.相鄰兩邊斜率之積等于-1，矩形邊與坐標(biāo)系平行的情況下，斜率無窮大不能用積判斷。輸入四點可能不按順序，需要對四點排序。51、矩陣式螺旋輸出52、

16、求兩個或N 個數(shù)的最大公約數(shù)和最小公倍數(shù)。53、最長遞增子序列題目描述：設(shè) L=是 n 個不同的實數(shù)的序列，L 的遞增子序列是這樣一個子序列Lin=，其中 k1k2km 且 aK1ak2akm。求最大的m 值。54、字符串原地壓縮題目描述：“eeeeeaaaff 壓縮為 e5a3f2，請編程實現(xiàn)。55、字符串匹配實現(xiàn)請以倆種方法，回溯與不回溯算法實現(xiàn)。56、一個含n 個元素的整數(shù)數(shù)組至少存在一個重復(fù)數(shù)，請編程實現(xiàn)，在 O（n）時間內(nèi)找出其中任意一個重復(fù)數(shù)。57、求最大區(qū)間大小題目描述：請編寫程序，找出下面“輸入數(shù)據(jù)及格式”中所描述的輸入數(shù)據(jù)文件中最大間的大小。區(qū)對一個正整數(shù) n ，如果n 在數(shù)

17、據(jù)文件中某行的兩個正整數(shù)（假設(shè)為A 和B）之間，即A=n=n=B ，則 n 屬于該行；如果 n 同時屬于行i 和 j ，則i 和j 有數(shù)個數(shù)。區(qū)間；區(qū)間的大小是同時屬于行 i 和j 的整例如，行（10 20）和（12 25）的區(qū)間為 12 20 ，其大小為 9，行(20 10)和（ 20 30 ）區(qū)間大小為 1 。的58、整數(shù)的素數(shù)和分解問題猜想說任何一個不小于 6 的偶數(shù)都可以分解為兩個奇素數(shù)之和。對此問題擴展，如果一個整數(shù)能夠表示成兩個或多個素數(shù)之和，則得到一個素數(shù)和分解式。對于一個給定的整數(shù)，輸出所有這種素數(shù)和分解式。注意，對于同構(gòu)的分解只輸出一次（比如 5 只有一個分解 2 + 3，而

18、 3 + 2 是 2 + 3 的同構(gòu)分解式）。例如，對于整數(shù) 8，可以作為如下三種分解： (1) 8 = 2 + 2 + 2 + 2(2) 8 = 2 + 3 + 3(3) 8 = 3 + 559、的一道面試題題目：輸入 a1,a2,.,an,b1,b2,.,bn,在 O(n)的時間,O(1)的空間將這個序列順序改為 a1,b1,a2,b2,a3,b3,.,an,bn，且不需要移動，通過交換完成，只需一個交換空間。例如，N=9 時，第 2 步執(zhí)行后，實際上中間位置的兩邊對稱的 4 個元素基本配對，只需交換中間的兩個元素即可，如下表所示。顏色表示每次要交換的元素,左邊向右交換,右邊向左交換。交換

19、過程如下表所示1.2.3.4.5.6.7.交換 x1,x3；交換 x2,x4；再交換中間的 x1,x4；交換 y1,y2。60、筆試題給定一個存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。要求：空間復(fù)雜度 O(1)，時間復(fù)雜度為 O（n）。微軟、等公司一些非常好的面試題、第 61-70 題61、騰訊現(xiàn)場招聘問題liuchen1206今天參加了騰訊的現(xiàn)場招聘會，碰到這個一個題目：在一篇英文文章中查找指定的人名，人名使用二十六個英文字母（可以是大寫或小寫）、空格以及兩個通配符組成（*、?），通配符“*”表示零個或多個任意字母，通配符“?”表示一個任意字母。如：“J* Smi?” 可以

20、匹配“John Smith” .請用C 語言實現(xiàn)如下函數(shù)：void scan(const char* pszText, const char* pszName);注：pszText 為整個文章字符，pszName 為要求匹配的英文名。請完成些函數(shù)實現(xiàn)輸出所有匹配的英文名，除了 prf 外，不能用第的庫函數(shù)等。代碼一（此段代碼已經(jīng)多個網(wǎng)友，bug 不少，但暫沒想到解決辦法）：1.代碼二：8.#include using namespatd; 11.12.scan(const char* text, const char* pattern)13. const char *p = pattern;i

21、f (*pattern = 0) return 1;if (*text = 0) return 0; 17.18.if (*pattern != * & *pattern != ?)19.if (*text != *pattern)return scan(text+1, pattern);22.23.24.if (*pattern = ?)25.26.if (!isalpha(*text)27.pattern = p;return scan(text+1, pattern);30.31.else32.33.return scan(text+1, pattern + 1);34.35.36.re

22、turn scan(text, pattern+1);37. 38.39.main()40. char *i, *j;i = new char100;j = new char100;cinij;coutscan(i,j);return 0;47. 2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.#include using namespatd;const char *pEnd=NULL;bool

23、match(const char *pszText,const charif(*pszName = /0)pEnd=pszText; return true;*pszName)if(*pszText = /0)if(*pszName = *)pEnd=pszText; return true;return false;if(*pszName!= * & *pszName!=?)if(*pszText = *pszName)return match(pszText+1,pszName+1);return false;elseif(*pszName = *)return match(pszText

24、,pszName+1)|match(pszText+1,pszName);elsereturn match(pszText+1,pszName+1);wangxugangzy05：這個是kmp 子串搜索（匹配），稍加改造，如 abcabd*?abe*?de 這個竄， 可以分成 abcabd,?,abe,?,?,并按順序先匹配 abcabd，當(dāng)匹配后，將匹配的文章中地址及匹配的是何子串放到棧里 下來，這樣，每次匹配都入棧保存當(dāng)前子串匹配信息，當(dāng)一次完整的全部子串都匹配完后，就輸出一個匹配結(jié)果，然后回溯一下，開始對棧頂?shù)淖哟倪M行文中下一個起始位置的匹配。62、微軟三道面試題yeardoubleh

25、ua1. 給一個有N 個整數(shù)的數(shù)組 S.和另一個整數(shù) X，判斷 S 里有沒有 2 個數(shù)的和為X，請設(shè)計成 O（n*log2(n)）的算法。46. 47.48. void scan(const char *pszText, const char *pszName)49. 50.while(*pszText!=/0)51.52.if(match(pszText,pszName)53.54.while(pszText!=pEnd)55.56.cout*pszText+;57.58.59.coutendl;60.61.return;62.63. 64.65.main()66. 67.char pszT

26、ext100,pszName100; 68.fgets(pszText,100,stdin);fgets(pszName,100,stdin);scan(pszText,pszName); 72.73.return 0;74. #include #include #include using namespatd;typedef pair Pair; 6.7. Pair findSum(*s,n,x) 8. 9.sort(); 10.11.*begin=s;12.*end=s+n-1; 13.14.whieginx)17.18.-end;19.20.else if(*begin+*endx)21

27、.22.+begin;23.24.else25.26.return Pair(*begin,*end);27.28.29.30.return Pair(-1,-1);31. 32.33.main()34. 35.arr100=36.有 2 個數(shù)組.里面有 N 個整數(shù)。設(shè)計一個算法O(n log2(n)，看是否兩個數(shù)組里存在一個同樣的數(shù)。讓你排序N 個比N7 小的數(shù)，要求的算法是 O(n)（給了提示.說往 N 進制那方面想）：1,快排,頭尾.#include #include using namespatd; 4.5. bool findSame(const*a,len1,const*b,len

28、2,*result) 6. 7.i,j;8.i=j=0;9.10.while(ilen1 & jlen2)11.12.if(aibj)17.18.+j;19.20.else21.*result=ai;return true;24.25.26.return false;27. 28.2,快排,線性掃描37.3, -4, 7, 8, 12, -5, 0, 938.;39.40.n=8,x;41.42.while(cinx)43.Pair ret=findSum(arr,n,x);coutret.,ret.secondendl;46.47.48.return 0;49. 3,基數(shù)排序已經(jīng)可以 O(n

29、)了,準(zhǔn)備 10 個 vector,從最低位數(shù)字開始,放入相應(yīng)的桶里,然后再順序取出來,然后再從次低位放入相應(yīng)桶里,在順序取出來.比如：N=5，分別是： 4,10,7,123,330 ：10123 ：123,334 ：4567 ：789順次取出來：10,123,33,4,7 0 ：4,71 ：1029.main()30. 31.a100,b100,len1,len2,result;32.cinlen1; 33.34.for(i=0;iai;37.38.39.cinlen2;40.for(i=0;ibi;43.44.45.if( findSame(a,len1,b,len2,&result) )

30、46.47.coutresultendl;48.49.return 0;50. #include #include #include #include 5.6. using namespatd; 7.size_t n;size_t maxLen=0;vector queue vec(10);vector result; 12.13. void sort()14. 2 ：1233 ：33456789依次取出來：4,7,10,123,33 0 ：4,7，10，331 ：12323456789依次取出來：4,7,10,33,123完畢。代碼，如下：15.16.17.18.19.20.21.22.23

31、.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40. 41. 42.43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57.58.for(size_t i=0;imaxLen;+i)for(size_t j=0;j=resultj.length() )vec0.push(resultj);elsevec resultjresultj.length()-1-i-0.push(resultj);result.clear();for(size_t k=0;kn;string input;

32、for(size_t i=0;iinput; result.push_back(input);if(maxLen = 0 | input.length()maxLen)maxLen=input.length();alex：第一題，1. 給一個有N 個整數(shù)的數(shù)組S.和另一個整數(shù)X，判斷 S 里有沒有 2 個數(shù)的和為X，請設(shè)計成 O（n*log2(n)）的算法。如果限定復(fù)雜度 nlgn 的話就不能用快排?？梢杂脷w并排序，然后 Y=X-E，用兩分搜索依次查找每一個 Y 是否存在，保證 復(fù)雜度為 nlgn.63、微軟亞洲hinyunsin假設(shè)有一顆二叉樹，已知這棵樹的節(jié)點上不均勻的分布了若干石頭，石頭

33、數(shù)跟這棵二叉樹的節(jié)點數(shù)相同，石頭只可以在子節(jié)點和父節(jié)點之間進行搬運，每次只能搬運一顆石頭。請問如何以最少的步驟將石頭搬運均勻，使得每個節(jié)點上的石頭上剛好為 1。個人，暫時還沒看到清晰的，更好的思路，以下是網(wǎng)友mathe、casahama、Torey 等人給的思路：mathe：對于任意一個節(jié)點，可以查看其本身和樹，右的幾個信息: i)本身上面石子數(shù)目樹中石子數(shù)目和節(jié)點數(shù)目的差值右中石子數(shù)目和節(jié)點數(shù)目的差值通過 i),ii),iii)可以計算出除掉這三部份其余節(jié)點中石子和節(jié)點數(shù)目的差值。如果上面信息都已經(jīng)計算出來，那么對于這個節(jié)點，就可以計算出同其關(guān)聯(lián)三條邊石子運送最小數(shù)目。比如，如果樹石子數(shù)目和

34、節(jié)點數(shù)目差值為 a0,那么表示必須通過這個節(jié)點通向左的邊反向運送a 個石子。同樣可以計算出同父節(jié)點之間的最小運送數(shù)目。59.sort(); 60.61.for(size_t i=0;in;+i)62.63.coutresulti ;64.65.66.cout前序遍歷樹-前序遍歷右前序遍歷，遞歸算法void preorder(bree t)/注，bree 為一指向二叉樹根結(jié)點的指針if(t)prf(%c,t-data); preorder(t-lchild); preorder(t-rchild);2.中序遍歷，遞歸算法 void preorder(bree t)if(t)inorder(t-l

35、child);prf(%c,t-data); inorder(t-rchild);3.后序遍歷，遞歸算法 void preorder(bree t)if(t)torder(t-lchild); torder(t-rchild);prf(%c,t-data);關(guān)于實現(xiàn)二叉樹的前序、中序、后序遍歷的遞歸與非遞歸實現(xiàn)，的，請參考這（微軟100 題第 43 題）：。64、淘寶校園筆試題goengineN 個雞蛋放到 M 個籃子中，籃子不能為空，要滿足：對任意不大于 N 的數(shù)量，能用若干個籃子中雞蛋的和表示。寫出函數(shù)，對輸入整數(shù)N 和 M，輸出所有可能的雞蛋的放法。比如對于 9 個雞蛋 5 個籃子解至少

36、有三組：1 2 4 1 11 2 2 2 21 2 3 2 1思路一、Sorehead 在微軟 100 題，地址上，已經(jīng)對此題有了詳細的思路與闡釋，以下是他的個人思路+代碼：Sorehead思路：1、由于每個籃子都不能為空，可以轉(zhuǎn)換成每個籃子先都有 1 個雞蛋，再對剩下的 N-M個雞蛋進行分配，這樣就可以先求和為N-M 的所有排列可能性。2、假設(shè)N-M=10，求解所有排列可能性可以從一個比較簡單的遞規(guī)來實現(xiàn)，轉(zhuǎn)變?yōu)橄铝袛?shù)組：(10,0)、(9,1)、(8,2)、(7,3)、(6,4)、(5,5)、(4,6)、(3,7)、(2,8)、(1,9)這里對其中第一個元素進行循環(huán)遞減，對第二個元素進行上

37、述遞規(guī)重復(fù)求解，例如(5,5)轉(zhuǎn)變成：(5,0)、(4,1)、(3,2)、(2,3)、(1,4)由于是求所有排列可能性，不允許有重復(fù)，因此結(jié)果就只能是非遞增或者非遞減隊列，這里我采用的非遞增隊列來處理。3、上面的遞規(guī)過程中對于像(4,6)這樣的不符合條件就可以跳過不輸出，但遞規(guī)不能直接跳出，必須繼續(xù)進行下去，因為(4,6)的結(jié)果集中還是有不少能符合條件的。我寫的是非遞規(guī)程序，因此(4,6)這樣的組合我就直接轉(zhuǎn)換成 4,4,2，然后再繼續(xù)做處理。4、N-M 的所有排列可能性已經(jīng)求出來了，里面的元素全部加 1，如果 N-MM，剩下的元素就全部是 1，這樣 N 個雞蛋放入 M 個籃子的所有可能性就全

38、部求出來了。注意排列中可能元素數(shù)量會超過籃子數(shù)量 M，去除這樣的排列即可。1.2. void malloc_egg(m,n) 3. *stack, top;count, max, flag, i; 6.7.if (m 1 | n n)8.return;9.10.11.i = n / 2;count = 1;while (i 0)14.15.i /= 2;16.count+;17.if (m = n - 1)23.24.if (m = n)25.prf(1,);26.else27.prf(2,);28.for (i = 0; i N，顯而易見這是不可能有結(jié)果的；那對于給定的N 值，M 是否不能小

39、于某個值呢，是肯定的。6、對于給定的 N 值，M 值最小的組合應(yīng)該是 1,2,4,8,16,32.這樣的序列，這樣就可以計算出 M 的最小值可能了，如果 M 小于該值，也是不可能有結(jié)果的。7、接下來，對于給定的結(jié)果集，由于有個籃子的雞蛋數(shù)量必須為 1，可以先去掉最小值大于 1 的；同樣，籃子中雞蛋最大數(shù)量也應(yīng)該過某值，該值應(yīng)該在 N/2 左右，具體值要看N 是奇數(shù)還是偶數(shù)了，原因是因為超過這個值，其它籃子的雞蛋數(shù)量全部相加都無法得到比該值小 1 的數(shù)。8、最后如何保證剩下的結(jié)果中都是符合要求的，這是個難題。當(dāng)然有個簡單方法就是對結(jié)果中的每個數(shù)挨個進行判斷。29.30.31.32.33.34.3

40、5.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.prf(1,);prf(/n);return;if (stack = malloc(sizeof(return;) *(n -m)= NULL)stack0 = n - m;top = 0;max = n % 2 ? n / 2 : n / 2 - 1;if(stack0 = max)prf(%d, n - m + 1);for (i = 1; i = 0 & stack

41、i = 1; count+;i-)if(count 0)top -= count;stacktop-; count+;while (stacktop N/2 時，似乎滿足條件一的所有組合都是滿73.stack+top = 1;74.75.76.if (top = m - 1)continue;if (stack0 max)continue;flag = 0;count = m - top;85.for (i = top; i = 0; i-)86.87.if (stacki = count)88.flag = 1;break;91.92.count += stacki + 1;93.if (f

42、lag)continue;98.for (i = 0; i m; i+)99.100.if (i 1); 108.109.free(stack);110.1.2.3.#include using namespatd; 6. long220;7.N,M;8.ans1000;9. void solve(n ,m ,Min )10. 11.if(n = N & m = M)12.13.for(i=1;i=M;i+)14.15.coutansi ;16.cout N | N 2M-m*n +2M-m-1)return ;else足條件二的；當(dāng) N=(2 的n 次方-1)，M=n 時，結(jié)果只有一個，就是

43、 1、2、4、.(2 的 n-1次方)，應(yīng)該可以根據(jù)這個對其它結(jié)果進行推導(dǎo)。3、這種方法是先根據(jù)條件一得到所有可能性，然后在這個結(jié)果集中去除不符合條件二的，感覺效率不是很好。個人覺得應(yīng)該有辦法可以直接把兩個條件一起考慮，靠某種方式主動推出結(jié)果，而不是我現(xiàn)在采用的篩選方式。其實我剛開始就是想采用這種方式，但得到的結(jié)果集中總是缺少一些了排列可能。思路二、以下是暉的個人思路：N 個雞蛋分到 M 個籃子里(NM),不能有空籃子，對于任意不大于于 N 的數(shù)，保證有幾個籃子的雞蛋數(shù)和等于此數(shù)，編程實現(xiàn)輸入 N，M 兩個數(shù)，輸出所有雞蛋的方法。1、全輸出的話本質(zhì)就是搜索+剪枝。2、(n,m,min)表示當(dāng)前

44、狀態(tài)，按照籃子里蛋的數(shù)目從小到大搜索。搜到了第 m 個籃子，1.m 個籃子面共放了 n 個蛋，當(dāng)前的籃子放了min 個蛋。下一個擴展(n+t,m+1,t),for t=min.n+1。當(dāng) n+(M-m)*minN (雞蛋不夠時)或者 2(M-m)*n+2(M-m)-1N（雞蛋太多）時 把這個枝剪掉；3、太多時的情況如下： n,n+1,2n+2,4n+4,8n+8.。代碼如下：此思路二來自：/archive/2011/03/30/6290131.aspx。65、面試char *str = AbcABca;寫出一個函數(shù)，查找出每個字符的個數(shù)，區(qū)分大小寫，要求時間復(fù)雜度是 n（提示用 ASC碼）1.

45、 #include 2.3.main(argc, char* argv) 4. 5.char *str = AbcABca;很基礎(chǔ)，也比較簡單的一題，看下這位網(wǎng)友給的代碼吧：nlqlove：23.24.for(i = Min; i = n+1; i+)25.26.ansm+1 = i;27.solve(n+i,m+1,i);28.29.30.31. 32.33.main()34. 35.20 = 1;36.for(i=1;i20;i+)37.38.2i =2i-1NM;41.if( M N |2M-1 N)42.43.cout沒有這樣的組合endl;44.45.solve( 0 , 0 , 1

46、 );system(pause);return 0;48. 66、微軟面試題 yaoha2003請把一個整形數(shù)組中重復(fù)的數(shù)字去掉。例如：1,2,應(yīng)該是： 2，0,2,-1,999,3,999,881,0，-1，999，3，88#include #include using namespatd; 4.template void CalcAllPermuion_R(T perm,num)67、請編程實現(xiàn)全排列算法。全排列算法有兩個比較常見的實現(xiàn)：遞歸排列和字典序排列。yysdsyl：（1）遞歸實現(xiàn)從集合中依次選出每一個元素，作為排列的第一個元素，然后對剩余的元素進行全排列，如此遞歸處理，從而得到所

47、有元素的全排列。算法實現(xiàn)如下：6.count256 = 0;7.8.for (char *p=str; *p; p+) 9.10.count*p+;11.12.13.14.for (i=0; i 0)17.18.prf(The count of %c is: %d/n,i, counti);19.20.21.return 0;22. 程序運行結(jié)果（優(yōu)化）：-bash-3.2$ g+ test.cpp -O3 -o ttt-bash-3.2$ time ./tttreal 0m10.556s user 0m10.551s sys 0m0.000s程序運行結(jié)果（不優(yōu)化）：-bash-3.2$ g+

48、 test.cpp -o ttt-bash-3.2$ time ./tttreal 0m21.355s user 0m21.332s sys 0m0.004s（2）字典序排列7. 8.if (num = 1) 9.return;10.11.12.for (i =; i + num; +i) swap(permi, perm);CalcAllPermuion_R(perm,+ 1, num - 1);swap(permi, perm);16.17. 18.19.main()20. constNUM = 12;char permNUM; 23.for (i = 0; i NUM; +i)permi

49、 = a + i; 26.27.CalcAllPermuion_R(perm, 0, NUM);28. ，#include #include using namespatd; 4.template void CalcAllPermuion(T perm,num) 7. if (num = 0; -i) if (permi permi + 1)break;16.17.18.if (i i; -k) if (permk permi)break;25.26.swap(permi, permk);reverse(perm + i + 1, perm + num); 29.30.31. 32.33.ma

50、in()34. 把升序的排列（當(dāng)然，也可以實現(xiàn)為降序）作為當(dāng)前排列開始，然后依次計算當(dāng)前排列的下一個字典序排列。對當(dāng)前排列從后向前掃描，找到一對為升序的相鄰元素，記為 i 和 j（i j）。如果不存在這樣一對為升序的相鄰元素，則所有排列均已找到，算法結(jié)束；否則，重新對當(dāng)前排列從后向前掃描，找到第一個大于i 的元素k，交換i 和k，然后對從 j 開始到結(jié)束的子序列反轉(zhuǎn)，則此時得到的新排列就為下一個字典序排列。這種方式實現(xiàn)得到的所有排列是按字典序有序的這也是 C+ STL 算法 next_permu ion 的 。算法實現(xiàn)如下：#include #include using namespatd;

51、4.template size_t CalcAllPermuion(T perm,num) 7. if (num 1)return 0; 10.size_t count = 0;while (next_permuion(perm, perm + num) 13.+count; 14.程序運行結(jié)果（優(yōu)化）：-bash-3.2$ g+ test.cpp -O3 -o ttt-bash-3.2$ time ./tttreal 0m3.055s user 0m3.044s sys 0m0.001s程序運行結(jié)果（不優(yōu)化）：-bash-3.2$ g+ test.cpp -o ttt-bash-3.2$ time ./tttreal 0m24.367s user 0m24.321s sys 0m0.006s使用 std:next_permuion 來進行對比測試，代碼如下：constNUM = 12;char permNUM; 37.for (i = 0; i NUM; +i)permi = a + i; 40.41.CalcAllPermuion(perm, NUM);42. 程序運行結(jié)果（優(yōu)化）：-bash-3.2$ g+ test.cpp -O3 -o ttt-bash-3.2$ time ./tttreal 0m3.606s user 0m3.601s sys 0m0.002s