1、1.把二元查找樹轉(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 BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node;/引用 245 樓 tree_star 的

2、回復(fù)#include #include struct BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node;typedef BSTreeNode DoubleList;DoubleList * pHead;DoubleList * pListIndex;void convertToDoubleList(BSTreeNode * pCurrent);/ 創(chuàng)建二元查找樹void addBSTreeNo

3、de(BSTreeNode * & pCurrent, int value) if (NULL = pCurrent) BSTreeNode * pBSTree = new BSTreeNode(); pBSTree-m_pLeft = NULL; pBSTree-m_pRight = NULL; pBSTree-m_nValue = value; pCurrent = pBSTree; else if (pCurrent-m_nValue) value) addBSTreeNode(pCurrent-m_pLeft, value); else if (pCurrent-m_nValue) m

4、_pRight, value); else /cout重復(fù)加入節(jié)點(diǎn)m_pLeft) ergodicBSTree(pCurrent-m_pLeft); / 節(jié)點(diǎn)接到鏈表尾部 convertToDoubleList(pCurrent); / 右子樹為空 if (NULL != pCurrent-m_pRight) ergodicBSTree(pCurrent-m_pRight); / 二叉樹轉(zhuǎn)換成listvoid convertToDoubleList(BSTreeNode * pCurrent) pCurrent-m_pLeft = pListIndex; if (NULL != pListIn

5、dex) pListIndex-m_pRight = pCurrent; else pHead = pCurrent; pListIndex = pCurrent; coutm_nValue NULL (MIN=10, POS=0)1: 7 - 0 (MIN=7, POS=1) 用數(shù)組表示堆棧，第0個(gè)元素表示棧底2: 3 - 1 (MIN=3, POS=2)3: 3 - 2 (MIN=3, POS=3)4: 8 - NULL (MIN=3, POS=3) 技巧在這里，因?yàn)?比當(dāng)前的MIN大，所以彈出8不會(huì)對當(dāng)前的MIN產(chǎn)生影響5：5 - NULL (MIN=3, POS=3)6: 2 - 2

6、(MIN=2, POS=6) 如果2出棧了，那么3就是MIN7: 6 - 6出棧的話采用類似方法修正。 所以，此題的第1小題，即是借助輔助棧，保存最小值，且隨時(shí)更新輔助棧中的元素。如先后，push 2 6 4 1 5stack A stack B（輔助棧）4: 5 1 /push 5,min=p-3=1 3: 1 1 /push 1,min=p-3=1 | /此刻push進(jìn)A的元素1小于B中棧頂元素22: 4 2 /push 4,min=p-0=2 |1: 6 2 /push 6,min=p-0=2 |0: 2 2 /push 2,min=p-0=2 |push第一個(gè)元素進(jìn)A，也把它push進(jìn)

7、B，當(dāng)向Apush的元素比B中的元素小， 則也push進(jìn)B，即更新B。否則，不動(dòng)B，保存原值。向棧A push元素時(shí)，順序由下至上。輔助棧B中，始終保存著最小的元素。然后，pop棧A中元素，5 1 4 6 2 A B -更新 4: 5 1 1 /pop 5,min=p-3=1 |3: 1 1 2 /pop 1,min=p-0=2 |2: 4 2 2 /pop 4,min=p-0=2 |1: 6 2 2 /pop 6,min=p-0=2 |0: 2 2 NULL /pop 2,min=NULL v當(dāng)pop A中的元素小于B中棧頂元素時(shí)，則也要pop B中棧頂元素。3.求子數(shù)組的最大和題目：輸入一

8、個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。/July 2010/10/18#include int maxSum(int* a, int n) int sum=0; int b=0; for(int i=0; in; i+) if(b0) b=ai; else b+=ai; if(sumb) sum=b; return sum;int main

9、() int a10=1,-8,6,3,-1,5,7,-2,0,1; coutmaxSum(a,10)endl; return 0;運(yùn)行結(jié)果，如下：20Press any key to continue-int maxSum(int* a, int n) int sum=0; int b=0; for(int i=0; in; i+) if(b=0) /此處修正下，把b0改為 b=0 b=ai; else b+=ai; if(sumb) sum=b; return sum;/解釋下：例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，那么最大的子數(shù)組為3, 10, -4, 7

10、, 2，因此輸出為該子數(shù)組的和18所有的東西都在以下倆行，即： b：0 1 -1 3 13 9 16 18 7 sum：0 1 1 3 13 13 16 18 18其實(shí)算法很簡單，當(dāng)前面的幾個(gè)數(shù)，加起來后，bsum，則更新sum=b;若bsum，則sum保持原值，不更新。:)。July、10/31。/關(guān)于第4題，當(dāng)訪問到某一結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動(dòng)回到父結(jié)點(diǎn)。因此我們在函數(shù)退出之前要在路徑上刪除

