程序員面試題精選(01)－把二元查找樹轉(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。
　　分析：本題是微軟的面試題。很多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。
　 　思路一：當(dāng)我們到達某一結(jié)點準(zhǔn)備調(diào)整以該結(jié)點為根結(jié)點的子樹時，先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。最近 鏈接左子鏈表的最右結(jié)點（左子樹的最大結(jié)點）、當(dāng)前結(jié)點和右子鏈表的最左結(jié)點（右子樹的最小結(jié)點）。從樹的根結(jié)點開始遞歸調(diào)整所有結(jié)點。
　　思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結(jié)點先訪問。如果我們每訪問一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當(dāng)前結(jié)點的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點都訪問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。
參考代碼：
首先我們定義二元查找樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：
??? struct BSTreeNode // a node in the binary search tree
??? {
??????? int????????? m_nValue; // value of node
??????? BSTreeNode? *m_pLeft;? // left child of node
??????? BSTreeNode? *m_pRight; // right child of node
??? };
思路一對應(yīng)的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//??????? asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
//???????? else return the greatest node in the sub-tree
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
????? if(!pNode)
??????????? return NULL;
????? BSTreeNode *pLeft = NULL;
????? BSTreeNode *pRight = NULL;

????? // Convert the left sub-tree
????? if(pNode->m_pLeft)
??????????? pLeft = ConvertNode(pNode->m_pLeft, false);

????? // Connect the greatest node in the left sub-tree to the current node
????? if(pLeft)
????? {
??????????? pLeft->m_pRight = pNode;
??????????? pNode->m_pLeft = pLeft;
????? }
????? // Convert the right sub-tree
????? if(pNode->m_pRight)
??????????? pRight = ConvertNode(pNode->m_pRight, true);
????? // Connect the least node in the right sub-tree to the current node
????? if(pRight)
????? {
??????????? pNode->m_pRight = pRight;
??????????? pRight->m_pLeft = pNode;
????? }

????? BSTreeNode *pTemp = pNode;
????? // If the current node is the right child of its parent,?
????? // return the least node in the tree whose root is the current node
????? if(asRight)
????? {
??????????? while(pTemp->m_pLeft)
????????????????? pTemp = pTemp->m_pLeft;
????? }
????? // If the current node is the left child of its parent,?
????? // return the greatest node in the tree whose root is the current node
????? else
????? {
??????????? while(pTemp->m_pRight)
????????????????? pTemp = pTemp->m_pRight;
????? }

????? return pTemp;
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
????? // As we want to return the head of the sorted double-linked list,
????? // we set the second parameter to be true
????? return ConvertNode(pHeadOfTree, true);
}
思路二對應(yīng)的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode -?????????? the head of the sub tree
//??????? pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
????? if(pNode == NULL)
??????????? return;

????? BSTreeNode *pCurrent = pNode;

????? // Convert the left sub-tree
????? if (pCurrent->m_pLeft != NULL)
??????????? ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

????? // Put the current node into the double-linked list
????? pCurrent->m_pLeft = pLastNodeInList;?
????? if(pLastNodeInList != NULL)
??????????? pLastNodeInList->m_pRight = pCurrent;

????? pLastNodeInList = pCurrent;

????? // Convert the right sub-tree
????? if (pCurrent->m_pRight != NULL)
??????????? ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
????? BSTreeNode *pLastNodeInList = NULL;
????? ConvertNode(pHeadOfTree, pLastNodeInList);

????? // Get the head of the double-linked list
????? BSTreeNode *pHeadOfList = pLastNodeInList;
????? while(pHeadOfList && pHeadOfList->m_pLeft)
??????????? pHeadOfList = pHeadOfList->m_pLeft;

????? return pHeadOfList;
}

?

程序員面試題精選(02)－設(shè)計包含min函數(shù)的棧
題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。 分析：這是去年google的一道面試題。
我看到這道題目時，第一反應(yīng)就是每次push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進棧的元素最先出棧，這種思路設(shè)計的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個棧了。
在棧里添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，如果該元素比當(dāng)前的最小元素還要小，則更新最小元素。
乍一看這樣思路挺好的。但仔細(xì)一想，該思路存在一個重要的問題：如果當(dāng)前最小元素被pop出去，如何才能得到下一個最小元素？
因 此僅僅只添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時將最小元素（或最小元素的 位置?？紤]到棧元素的類型可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能減少空間消耗）push到輔助棧中；每次pop一個元素出棧的時候，同時pop輔助 棧。
參考代碼：
#include

