【正文】 數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。？為什么不用hash？說明為什么你會選擇用這樣的方法？。？分析：主要在基本概念上的理解。(非空結(jié)點)，在p前面插入一個結(jié)點。此時，原單鏈表可以看作兩條單鏈表，一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。 如果head1==head2，那么顯然相交，直接返回head1。(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應(yīng)能力，對數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實的編程功底。圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。題目：有一個復(fù)雜鏈表，其結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外，還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。要幾十分鐘的時間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應(yīng)和較強的邏輯思維能力。分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。 result *= base。 i = exponent。可能有不少的人在看到題目后30秒寫出如下的代碼：double Power(double base, int exponent){。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)，還有逆序生成排列和一些不需要遞歸生成排列的方法。但這個思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。請給出解決問題的算法，并證明該算法。 。比如輸入3，則輸出3一直到最大的3位數(shù)即999。求按從小到大的順序的第1500個丑數(shù)。64. 尋找丑數(shù)。例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個字符串變成”Thy r stdnts.”。微軟非常喜歡與鏈表相關(guān)的題目，因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。鏈表的結(jié)點定義為：struct ListNode{分析：這是一道很新穎的關(guān)于位運算的面試題。 m_pNext。題目：給定鏈表的頭指針和一個結(jié)點指針，在O(1)時間刪除該結(jié)點。這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。 ListNode* m_pNext。 int}。 node)。 題目：某隊列的聲明如下：templatetypename T class CQueue{public:例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，則輸出它們的長度4，并打印任意一個子串。 char* m_pData。 CMyStringamp。 str)。55.題目：類CMyString的聲明如下：class CMyString{public:。題目：輸入一個字符串，打印出該字符串中字符的所有排列。 // right child of node}。 m_nValue。 16輸出該樹的深度3。 12 4 \ /例如：輸入二元樹：。 {3,6}{2,4,3} m=2：，存在一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）某一個元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個全零矩陣經(jīng)過上述運算得到。，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤，照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，若匹配不過，照相機則按測好的晶元間距移到下一個位置。要求：引用自：zp1553348771)設(shè)計一個棧結(jié)構(gòu)，滿足一下條件：min，push，pop操作的時間復(fù)雜度為O(1)。，如何從中去除重復(fù)的，優(yōu)化時間空間復(fù)雜度37.有n個長為m+1的字符串，如果某個字符串的最后m個字符與某個字符串的前m個字符匹配，則兩個字符串可以聯(lián)接，問這n個字符串最多可以連成一個多長的字符串，如果出現(xiàn)循環(huán)，則返回錯誤。n1，已知它們之間的實力對比關(guān)系，存儲在一個二維數(shù)組w[n][n]中，w[i][j] 的值代表編號為i，j的隊伍中更強的一支。35.求一個矩陣中最大的二維矩陣(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)寫出算法。32.有兩個序列a,b，大小都為n,序列元素的值任意整數(shù)，無序；要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。因為可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop序列就是1。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應(yīng)的pop順序。分析：這是一道很基本的考查位運算的面試題。這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。例如：abcd12345ed125ss123456789的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789如果用程序，又怎么實現(xiàn)呢？因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。 求出在這個圓圈中剩下的最后一個數(shù)字。 分析：這道題是2006年google的一道筆試題。 BSTreeNode *m_pLeft。10 6/\ /\5 7 9 11輸出： 例如輸入：要求時間復(fù)雜度是O(n)。 ListNode* m_pNext。鏈表結(jié)點定義如下：第12題題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。 11因此返回true。 / \ 10 /此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。優(yōu)化速度。優(yōu)化速度。　　★用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。有什么辦法呢？，你要用一根金條作為報酬。第8題此貼選一些 比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。 第6題騰訊面試題： 給你10分鐘時間，根據(jù)上排給出十個數(shù)，在其下排填出對應(yīng)的十個數(shù) 要求下排每個數(shù)都是先前上排那十個數(shù)在下排出現(xiàn)的次數(shù)。 // left child of nodeBinaryTreeNode *m_pRight。打印出和與輸入整數(shù)相等的所有路徑。要求時間復(fù)雜度為O(n)。要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。 // left child of node BSTreeNode *m_pRight。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。由他們自己來認(rèn)定。從2010年10月11日當(dāng)天最初發(fā)表前40題以來，直至此刻，整理這100題，已有近2個月。================作者:July 2010年12月6日。這微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題系列(是的，系列)，到底現(xiàn)在、或此刻、或未來，對初學(xué)者有多大的意義，在此，我就不給予評說了。 題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。 // value of node BSTreeNode *m_pLeft。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。求所有子數(shù)組的和的最大值。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。 // value of nodeBinaryTreeNode *m_pLeft。例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。問題擴展：??現(xiàn)在要求受訓(xùn)者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。現(xiàn)在在不用遞歸式的情況下做一遍?！　　镱嵉挂粋€字符串?！　　镎业揭粋€子字符串?！　　锛僭O(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間?，F(xiàn)在用同樣的方法增加7倍。例如輸入18，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果： 8 / \ 7 9第10題翻轉(zhuǎn)句子中單詞的順序。例如輸入“I am a student.”，則輸出“student. a am I”。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。第14題：題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。由于4+11=15，因此輸出4和11。 6 10 / \ // value of node // right child of node}。 例如輸入6 10/ \ / \5 7 9 11輸出8 6 10 5 7 9 11。當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。第19題：題目：定義Fibonacci數(shù)列如下：分析：在很多C語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci作為例子。例如輸入字符串345，則輸出整數(shù)345。請教如何推理，A是怎么知道的。 3D坐標(biāo)系 原點(,)圓形:半徑r = 圓心o = (*.*, , *.*)正方形:4個角坐標(biāo)。第25題：寫一個函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)功能：在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。求總共有多少總跳法，并分析算法的時間復(fù)雜度。例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。、pop序列題目：輸入兩個整數(shù)序列。 比如輸入的push序列是5，那么1就有可能是一個pop系列。題目：輸入一個整數(shù)n，求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。：一類似于蜂窩的結(jié)構(gòu)的圖，進行搜索最短路徑（要求5分鐘）var b=[1, 2, 3, 4,5,40]。(2)分析時間復(fù)雜度。所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中，比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是 4對3， 5對8。39.網(wǎng)易有道筆試：(1).求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數(shù)，比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。2)一串首尾相連的珠子(m個)，有N種顏色(N=10)，設(shè)計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。 *系統(tǒng)每秒的查詢數(shù)量可能上千次；求遍歷晶