11、當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個(gè)棧結(jié)構(gòu)，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過程。void FindPath( BinaryTreeNode* pTreeNode, / a node of binary tree int expectedSum, / the expected sum std:vector& path, / a path from root to current node int& currentSum / the sum of path) if(!pTreeNo

12、de) return; currentSum += pTreeNode-m_nValue; path.push_back(pTreeNode-m_nValue); / if the node is a leaf, and the sum is same as pre-defined, / the path is what we want. print the path bool isLeaf = (!pTreeNode-m_pLeft & !pTreeNode-m_pRight); if(currentSum = expectedSum & isLeaf) std:vector:iterato

13、r iter = path.begin(); for(; iter != path.end(); + iter) std:cout *iter t; std:cout m_pLeft) FindPath(pTreeNode-m_pLeft, expectedSum, path, currentSum); if(pTreeNode-m_pRight) FindPath(pTreeNode-m_pRight, expectedSum, path, currentSum); / when we finish visiting a node and return to its parent node,

14、 / we should delete this node from the path and / minus the nodes value from the current sum currentSum -= pTreeNode-m_nValue; path.pop_back();5.查找最小的k個(gè)元素題目：輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1，2，3和4。/July 2010/10/18/引用自116 樓 wocaoqwer 的回復(fù)。#includeusing namespace std;class MinKpublic

15、: MinK(int *arr,int si):array(arr),size(si) bool kmin(int k,int*& ret) if(ksize) ret=NULL; return false; else ret=new intk-; int i; for(i=0;i=0;-j) shiftDown(ret,j,k); for(;isize;+i) if(arrayiret0) ret0=arrayi; shiftDown(ret,0,k); return true; void remove(int*& ret) delete ret; ret=NULL; private: vo