????? void push(const T& value);
????? void pop(void);

????? const T& min(void) const;

private:
???? T> m_data;?????????????? // the elements of stack
???? size_t> m_minIndex;????? // the indices of minimum elements
};

// get the last element of mutable stack
template

// get the last element of non-mutable stack
template

// insert an elment at the end of stack
template

????? // set the index of minimum elment in m_data at the end of m_minIndex
????? if(m_minIndex.size() == 0)
??????????? m_minIndex.push_back(0);
????? else
????? {
??????????? if(value < m_data[m_minIndex.back()])
????????????????? m_minIndex.push_back(m_data.size() - 1);
??????????? else
????????????????? m_minIndex.push_back(m_minIndex.back());
????? }
}

// erease the element at the end of stack
template

// get the minimum element of stack
template

?

?

程序員面試題精選(03)－求子數(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。
分析：本題最初為2005年浙江大學(xué)計算機系的考研題的最后一道程序設(shè)計題，在2006年里包括google在內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2006年程序員面試題中經(jīng)典中的經(jīng)典。
如果不考慮時間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長度為n的數(shù)組有O(n2)個子數(shù)組；而且求一個長度為n的數(shù)組的和的時間復(fù)雜度為O(n)。因此這種思路的時間是O(n3)。
很容易理解，當(dāng)我們加上一個正數(shù)時，和會增加；當(dāng)我們加上一個負(fù)數(shù)時，和會減少。如果當(dāng)前得到的和是個負(fù)數(shù)，那么這個和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個負(fù)數(shù)將會減少接下來的和?；谶@樣的思路，我們可以寫出如下代碼。
參考代碼：
/////////////////////////////////////////////////////////////////////////////
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool FindGreatestSumOfSubArray
(
????? int *pData,?????????? // an array
????? unsigned int nLength, // the length of array
????? int &nGreatestSum???? // the greatest sum of all sub-arrays
)
{
????? // if the input is invalid, return false
????? if((pData == NULL) || (nLength == 0))
??????????? return false;
????? int nCurSum = nGreatestSum = 0;
????? for(unsigned int i = 0; i < nLength; i)
????? {
??????????? nCurSum = pData;
??????????? // if the current sum is negative, discard it
??????????? if(nCurSum < 0)
????????????????? nCurSum = 0;

??????????? // if a greater sum is found, update the greatest sum
??????????? if(nCurSum > nGreatestSum)
????????????????? nGreatestSum = nCurSum;
????? }
????? // if all data are negative, find the greatest element in the array
????? if(nGreatestSum == 0)
????? {
??????????? nGreatestSum = pData[0];
??????????? for(unsigned int i = 1; i < nLength; i)
??????????? {
????????????????? if(pData > nGreatestSum)
??????????????????????? nGreatestSum = pData;
??????????? }
????? }

????? return true;
}

討論：上述代碼中有兩點值得和大家討論一下：
??????????函數(shù)的返回值不是子數(shù)組和的最大值，而是一個判斷輸入是否有效的標(biāo)志。如 果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個空指針是應(yīng)該返回什么呢？返回0？那這個函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中 情況呢？基于這個考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標(biāo)志。
??????????輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時，子數(shù)組和的最大值就是數(shù)組中的最大元素。

?

程序員面試題精選(04)－在二元樹中找出和為某一值的所有路徑
題目：輸入一個整數(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
};
分析：這是百度的一道筆試題，考查對樹這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。
當(dāng) 訪問到某一結(jié)點時，把該結(jié)點添加到路徑上，并累加當(dāng)前結(jié)點的值。如果當(dāng)前結(jié)點為葉結(jié)點并且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把 它打印出來。如果當(dāng)前結(jié)點不是葉結(jié)點，則繼續(xù)訪問它的子結(jié)點。當(dāng)前結(jié)點訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點。因此我們在函數(shù)退出之前要在路徑上刪除當(dāng)前 結(jié)點并減去當(dāng)前結(jié)點的值，以確保返回父結(jié)點時路徑剛好是根結(jié)點到父結(jié)點的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實際上是一個棧結(jié)構(gòu)，因為路徑要與遞歸調(diào)用 狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個壓棧和出棧的過程。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
????? BinaryTreeNode*?? pTreeNode,??? // a node of binary tree
????? int?????????????? expectedSum,? // the expected sum
????? std::vector

????? // if the node is not a leaf, goto its children
????? if(pTreeNode->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,
????? // we should delete this node from the path and?
????? // minus the node's value from the current sum
????? currentSum -= pTreeNode->m_nValue;
????? path.pop_back();
}

?

程序員面試題精選(05)－查找最小的k個元素
題目：輸入n個整數(shù)，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。
分析：這道題最簡單的思路莫過于把輸入的n個整數(shù)排序，這樣排在最前面的k個數(shù)就是最小的k個數(shù)。只是這種思路的時間復(fù)雜度為O(nlogn)。我們試著尋找更快的解決思路。
我 們可以開辟一個長度為k的數(shù)組。每次從輸入的n個整數(shù)中讀入一個數(shù)。如果數(shù)組中已經(jīng)插入的元素少于k個，則將讀入的整數(shù)直接放到數(shù)組中。否則長度為k的數(shù) 組已經(jīng)滿了，不能再往數(shù)組里插入元素，只能替換了。如果讀入的這個整數(shù)比數(shù)組中已有k個整數(shù)的最大值要小，則用讀入的這個整數(shù)替換這個最大值；如果讀入的 整數(shù)比數(shù)組中已有k個整數(shù)的最大值還要大，則讀入的這個整數(shù)不可能是最小的k個整數(shù)之一，拋棄這個整數(shù)。這種思路相當(dāng)于只要排序k個整數(shù)，因此時間復(fù)雜可 以降到O(n nlogk)。通常情況下k要遠小于n，所以這種辦法要優(yōu)于前面的思路。
這是我能夠想出來的最快的解決方案。不過從給面試官留下更 好印象的角度出發(fā)，我們可以進一步把代碼寫得更漂亮一些。從上面的分析，當(dāng)長度為k的數(shù)組已經(jīng)滿了之后，如果需要替換，每次替換的都是數(shù)組中的最大值。在 常用的數(shù)據(jù)結(jié)構(gòu)中，能夠在O(1)時間里得到最大值的數(shù)據(jù)結(jié)構(gòu)為最大堆。因此我們可以用堆（heap）來代替數(shù)組。
另外，自己重頭開始寫一個最大堆需要一定量的代碼。我們現(xiàn)在不需要重新去發(fā)明車輪，因為前人早就發(fā)明出來了。同樣，STL中的set和multiset為我們做了很好的堆的實現(xiàn)，我們可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印象，何樂而不為之？
參考代碼：
#include

????? if(k == 0 || data.size() < k)
??????????? return;
????? vector

??????????? // leastNumbers contains k numbers and it's full now
??????????? else
??????????? {
????????????????? // first number in leastNumbers is the greatest one
????????????????? IntHeap::iterator iterFirst = leastNumbers.begin();
????????????????? // if is less than the previous greatest number?
????????????????? if(*iter < *(leastNumbers.begin()))
????????????????? {
??????????????????????? // replace the previous greatest number
??????????????????????? leastNumbers.erase(iterFirst);
??????????????????????? leastNumbers.insert(*iter);
????????????????? }
??????????? }
????? }
}