16、id shiftDown(int *ret,int pos,int length) int t=retpos; for(int s=2*pos+1;s=length;s=2*s+1) if(slength&retsrets+1) +s; if(trets) retpos=rets; pos=s; else break; retpos=t; int *array; int size;int main() int array=1,2,3,4,5,6,7,8; MinK mink(array,sizeof(array)/sizeof(array0); int *ret; int k=4; if(mi

17、nk.kmin(k,ret) for(int i=0;ik;+i) coutretiendl; mink.remove(ret); return 0;/運(yùn)行結(jié)果：4231Press any key to continue/第6題-騰訊面試題： 給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對應(yīng)的十個(gè)數(shù) 要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。 上排的十個(gè)數(shù)如下： 【0，1，2，3，4，5，6，7，8，9】初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂。 舉一個(gè)例子， 數(shù)值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0

18、0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次， 2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次. 以此類推. / 引用自July 2010年10月18日。/數(shù)值: 0,1,2,3,4,5,6,7,8,9/分配: 6,2,1,0,0,0,1,0,0,0#include #define len 10class NumberTB private: int toplen; int bottomlen; bool success;public: NumberTB(); int* getBottom(); void setNextBottom(); int getFrequecy(int num);NumberTB:N

19、umberTB() success = false; /format top for(int i=0;ilen;i+) topi = i; int* NumberTB:getBottom() int i = 0; while(!success) i+; setNextBottom(); return bottom; /set next bottom void NumberTB:setNextBottom() bool reB = true; for(int i=0;ilen;i+) int frequecy = getFrequecy(i); if(bottomi != frequecy) b

20、ottomi = frequecy; reB = false; success = reB; /get frequency in bottom int NumberTB:getFrequecy(int num) /此處的num即指上排的數(shù) i int count = 0; for(int i=0;ilen;i+) if(bottomi = num) count+; return count; /cout即對應(yīng) frequecyint main() NumberTB nTB; int* result= nTB.getBottom(); for(int i=0;ilen;i+) cout*resu

21、lt+next; while(fast!=NULL & fast-next!=NULL) low=low-next; fast=fast-next-next; if(low=fast) return true; return false;/如果鏈表可能有環(huán)，則如何判斷兩個(gè)鏈表是否相交/思路：鏈表1 步長為1，鏈表2步長為2 ，如果有環(huán)且相交則肯定相遇，否則不相交list1 head: p1list2 head: p2while( p1 != p2 & p1 != NULL & p2 != NULL ) b/但當(dāng)鏈表有環(huán)但不相交時(shí)，此處是死循環(huán)。!/b p1 = p1-next; if ( p2

22、-next ) p2 = p2-next-next; else p2 = p2-next;if ( p1 = p2 & p1 & p2) /相交else /不相交color=#FF0000b所以，判斷帶環(huán)的鏈表，相不相交，只能這樣/b：/color如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。如果在，則相交，如果不在，則不相交。(未寫代碼實(shí)現(xiàn)，見諒。:).-第9題-判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true，否則返回false。例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如

23、下樹的后序遍歷結(jié)果： 8 / 6 10/ / 5 7 9 11因此返回true。如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。/貌似，少有人關(guān)注此題。:).2010/10/18bool verifySquenceOfBST(int squence, int length) if(squence = NULL | length = 0) return false; / root of a BST is at the end of post order traversal squence int root = squencelength - 1; / the n

24、odes in left sub-tree are less than the root int i = 0; for(; i root) break; / the nodes in the right sub-tree are greater than the root int j = i; for(; j length - 1; + j) if(squencej 0) left = verifySquenceOfBST(squence, i); / verify whether the right sub-tree is a BST bool right = true; if(i leng

25、th - 1) right = verifySquenceOfBST(squence + i, length - i - 1); return (left & right);第9題：其實(shí)，就是一個(gè)后序遍歷二叉樹的算法。關(guān)鍵點(diǎn)：1. /確定根結(jié)點(diǎn) int root = squencelength - 1;2. / the nodes in left sub-tree are less than the root int i = 0; for(; i root) break; / the nodes in the right sub-tree are greater than the root i

26、nt j = i; for(; j length - 1; + j) if(squencej root) return false; 3.遞歸遍歷，左右子樹。-/第10題，單詞翻轉(zhuǎn)。/單詞翻轉(zhuǎn)，引用自117 樓 wocaoqwer 的回復(fù)。#include#includeusing namespace std;class ReverseWordspublic: ReverseWords(string* wo):words(wo) void reverse_() int length=words-size(); int begin=-1,end=-1; for(int i=0;iat(i)= )

27、 continue; if(begin=-1) begin=i; continue; if(words-at(i)= ) end=i-1; else if(i=length-1) end=i; else continue; reverse_(begin,end); /1.字母翻轉(zhuǎn) begin=-1,end=-1; reverse_(0,length-1); /2.單詞翻轉(zhuǎn) private: void reverse_(int begin,int end) / while(beginat(begin); words-at(begin)=words-at(end); words-at(end)=t

28、; +begin; -end; string* words;int main() string s=I am a student.; ReverseWords r(&s); r.reverse_(); coutspLeft = NULL) pRoot-MaxLeft = 0; else /若左子樹不為空 int TempLen = 0; if(pRoot-pLeft-MaxLeft pRoot-pLeft-MaxRight) /左子樹上的，某一節(jié)點(diǎn)，往左邊大，還是往右邊大 TempLen+=pRoot-pLeft-MaxLeft; else TempLen+=pRoot-pLeft-MaxRi

29、ght; pRoot-nMaxLeft = TempLen + 1; traversal_MaxLen(NODE* pRoot-pLeft); /此處，加上遞歸 if(pRoot-pRigth = NULL) pRoot-MaxRight = 0; else /若右子樹不為空 int TempLen = 0; if(pRoot-pRight-MaxLeft pRoot-pRight-MaxRight) /右子樹上的，某一節(jié)點(diǎn)，往左邊大，還是往右邊大 TempLen+=pRoot-pRight-MaxLeft; else TempLen+=pRoot-pRight-MaxRight; pRoot

30、-MaxRight = TempLen + 1; traversal_MaxLen(NODE* pRoot-pRight); /此處，加上遞歸 if(pRoot-MaxLeft + pRoot-MaxRight 0) MaxLength=pRoot-nMaxLeft + pRoot-MaxRight; / 數(shù)據(jù)結(jié)構(gòu)定義 struct NODE NODE* pLeft; / 左子樹 NODE* pRight; / 右子樹 int nMaxLeft; / 左子樹中的最長距離 int nMaxRight; / 右子樹中的最長距離 char chValue; / 該節(jié)點(diǎn)的值 ; int nMaxLen

31、 = 0; / 尋找樹中最長的兩段距離 void FindMaxLen(NODE* pRoot) / 遍歷到葉子節(jié)點(diǎn)，返回 if(pRoot = NULL) return; / 如果左子樹為空，那么該節(jié)點(diǎn)的左邊最長距離為0 if(pRoot - pLeft = NULL) pRoot - nMaxLeft = 0; / 如果右子樹為空，那么該節(jié)點(diǎn)的右邊最長距離為0 if(pRoot - pRight = NULL) pRoot - nMaxRight = 0; / 如果左子樹不為空，遞歸尋找左子樹最長距離 if(pRoot - pLeft != NULL) FindMaxLen(pRoot -

32、 pLeft); / 如果右子樹不為空，遞歸尋找右子樹最長距離 if(pRoot - pRight != NULL) FindMaxLen(pRoot - pRight); / 計(jì)算左子樹最長節(jié)點(diǎn)距離 if(pRoot - pLeft != NULL) int nTempMax = 0; if(pRoot - pLeft - nMaxLeft pRoot - pLeft - nMaxRight) nTempMax = pRoot - pLeft - nMaxLeft; else nTempMax = pRoot - pLeft - nMaxRight; pRoot - nMaxLeft = nTempMax + 1; / 計(jì)算右子樹最長節(jié)點(diǎn)距離 if(pRoot - pRight != NULL) int nTempMax = 0; if(pRoot - pRight - nMaxLeft pRoot - pRight - nMaxRight) nTempMax = pRoot - pRight - nMaxLeft; else nTempMa