?

程序員面試題精選(06)－判斷整數(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。
分析：這是一道trilogy的筆試題，主要考查對二元查找樹的理解。
在 后續(xù)遍歷得到的序列中，最后一個元素為樹的根結(jié)點。從頭開始掃描這個序列，比根結(jié)點小的元素都應(yīng)該位于序列的左半部分；從第一個大于跟結(jié)點開始到跟結(jié)點前 面的一個元素為止，所有元素都應(yīng)該大于跟結(jié)點，因為這部分元素對應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右 兩部分是不是都是二元查找樹。
參考代碼：
using namespace std;
///////////////////////////////////////////////////////////////////////
// Verify whether a squence of integers are the post order traversal
// of a binary search tree (BST)
// Input: squence - the squence of integers
//??????? length? - the length of squence
// Return: return ture if the squence is traversal result of a BST,
//???????? otherwise, return false
///////////////////////////////////////////////////////////////////////
bool 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 = squence[length - 1];
????? // the nodes in left sub-tree are less than the root
????? int i = 0;
????? for(; i < length - 1; i)
????? {
??????????? if(squence > root)
????????????????? break;
????? }

????? // the nodes in the right sub-tree are greater than the root
????? int j = i;
????? for(; j < length - 1; j)
????? {
??????????? if(squence[j] < root)
????????????????? return false;
????? }

????? // verify whether the left sub-tree is a BST
????? bool left = true;
????? if(i > 0)
??????????? left = verifySquenceOfBST(squence, i);

????? // verify whether the right sub-tree is a BST
????? bool right = true;
????? if(i < length - 1)
??????????? right = verifySquenceOfBST(squence i, length - i - 1);

????? return (left && right);
}

?

程序員面試題精選(07)－翻轉(zhuǎn)句子中單詞的順序
題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標(biāo)點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
分析：由于編寫字符串相關(guān)代碼能夠反映程序員的編程能力和編程習(xí)慣，與字符串相關(guān)的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。
由于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所有字符。這時，不但翻轉(zhuǎn)了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉(zhuǎn)了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時的順序保持一致。
還是以上面的輸入為例子。翻轉(zhuǎn)“I am a student.”中所有字符得到“.tneduts a ma I”，再翻轉(zhuǎn)每個單詞中字符的順序得到“students. a am I”，正是符合要求的輸出。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Reverse a string between two pointers
// Input: pBegin - the begin pointer in a string
//??????? pEnd?? - the end pointer in a string
///////////////////////////////////////////////////////////////////////
void Reverse(char *pBegin, char *pEnd)
{
????? if(pBegin == NULL || pEnd == NULL)
??????????? return;
????? while(pBegin < pEnd)
????? {
??????????? char temp = *pBegin;
??????????? *pBegin = *pEnd;
??????????? *pEnd = temp;
??????????? pBegin , pEnd --;
????? }
}
///////////////////////////////////////////////////////////////////////
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
///////////////////////////////////////////////////////////////////////
char* ReverseSentence(char *pData)
{
????? if(pData == NULL)
??????????? return NULL;

????? char *pBegin = pData;
????? char *pEnd = pData;
????? while(*pEnd != '/0')
??????????? pEnd ;
????? pEnd--;

????? // Reverse the whole sentence
????? Reverse(pBegin, pEnd);

????? // Reverse every word in the sentence
????? pBegin = pEnd = pData;
????? while(*pBegin != '/0')
????? {
??????????? if(*pBegin == ' ')
??????????? {
????????????????? pBegin ;
????????????????? pEnd ;
????????????????? continue;
??????????? }
??????????? // A word is between with pBegin and pEnd, reverse it
??????????? else if(*pEnd == ' ' || *pEnd == '/0')
??????????? {
????????????????? Reverse(pBegin, --pEnd);
????????????????? pBegin = pEnd;
??????????? }
??????????? else
??????????? {
????????????????? pEnd ;
??????????? }
????? }
????? return pData;
}

程序員面試題精選(08)－求1 2 ... n
題目：求1 2 … n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。
分析：這道題沒有多少實際意義，因為在軟件開發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關(guān)技術(shù)理解的深刻程度。
通 常求1 2 … n除了用公式n(n 1)/2之外，無外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣， 遞歸函數(shù)也需要用if語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語句了。
我們?nèi)匀粐@循環(huán)做文章。 循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數(shù)組，那么該 類的構(gòu)造函數(shù)將確定會被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個思路：
class Temp
{
public:
????? Temp() { N; Sum = N; }
????? static void Reset() { N = 0; Sum = 0; }
????? static int GetSum() { return Sum; }
private:
????? static int N;
????? static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
????? Temp::Reset();

????? Temp *a = new Temp[n];
????? delete []a;
????? a = 0;

????? return Temp::GetSum();
}
我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應(yīng)該終止遞歸，我 們不妨定義兩個函數(shù)。一個函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個函數(shù)處理終止遞歸的情況，我們需要做的就是在兩個函數(shù)里二選一。從二選一我們很自然的想到布爾變 量，比如ture（1）的時候調(diào)用第一個函數(shù)，false（0）的時候調(diào)用第二個函數(shù)。那現(xiàn)在的問題是如和把數(shù)值變量n轉(zhuǎn)換成布爾值。如果對n連續(xù)做兩次 反運算，即!!n，那么非零的n轉(zhuǎn)換為true，0轉(zhuǎn)換為false。有了上述分析，我們再來看下面的代碼：
class A;
A* Array[2];

class A
{
public:
????? virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
????? virtual int Sum (int n) { return Array[!!n]->Sum(n-1) n; }
};
int solution2_Sum(int n)
{
????? A a;
????? B b;
????? Array[0] = &a;
????? Array[1] = &b;

????? int value = Array[1]->Sum(n);
????? return value;
}
這種方法是用虛函數(shù)來實現(xiàn)函數(shù)的選擇。當(dāng)n不為零時，執(zhí)行函數(shù)B::Sum；當(dāng)n為0時，執(zhí)行A::Sum。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：
typedef int (*fun)(int);
int solution3_f1(int i)?
{
????? return 0;
}
int solution3_f2(int i)
{
????? fun f[2]={solution3_f1, solution3_f2};?
????? return i f[!!i](i-1);
}
另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：
template

template <> struct solution4_Sum

?

程序員面試題精選(09)－查找鏈表中倒數(shù)第k個結(jié)點
題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下： struct ListNode
{
????? int?????? m_nKey;
????? ListNode* m_pNext;
};
分析：為了得到倒數(shù)第k個結(jié)點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。
既 然不能從尾結(jié)點開始遍歷這個鏈表，我們還是把思路回到頭結(jié)點上來。假設(shè)整個鏈表有n個結(jié)點，那么倒數(shù)第k個結(jié)點是從頭結(jié)點開始的第n-k-1個結(jié)點（從0 開始計數(shù)）。如果我們能夠得到鏈表中結(jié)點的個數(shù)n，那我們只要從頭結(jié)點開始往后走n-k-1步就可以了。如何得到結(jié)點數(shù)n？這個不難，只需要從頭開始遍歷 鏈表，每經(jīng)過一個結(jié)點，計數(shù)器加一就行了。
這種思路的時間復(fù)雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點個數(shù)n，第二次得到從頭結(jié)點開始的第n?-k-1個結(jié)點即倒數(shù)第k個結(jié)點。
如 果鏈表的結(jié)點數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點個數(shù)很多，有可能不能一次性把整個鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個結(jié) 點需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1？如果可以，將能有效地提高代 碼執(zhí)行的時間效率。
如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個指針保持不動；在第k-1步開 始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1，當(dāng)?shù)谝粋€（走在前面的）指針到達鏈表的尾結(jié)點時，第二個指針（走在后面 的）指針正好是倒數(shù)第k個結(jié)點。
這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結(jié)點從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時間效率前面的方法要高。
思路一的參考代碼：
///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
//??????? k???????? - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)
{
????? if(pListHead == NULL)
??????????? return NULL;

????? // count the nodes number in the list
????? ListNode *pCur = pListHead;
????? unsigned int nNum = 0;
????? while(pCur->m_pNext != NULL)
????? {
??????????? pCur = pCur->m_pNext;
??????????? nNum ;
????? }

????? // if the number of nodes in the list is less than k
????? // do nothing
????? if(nNum < k)
??????????? return NULL;

????? // the kth node from the tail of a list?
????? // is the (n - k)th node from the head
????? pCur = pListHead;
????? for(unsigned int i = 0; i < nNum - k; i)
??????????? pCur = pCur->m_pNext;
????? return pCur;
}
思路二的參考代碼：
///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
//??????? k???????? - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k)
{
????? if(pListHead == NULL)
??????????? return NULL;

????? ListNode *pAhead = pListHead;
????? ListNode *pBehind = NULL;
????? for(unsigned int i = 0; i < k; i)
????? {