程式員面試題精選100題 [折疊]
前言
随着高校的持續擴張，每年應屆畢業生的數目都在不斷增長，伴随而來的是應屆畢業生的就業壓力也越來越大。
在這樣的背景下，就業變成一個買方市場的趨勢越來越明顯。為了找到一個稱心的工作，絕大多數應屆畢業生都必須反複經曆履歷篩選、電話面試、筆試、面試等環節。在這些環節中，面試無疑起到最為重要的作用，因為通過面試公司能夠最直覺的了解學生的能力。
為了有效地準備面試，面經這個新興概念應運而生。筆者在當初找工作階段也從面經中獲益匪淺并最終找到滿意的工作。為了友善後來者，筆者花費大量時間收集并整理散落在茫茫網絡中的面經。不同行業的面經全然不同，筆者從自身專業出發，着重關注程式員面試的面經，并從精選出若幹具有代表性的技術類的面試題展開讨論，希望能給讀者帶來一些啟發。
由于筆者水準有限，給各面試題提供的思路和代碼難免會有錯誤，還請讀者批評指正。另外，熱忱歡迎讀者能夠提供更多、更好的面試題，本人将感激不盡。
(01)把二進制查找樹轉變成排序的雙向連結清單
[折疊]
題目：輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻調整指針的指向。
比如将二進制查找樹
10
/ \
6 14
/ \ / \
4 8 12 16
轉換成雙向連結清單
4=6=8=10=12=14=16。
分析：本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。
思路一：當我們到達某一結點準備調整以該結點為根結點的子樹時，先調整其左子樹将左子樹轉換成一個排好序的左子連結清單，再調整其右子樹轉換右子連結清單。最近連結左子連結清單的最右結點（左子樹的最大結點）、目前結點和右子連結清單的最左結點（右子樹的最小結點）。從樹的根結點開始遞歸調整所有結點。
思路二：我們可以中序周遊整棵樹。按照這個方式周遊樹，比較小的結點先通路。如果我們每通路一個結點，假設之前通路過的結點已經調整成一個排序雙向連結清單，我們再把調整目前結點的指針将其連結到連結清單的末尾。當所有結點都通路過之後，整棵樹也就轉換成一個排序雙向連結清單了。
參考代碼：
首先我們定義二進制查找樹結點的資料結構如下：
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; // rightchild of node
};
思路一對應的代碼：
///
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// asRight - whether pNode is theright child of its parent
// Output: if asRight is true, return the least node in the sub-tree
// else return the greatest nodein the sub-tree
///
BSTreeNode*ConvertNode(BSTreeNode* pNode, bool asRight)
{
if(!pNode)
returnNULL;
BSTreeNode *pLeft = NULL;
BSTreeNode *pRight = NULL;
// Convertthe left sub-tree
if(pNode->m_pLeft)
pLeft = ConvertNode(pNode->m_pLeft,false);
// Connectthe greatest node in the left sub-tree to the current node
if(pLeft)
{
pLeft->m_pRight = pNode;
pNode->m_pLeft = pLeft;
}
// Convertthe right sub-tree
if(pNode->m_pRight)
pRight =ConvertNode(pNode->m_pRight, true);
// Connectthe 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 thecurrent 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 thecurrent 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;
}
returnpTemp;
}
///
// 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 wewant to return the head of the sorted double-linked list,
// weset the second parameter to be true
returnConvertNode(pHeadOfTree, true);
}
思路二對應的代碼：
///
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head ofthe sub tree
// pLastNodeInList - the tail ofthe double-linked list
///
void ConvertNode(BSTreeNode* pNode, BSTreeNode*&pLastNodeInList)
{
if(pNode== NULL)
return;
BSTreeNode *pCurrent = pNode;
// Convertthe left sub-tree
if(pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft,pLastNodeInList);
// Put thecurrent node into the double-linked list
pCurrent->m_pLeft =pLastNodeInList;
if(pLastNodeInList!= NULL)
pLastNodeInList->m_pRight =pCurrent;
pLastNodeInList = pCurrent;
// Convertthe 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 thehead of the double-linked list
BSTreeNode *pHeadOfList =pLastNodeInList;
while(pHeadOfList&& pHeadOfList->m_pLeft)
pHeadOfList =pHeadOfList->m_pLeft;
returnpHeadOfList;
}
(02)設計包含min函數的棧
[折疊]
題目：定義棧的資料結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間複雜度都是O(1)。
分析：這是去年google的一道面試題。
我看到這道題目時，第一反應就是每次push一個新元素時，将棧裡所有逆序元素排序。這樣棧頂元素将是最小元素。但由于不能保證最後push進棧的元素最先出棧，這種思路設計的資料結構已經不是一個棧了。
在棧裡添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，如果該元素比目前的最小元素還要小，則更新最小元素。
乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果目前最小元素被pop出去，如何才能得到下一個最小元素？
是以僅僅隻添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時将最小元素（或最小元素的位置。考慮到棧元素的類型可能是複雜的資料結構，用最小元素的位置将能減少空間消耗）push到輔助棧中；每次pop一個元素出棧的時候，同時pop輔助棧。
參考代碼：
#include <deque>
#include <assert.h>
template <typenameT> class CStackWithMin
{
public:
CStackWithMin(void){}
virtual~CStackWithMin(void) {}
T& top(void);
constT& top(void) const;
voidpush(const T& value);
voidpop(void);
constT& min(void) const;
private:
T>m_data;//theelements of stack
size_t>m_minIndex;// the indicesof minimum elements
};
// get the last element of mutable stack
template <typenameT> T& CStackWithMin<T>::top()
{
returnm_data.back();
}
// get the last element of non-mutable stack
template <typenameT> const T&CStackWithMin<T>::top() const
{
returnm_data.back();
}
// insert an elment at the end of stack
template <typenameT> void CStackWithMin<T>::push(const T& value)
{
// appendthe data into the end of m_data
m_data.push_back(value);
// set theindex 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 <typenameT> void CStackWithMin<T>::pop()
{
// popm_data
m_data.pop_back();
// popm_minIndex
m_minIndex.pop_back();
}
// get the minimum element of stack
template <typenameT> const T&CStackWithMin<T>::min() const
{
assert(m_data.size() > 0);
assert(m_minIndex.size() > 0);
returnm_data[m_minIndex.back()];
}
舉個例子示範上述代碼的運作過程：
步驟 資料棧 輔助棧 最小值
1.push 3 3 0 3
2.push 4 3,4 0,0 3
3.push 2 3,4,2 0,0,2 2
4.push 1 3,4,2,1 0,0,2,3 1
5.pop 3,4,2 0,0,2 2
6.pop 3,4 0,0 3
7.push 0 3,4,0 0,0,2 0
讨論：如果思路正确，編寫上述代碼不是一件很難的事情。但如果能注意一些細節無疑能在面試中加分。比如我在上面的代碼中做了如下的工作：
· 用模闆類實作。如果别人的元素類型隻是int類型，模闆将能給面試官帶來好印象；
· 兩個版本的top函數。在很多類中，都需要提供const和非const版本的成員通路函數；
· min函數中assert。把代碼寫的盡量安全是每個軟體公司對程式員的要求；
· 添加一些注釋。注釋既能提高代碼的可讀性，又能增加代碼量，何樂而不為？
總之，在面試時如果時間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個小亮點就能讓自己輕松拿到心儀的Offer。
(03)－求子數組的最大和
[折疊]
題目：輸入一個整形數組，數組裡有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間複雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，是以輸出為該子數組的和18。
分析：本題最初為2005年浙江大學計算機系的考研題的最後一道程式設計題，在2006年裡包括google在内的很多知名公司都把本題當作面試題。由于本題在網絡中廣為流傳，本題也順利成為2006年程式員面試題中經典中的經典。
如果不考慮時間複雜度，我們可以枚舉出所有子數組并求出他們的和。不過非常遺憾的是，由于長度為n的數組有O(n2)個子數組；而且求一個長度為n的數組的和的時間複雜度為O(n)。是以這種思路的時間是O(n3)。
很容易了解，當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果目前得到的和是個負數，那麼這個和在接下來的累加中應該抛棄并重新清零，不然的話這個負數将會減少接下來的和。基于這樣的思路，我們可以寫出如下代碼。
參考代碼：
/
// 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
unsignedint nLength, // thelength of array
int&nGreatestSum // the greatest sum of all sub-arrays
)
{
// if theinput is invalid, return false
if((pData== NULL) || (nLength == 0))
returnfalse;
intnCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i< nLength; ++i)
{
nCurSum += pData[i];
// if thecurrent sum is negative, discard it
if(nCurSum< 0)
nCurSum = 0;
// if agreater sum is found, update the greatest sum
if(nCurSum> nGreatestSum)
nGreatestSum = nCurSum;
}
// if alldata 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[i]> nGreatestSum)
nGreatestSum = pData[i];
}
}
returntrue;
}
讨論：上述代碼中有兩點值得和大家讨論一下：
· 函數的傳回值不是子數組和的最大值，而是一個判斷輸入是否有效的标志。如果函數傳回值的是子數組和的最大值，那麼當輸入一個空指針是應該傳回什麼呢？傳回0？那這個函數的使用者怎麼區分輸入無效和子數組和的最大值剛好是0這兩中情況呢？基于這個考慮，本人認為把子數組和的最大值以引用的方式放到參數清單中，同時讓函數傳回一個函數是否正常執行的标志。
· 輸入有一類特殊情況需要特殊處理。當輸入數組中所有整數都是負數時，子數組和的最大值就是數組中的最大元素。
(04)－在二進制樹中找出和為某一值的所有路徑 [折疊]
題目：輸入一個整數和一棵二進制樹。從樹的根結點開始往下通路一直到葉結點所經過的所有結點形成一條路徑。列印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二進制樹
10
/ \
5 12
/ \
4 7
則列印出兩條路徑：10, 12和10, 5, 7。
二進制樹結點的資料結構定義為：
struct BinaryTreeNode // anode in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // rightchild of node
};
分析：這是百度的一道筆試題，考查對樹這種基本資料結構以及遞歸函數的了解。
當通路到某一結點時，把該結點添加到路徑上，并累加目前結點的值。如果目前結點為葉結點并且目前路徑的和剛好等于輸入的整數，則目前的路徑符合要求，我們把它列印出來。如果目前結點不是葉結點，則繼續通路它的子結點。目前結點通路結束後，遞歸函數将自動回到父結點。是以我們在函數退出之前要在路徑上删除目前結點并減去目前結點的值，以確定傳回父結點時路徑剛好是根結點到父結點的路徑。我們不難看出儲存路徑的資料結構實際上是一個棧結構，因為路徑要與遞歸調用狀态一緻，而遞歸調用本質就是一個壓棧和出棧的過程。
參考代碼：
///
// Find paths whose sum equal to expected sum
///
void FindPath
(
BinaryTreeNode* pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector<int>&path, // a pathfromroot to current node
int& currentSum // the sum ofpath
)
{
if(!pTreeNode)
return;
currentSum += pTreeNode->m_nValue;
path.push_back(pTreeNode->m_nValue);
// if thenode is a leaf, and the sum is same as pre-defined,
//the path is what we want. print the path
boolisLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum== expectedSum && isLeaf)
{
std::vector<int>::iterator iter=path.begin();
for(; iter != path.end(); ++ iter)
std::cout<<*iter<<'\t';
std::cout<<std::endl;
}
// if thenode 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 wefinish visiting a node and return to its parent node,
// weshould delete this node from the path and
//minus the node's value from the current sum
currentSum -=pTreeNode->m_nValue; //!!I think here is no use
path.pop_back();
}
(05)查找最小的k個元素 [折疊]
題目：輸入n個整數，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。
分析：這道題最簡單的思路莫過于把輸入的n個整數排序，這樣排在最前面的k個數就是最小的k個數。隻是這種思路的時間複雜度為O(nlogn)。我們試着尋找更快的解決思路。
我們可以開辟一個長度為k的數組。每次從輸入的n個整數中讀入一個數。如果數組中已經插入的元素少于k個，則将讀入的整數直接放到數組中。否則長度為k的數組已經滿了，不能再往數組裡插入元素，隻能替換了。如果讀入的這個整數比數組中已有k個整數的最大值要小，則用讀入的這個整數替換這個最大值；如果讀入的整數比數組中已有k個整數的最大值還要大，則讀入的這個整數不可能是最小的k個整數之一，抛棄這個整數。這種思路相當于隻要排序k個整數，是以時間複雜可以降到O(n+nlogk)。通常情況下k要遠小于n，是以這種辦法要優于前面的思路。
這是我能夠想出來的最快的解決方案。不過從給面試官留下更好印象的角度出發，我們可以進一步把代碼寫得更漂亮一些。從上面的分析，當長度為k的數組已經滿了之後，如果需要替換，每次替換的都是數組中的最大值。在常用的資料結構中，能夠在O(1)時間裡得到最大值的資料結構為最大堆。是以我們可以用堆（heap）來代替數組。
另外，自己重頭開始寫一個最大堆需要一定量的代碼。我們現在不需要重新去發明車輪，因為前人早就發明出來了。同樣，STL中的set和multiset為我們做了很好的堆的實作，我們可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印象，何樂而不為之？
參考代碼：
#include <set>
#include <vector>
#include <iostream>
using namespacestd;
typedef multiset<int,greater<int> > IntHeap;
///
// find k least numbers in a vector
///
void FindKLeastNumbers
(
constvector<int>& data, // a vectorof data
IntHeap& leastNumbers, // kleast numbers, output
unsignedint k
)
{
leastNumbers.clear();
if(k== 0 || data.size() < k)
return;
vector<int>::const_iteratoriter = data.begin();
for(;iter != data.end(); ++ iter)
{
// ifless than k numbers was inserted into leastNumbers
if((leastNumbers.size())< k)
leastNumbers.insert(*iter);
//leastNumbers contains k numbers and it's full now
else
{
//first number in leastNumbers is the greatest one
IntHeap::iteratoriterFirst = leastNumbers.begin();
// ifis less than the previous greatest number
if(*iter< *(leastNumbers.begin()))
{
//replace the previous greatest number
leastNumbers.erase(iterFirst);
leastNumbers.insert(*iter);
}
}
}
}
(06)判斷整數序列是不是二進制查找樹的後序周遊結果
[折疊]
題目：輸入一個整數數組，判斷該數組是不是某二進制查找樹的後序周遊的結果。如果是傳回true，否則傳回false。
例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的後序周遊結果：
8
/ \
6 10
/ \ / \
5 7 9 11
是以傳回true。
如果輸入7、4、6、5，沒有哪棵樹的後序周遊的結果是這個序列，是以傳回false。
分析：這是一道trilogy的筆試題，主要考查對二進制查找樹的了解。
在後續周遊得到的序列中，最後一個元素為樹的根結點。從頭開始掃描這個序列，比根結點小的元素都應該位于序列的左半部分；從第一個大于跟結點開始到跟結點前面的一個元素為止，所有元素都應該大于跟結點，因為這部分元素對應的是樹的右子樹。根據這樣的劃分，把序列劃分為左右兩部分，我們遞歸地确認序列的左、右兩部分是不是都是二進制查找樹。
參考代碼：
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[], intlength)
{
if(squence== NULL || length <= 0)
returnfalse;
// root of aBST is at the end of post order traversal squence
introot = squence[length - 1];
// the nodesin left sub-tree are less than the root
inti = 0;
for(;i < length - 1; ++ i)
{
if(squence[i]> root)
break;
}
// the nodesin the right sub-tree are greater than the root
intj = i;
for(;j < length - 1; ++ j)
{
if(squence[j]< root)
returnfalse;
}
// verifywhether the left sub-tree is a BST
boolleft = true;
if(i> 0)
left = verifySquenceOfBST(squence,i);
// verifywhether the right sub-tree is a BST
boolright = true;
if(i< length - 1)
right = verifySquenceOfBST(squence+ i, length - i - 1);
return(left && right);
}
(07)－翻轉句子中單詞的順序 [折疊]
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞内字元的順序不變。句子中單詞以空格符隔開。為簡單起見，标點符号和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
分析：由于編寫字元串相關代碼能夠反映程式員的程式設計能力和程式設計習慣，與字元串相關的問題一直是程式員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在内的大量公司的青睐。
由于本題需要翻轉句子，我們先颠倒句子中的所有字元。這時，不但翻轉了句子中單詞的順序，而且單詞内字元也被翻轉了。我們再颠倒每個單詞内的字元。由于單詞内的字元被翻轉兩次，是以順序仍然和輸入時的順序保持一緻。
還是以上面的輸入為例子。翻轉“I am a student.”中所有字元得到“.tneduts a ma I”，再翻轉每個單詞中字元的順序得到“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)
{
chartemp = *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)
returnNULL;
char*pBegin = pData;
char*pEnd = pData;
while(*pEnd!= '\0')
pEnd ++;
pEnd--;
// Reversethe whole sentence
Reverse(pBegin, pEnd);
// Reverseevery word in the sentence
pBegin = pEnd = pData;
while(*pBegin!= '\0')
{
if(*pBegin== ' ')
{
pBegin ++;
pEnd ++;
continue;
}
// A wordis between with pBegin and pEnd, reverse it
elseif(*pEnd == ' '|| *pEnd == '\0')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
returnpData;
}
(08)－求1+2+...+n
題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（A?B:C）。
分析：這道題沒有多少實際意義，因為在軟體開發中不會有這麼變态的限制。但這道題卻能有效地考查發散思維能力，而發散思維能力能反映出對程式設計相關技術了解的深刻程度。
通常求1+2+…+n除了用公式n(n+1)/2之外，無外乎循環和遞歸兩種思路。由于已經明确限制for和while的使用，循環已經不能再用了。同樣，遞歸函數也需要用if語句或者條件判斷語句來判斷是繼續遞歸下去還是終止遞歸，但現在題目已經不允許使用這兩種語句了。
我們仍然圍繞循環做文章。循環隻是讓相同的代碼執行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數組，那麼該類的構造函數将确定會被調用n次。我們可以将需要執行的代碼放到構造函數裡。如下代碼正是基于這個思路：
class Temp
{
public:
Temp() { ++ N; Sum += N; }
staticvoid Reset() { N = 0; Sum = 0; }
staticint GetSum() { returnSum; }
private:
staticint N;
staticint Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(intn)
{
Temp::Reset();
Temp *a = newTemp[n];
delete[]a;
a = 0;
returnTemp::GetSum();
}
我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我們不妨定義兩個函數。一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，我們需要做的就是在兩個函數裡二選一。從二選一我們很自然的想到布爾變量，比如ture（1）的時候調用第一個函數，false（0）的時候調用第二個函數。那現在的問題是如和把數值變量n轉換成布爾值。如果對n連續做兩次反運算，即!!n，那麼非零的n轉換為true，0轉換為false。有了上述分析，我們再來看下面的代碼：
class A;
A* Array[2];
class A
{
public:
virtualint Sum (int n){ return 0; }
};
class B: publicA
{
public:
virtualint Sum (int n){ return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(intn)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
intvalue = Array[1]->Sum(n);
returnvalue;
}
這種方法是用虛函數來實作函數的選擇。當n不為零時，執行函數B::Sum；當n為0時，執行A::Sum。我們也可以直接用函數指針數組，這樣可能還更直接一些：
typedef int (*fun)(int);
int solution3_f1(inti)
{
return0;
}
int solution3_f2(inti)
{
fun f[2]={solution3_f1,solution3_f2};
returni+f[!!i](i-1);
}
另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：
template <int n> struct solution4_Sum
{
enumValue { N = solution4_Sum<n - 1>::N + n};
};
template <> structsolution4_Sum<1>
{
enumValue { N = 1};
};
solution4_Sum<100>::N就是1+2+...+100的結果。當編譯器看到solution4_Sum<100>時，就是為模闆類solution4_Sum以參數100生成該類型的代碼。但以100為參數的類型需要得到以99為參數的類型，因為solution4_Sum<100>::N=solution4_Sum<99>::N+100。這個過程會遞歸一直到參數為1的類型，由于該類型已經顯式定義，編譯器無需生成，遞歸編譯到此結束。由于這個過程是在編譯過程中完成的，是以要求輸入n必須是在編譯期間就能确定，不能動态輸入。這是該方法最大的缺點。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。
大家還有更多、更巧妙的思路嗎？歡迎讨論^_^
(09)－查找連結清單中倒數第k個結點
題目：輸入一個單向連結清單，輸出該連結清單中倒數第k個結點。連結清單的倒數第0個結點為連結清單的尾指針。連結清單結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：為了得到倒數第k個結點，很自然的想法是先走到連結清單的尾端，再從尾端回溯k步。可是輸入的是單向連結清單，隻有從前往後的指針而沒有從後往前的指針。是以我們需要打開我們的思路。
既然不能從尾結點開始周遊這個連結清單，我們還是把思路回到頭結點上來。假設整個連結清單有n個結點，那麼倒數第k個結點是從頭結點開始的第n-k-1個結點（從0開始計數）。如果我們能夠得到連結清單中結點的個數n，那我們隻要從頭結點開始往後走n-k-1步就可以了。如何得到結點數n？這個不難，隻需要從頭開始周遊連結清單，每經過一個結點，計數器加一就行了。
這種思路的時間複雜度是O(n)，但需要周遊連結清單兩次。第一次得到連結清單中結點個數n，第二次得到從頭結點開始的第n-k-1個結點即倒數第k個結點。
如果連結清單的結點數不多，這是一種很好的方法。但如果輸入的連結清單的結點個數很多，有可能不能一次性把整個連結清單都從硬碟讀入實體記憶體，那麼周遊兩遍意味着一個結點需要兩次從硬碟讀入到實體記憶體。我們知道把資料從硬碟讀入到記憶體是非常耗時間的操作。我們能不能把連結清單周遊的次數減少到1？如果可以，将能有效地提高代碼執行的時間效率。
如果我們在周遊時維持兩個指針，第一個指針從連結清單的頭指針開始周遊，在第k-1步之前，第二個指針保持不動；在第k-1步開始，第二個指針也開始從連結清單的頭指針開始周遊。由于兩個指針的距離保持在k-1，當第一個（走在前面的）指針到達連結清單的尾結點時，第二個指針（走在後面的）指針正好是倒數第k個結點。
這種思路隻需要周遊連結清單一次。對于很長的連結清單，隻需要把每個結點從硬碟導入到記憶體一次。是以這一方法的時間效率前面的方法要高。
思路一的參考代碼：
///
// 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, unsignedint k)
{
if(pListHead== NULL)
returnNULL;
// count thenodes number in the list
ListNode *pCur = pListHead;
unsignedint nNum = 0;
while(pCur->m_pNext!= NULL)
{
pCur = pCur->m_pNext;
nNum ++;
}
// if thenumber of nodes in the list is less than k
// donothing
if(nNum< k)
returnNULL;
// the kthnode from the tail of a list
// isthe (n - k)th node from the head
pCur = pListHead;
for(unsigned int i = 0; i< nNum - k; ++ i)
pCur = pCur->m_pNext;
returnpCur;
}
思路二的參考代碼：
///
// 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, unsignedint k)
{
if(pListHead== NULL)
returnNULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for(unsigned int i = 0; i< k; ++ i)
{
if(pAhead->m_pNext!= NULL)
pAhead = pAhead->m_pNext;
else
{
// ifthe number of nodes in the list is less than k,
//do nothing
returnNULL;
}
}
pBehind = pListHead;
// thedistance between pAhead and pBehind is k
//when pAhead arrives at the tail, p
//Behind is at the kth node from the tail
while(pAhead->m_pNext!= NULL)
{
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
}
returnpBehind;
}
讨論：這道題的代碼有大量的指針操作。在軟體開發中，錯誤的指針操作是大部分問題的根源。是以每個公司都希望程式員在操作指針時有良好的習慣，比如使用指針之前判斷是不是空指針。這些都是程式設計的細節，但如果這些細節把握得不好，很有可能就會和心儀的公司失之交臂。
另外，這兩種思路對應的代碼都含有循環。含有循環的代碼經常出的問題是在循環結束條件的判斷。是該用小于還是小于等于？是該用k還是該用k-1？由于題目要求的是從0開始計數，而我們的習慣思維是從1開始計數，是以首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之後再用邊界值、邊界值減1、邊界值加1都運作一次（在紙上寫代碼就隻能在心裡運作了）。
擴充：和這道題類似的題目還有：輸入一個單向連結清單。如果該連結清單的結點數為奇數，輸出中間的結點；如果連結清單結點數為偶數，輸出中間兩個結點前面的一個。如果各位感興趣，請自己分析并編寫代碼。
思路：設定兩個指針* fast、*slow都指向單連結清單的頭節點。其中* fast的移動速度是* slow的2倍。當* fast指向末尾節點的時候，slow正好就在中間了。
(10)－在排序數組中查找和為給定值的兩個數字
題目：輸入一個已經按升序排序過的數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。要求時間複雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。
例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，是以輸出4和11。
分析：如果我們不考慮時間複雜度，最簡單想法的莫過去先在數組中固定一個數字，再依次判斷數組中剩下的n-1個數字與它的和是不是等于輸入的數字。可惜這種思路需要的時間複雜度是O(n2)。
我們假設現在随便在數組中找到兩個數。如果它們的和等于輸入的數字，那太好了，我們找到了要找的兩個數字；如果小于輸入的數字呢？我們希望兩個數字的和再大一點。由于數組已經排好序了，我們是不是可以把較小的數字的往後面移動一個數字？因為排在後面的數字要大一些，那麼兩個數字的和也要大一些，就有可能等于輸入的數字了；同樣，當兩個數字的和大于輸入的數字的時候，我們把較大的數字往前移動，因為排在數組前面的數字要小一些，它們的和就有可能等于輸入的數字了。
我們把前面的思路整理一下：最初我們找到數組的第一個數字和最後一個數字。當兩個數字的和大于輸入的數字時，把較大的數字往前移動；當兩個數字的和小于數字時，把較小的數字往後移動；當相等時，打完收工。這樣掃描的順序是從數組的兩端向數組的中間掃描。
問題是這樣的思路是不是正确的呢？這需要嚴格的數學證明。感興趣的讀者可以自行證明一下。
參考代碼：
///
// Find two numbers with a sum in a sorted array
// Output: ture is found such two numbers, otherwise false
///
bool FindTwoNumbersWithSum
(
intdata[], // a sorted array
unsignedint length, // the length of the sorted array
intsum, // the sum
int&num1, //the first number, output
int&num2 //the second number, output
)
{
bool found = false;
if(length< 1)
returnfound;
intahead = length - 1;
intbehind = 0;
while(ahead> behind)
{
long longcurSum = data[ahead] + data[behind];
// if thesum of two numbers is equal to the input
//we have found them
if(curSum== sum)
{
num1 = data[behind];
num2 = data[ahead];
found = true;
break;
}
// if thesum of two numbers is greater than the input
//decrease the greater number
elseif(curSum > sum)
ahead --;
// if thesum of two numbers is less than the input
//increase the less number
else
behind ++;
}
returnfound;
}
擴充：如果輸入的數組是沒有排序的，但知道裡面數字的範圍，其他條件不變，如和在O(n)時間裡找到這兩個數字？
(11)－求二進制查找樹的鏡像
題目：輸入一顆二進制查找樹，将該樹轉換為它的鏡像，即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
定義二進制查找樹的結點為：
struct BSTreeNode // a node inthe binary search tree (BST)
{
int m_nValue; //value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // rightchild of node
};
分析：盡管我們可能一下子不能了解鏡像是什麼意思，但上面的例子給我們的直覺感覺，就是交換結點的左右子樹。我們試着在周遊例子中的二進制查找樹的同時來交換每個結點的左右子樹。周遊時首先通路頭結點8，我們交換它的左右子樹得到：
8
/ \
10 6
/\ /\
9 11 5 7
我們發現兩個結點6和10的左右子樹仍然是左結點的值小于右結點的值，我們再試着交換他們的左右子樹，得到：
8
/ \
10 6
/\ /\
11 9 7 5
剛好就是要求的輸出。
上面的分析印證了我們的直覺：在周遊二進制查找樹時每通路到一個結點，交換它的左右子樹。這種思路用遞歸不難實作，将周遊二進制查找樹的代碼稍作修改就可以了。參考代碼如下：
///
// Mirror a BST (swap the left right child of each node) recursively
// the head of BST in initial call
///
void MirrorRecursively(BSTreeNode *pNode)
{
if(!pNode)
return;
// swap theright and left child sub-tree
BSTreeNode *pTemp =pNode->m_pLeft;
pNode->m_pLeft =pNode->m_pRight;
pNode->m_pRight = pTemp;
// mirror left child sub-tree if not null
if(pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
// mirrorright child sub-tree if not null
if(pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
由于遞歸的本質是編譯器生成了一個函數調用的棧，是以用循環來完成同樣任務時最簡單的辦法就是用一個輔助棧來模拟遞歸。首先我們把樹的頭結點放入棧中。在循環中，隻要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。如果它有左子樹，把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環中就能交換它兒子結點的左右子樹了。參考代碼如下：
///
// Mirror a BST (swap the left right child of each node) Iteratively
// Input: pTreeHead: the head of BST
///
void MirrorIteratively(BSTreeNode *pTreeHead)
{
if(!pTreeHead)
return;
std::stack<BSTreeNode*>stackTreeNode;
stackTreeNode.push(pTreeHead);
while(stackTreeNode.size())
{
BSTreeNode *pNode =stackTreeNode.top();
stackTreeNode.pop();
// swapthe right and left child sub-tree
BSTreeNode *pTemp =pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// pushleft child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);
// pushright child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
(12)－從上往下周遊二進制樹
題目：輸入一顆二進制樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印。
例如輸入
8
/ \
6 10
/\ /\
5 7 9 11
輸出8 6 10 5 7 9 11。
分析：這曾是微軟的一道面試題。這道題實質上是要求周遊一棵二進制樹，隻不過不是我們熟悉的前序、中序或者後序周遊。
我們從樹的根結點開始分析。自然先應該列印根結點8，同時為了下次能夠列印8的兩個子結點，我們應該在周遊到8時把子結點6和10儲存到一個資料容器中。現在資料容器中就有兩個元素6 和10了。按照從左往右的要求，我們先取出6通路。列印6的同時要把6的兩個子結點5和7放入資料容器中，此時資料容器中有三個元素10、5和7。接下來我們應該從資料容器中取出結點10通路了。注意10比5和7先放入容器，此時又比5和7先取出，就是我們通常說的先入先出。是以不難看出這個資料容器的類型應該是個隊列。
既然已經确定資料容器是一個隊列，現在的問題變成怎麼實作隊列了。實際上我們無需自己動手實作一個，因為STL已經為我們實作了一個很好的deque（兩端都可以進出的隊列），我們隻需要拿過來用就可以了。
我們知道樹是圖的一種特殊退化形式。同時如果對圖的深度優先周遊和廣度優先周遊有比較深刻的了解，将不難看出這種周遊方式實際上是一種廣度優先周遊。是以這道題的本質是在二進制樹上實作廣度優先周遊。
參考代碼：
#include <deque>
#include <iostream>
using namespacestd;
struct BTreeNode // anode in the binary tree
{
int m_nValue; //value of node
BTreeNode *m_pLeft; // left child of node
BTreeNode *m_pRight; // rightchild of node
};
///
// Print a binary tree from top level to bottom level
// Input: pTreeRoot - the root of binary tree
///
void PrintFromTopToBottom(BTreeNode*pTreeRoot)
{
if(!pTreeRoot)
return;
// get aempty queue
deque<BTreeNode *>dequeTreeNode;
// insertthe root at the tail of queue
dequeTreeNode.push_back(pTreeRoot);
while(dequeTreeNode.size())
{
// get anode from the head of queue
BTreeNode *pNode =dequeTreeNode.front();
dequeTreeNode.pop_front();
// printthe node
cout <<pNode->m_nValue << ' ';
// printits left child sub-tree if it has
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
// printits right child sub-tree if it has
if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
}
(13)－第一個隻出現一次的字元
題目：在一個字元串中找到第一個隻出現一次的字元。如輸入abaccdeff，則輸出b。
分析：這道題是2006年google的一道筆試題。
看到這道題時，最直覺的想法是從頭開始掃描這個字元串中的每個字元。當通路到某字元時拿這個字元和後面的每個字元相比較，如果在後面沒有發現重複的字元，則該字元就是隻出現一次的字元。如果字元串有n個字元，每個字元可能與後面的O(n)個字元相比較，是以這種思路時間複雜度是O(n2)。我們試着去找一個更快的方法。
由于題目與字元出現的次數相關，我們是不是可以統計每個字元在該字元串中出現的次數？要達到這個目的，我們需要一個資料容器來存放每個字元的出現次數。在這個資料容器中可以根據字元來查找它出現的次數，也就是說這個容器的作用是把一個字元映射成一個數字。在常用的資料容器中，哈希表正是這個用途。
哈希表是一種比較複雜的資料結構。由于比較複雜，STL中沒有實作哈希表，是以需要我們自己實作一個。但由于本題的特殊性，我們隻需要一個非常簡單的哈希表就能滿足要求。由于字元（char）是一個長度為8的資料類型，是以總共有可能256 種可能。于是我們建立一個長度為256的數組，每個字母根據其ASCII碼值作為數組的下标對應數組的對應項，而數組中存儲的是每個字元對應的次數。這樣我們就建立了一個大小為256，以字元ASCII碼為鍵值的哈希表。
我們第一遍掃描這個數組時，每碰到一個字元，在哈希表中找到對應的項并把出現的次數增加一次。這樣在進行第二次掃描時，就能直接從哈希表中得到每個字元出現的次數了。
參考代碼如下：
///
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///
char FirstNotRepeatingChar(char*pString)
{
// invalidinput
if(!pString)
return0;
// get ahash table, and initialize it
constinttableSize=256;
unsignedinthashTable[tableSize];
for(unsignedinti= 0; i<tableSize; ++ i)
hashTable[i] = 0;
// get thehow many times each char appears in the string
char*pHashKey = pString;
while(*(pHashKey)!= '\0')
hashTable[*(pHashKey++)] ++;
// find thefirst char which appears only once in a string
pHashKey = pString;
while(*pHashKey!= '\0')
{
if(hashTable[*pHashKey]== 1)
return*pHashKey;
pHashKey++;
}
// if thestring is empty
// orevery char in the string appears at least twice
return0;
}
(14)－圓圈中最後剩下的數字
題目：n個數字（0,1,…,n-1）形成一個圓圈，從數字0開始，每次從這個圓圈中删除第m個數字（第一個為目前數字本身，第二個為目前數字的下一個數字）。當一個數字删除後，從被删除數字的下一個繼續删除第m個數字。求出在這個圓圈中剩下的最後一個數字。
分析：既然題目有一個數字圓圈，很自然的想法是我們用一個資料結構來模拟這個圓圈。在常用的資料結構中，我們很容易想到用環形清單。我們可以建立一個總共有m個數字的環形清單，然後每次從這個清單中删除第m個元素。
在參考代碼中，我們用STL中std::list來模拟這個環形清單。由于list并不是一個環形的結構，是以每次跌代器掃描到清單末尾的時候，要記得把跌代器移到清單的頭部。這樣就是按照一個圓圈的順序來周遊這個清單了。
這種思路需要一個有n個結點的環形清單來模拟這個删除的過程，是以記憶體開銷為O(n)。而且這種方法每删除一個數字需要m步運算，總共有n個數字，是以總的時間複雜度是O(mn)。當m和n都很大的時候，這種方法是很慢的。
接下來我們試着從數學上分析出一些規律。首先定義最初的n個數字（0,1,…,n-1）中最後剩下的數字是關于n和m的方程為f(n,m)。
在這n個數字中，第一個被删除的數字是m%n-1，為簡單起見記為k。那麼删除k之後的剩下n-1的數字為0,1,…,k-1,k+1,…,n-1，并且下一個開始計數的數字是k+1。相當于在剩下的序列中，k+1排到最前面，進而形成序列k+1,…,n-1,0,…k-1。該序列最後剩下的數字也應該是關于n和m的函數。由于這個序列的規律和前面最初的序列不一樣（最初的序列是從0開始的連續序列），是以該函數不同于前面函數，記為f’(n-1,m)。最初序列最後剩下的數字f(n,m)一定是剩下序列的最後剩下數字f’(n-1,m)，是以f(n,m)=f’(n-1,m)。
接下來我們把剩下的的這n-1個數字的序列k+1,…,n-1,0,…k-1作一個映射，映射的結果是形成一個從0到n-2的序列：
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
把映射定義為p，則p(x)= (x-k-1)%n，即如果映射前的數字是x，則映射後的數字是(x-k-1)%n。對應的逆映射是p-1(x)=(x+k+1)%n。
由于映射之後的序列和最初的序列有同樣的形式，都是從0開始的連續序列，是以仍然可以用函數f來表示，記為f(n-1,m)。根據我們的映射規則，映射之前的序列最後剩下的數字f’(n-1,m)= p-1[f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。
經過上面複雜的分析，我們終于找到一個遞歸的公式。要得到n個數字的序列的最後剩下的數字，隻需要得到n-1個數字的序列的最後剩下的數字，并可以依此類推。當n=1時，也就是序列中開始隻有一個數字0，那麼很顯然最後剩下的數字就是0。我們把這種關系表示為：
0 n=1
f(n,m)={
[f(n-1,m)+m]%n n>1
盡管得到這個公式的分析過程非常複雜，但它用遞歸或者循環都很容易實作。最重要的是，這是一種時間複雜度為O(n)，空間複雜度為O(1)的方法，是以無論在時間上還是空間上都優于前面的思路。
思路一的參考代碼：
///
// n integers (0, 1, ... n - 1) form a circle. Remove the mth from
// the circle at every time. Find the last number remaining
// Input: n - the number of integers in the circle initially
// m - remove the mth number atevery time
// Output: the last number remaining when the input is valid,
// otherwise -1
///
int LastRemaining_Solution1(unsignedint n, unsignedint m)
{
// invalidinput
if(n< 1 || m < 1)
return-1;
unsignedint i = 0;
// initiatea list with n integers (0, 1, ... n - 1)
list<int> integers;
for(i= 0; i < n; ++ i)
integers.push_back(i);
list<int>::iteratorcurinteger = integers.begin();
while(integers.size()> 1)
{
// findthe mth integer. Note that std::list is not a circle
//so we should handle it manually
for(int i = 1; i < m; ++ i)
{
curinteger ++;
if(curinteger== integers.end())
curinteger =integers.begin();
}
// removethe mth integer. Note that std::list is not a circle
//so we should handle it manually
list<int>::iterator nextinteger = ++ curinteger;
if(nextinteger== integers.end())
nextinteger = integers.begin();
-- curinteger;
integers.erase(curinteger);
curinteger = nextinteger;
}
return*(curinteger);
}
思路二的參考代碼：
///
// n integers (0, 1, ... n - 1) form a circle. Remove the mth from
// the circle at every time. Find the last number remaining
// Input: n - the number of integers in the circle initially
// m - remove the mth number atevery time
// Output: the last number remaining when the input is valid,
// otherwise -1
///
int LastRemaining_Solution2(intn, unsigned intm)
{
// invalidinput
if(n<= 0 || m < 0)
return-1;
// if thereare only one integer in the circle initially,
// ofcourse the last remaining one is 0
intlastinteger = 0;
// find thelast remaining one in the circle with n integers
for(int i = 2; i <= n; i ++)
lastinteger = (lastinteger + m) %i;
returnlastinteger;
}
如果對兩種思路的時間複雜度感興趣的讀者可以把n和m的值設的稍微大一點，比如十萬這個數量級的數字，運作的時候就能明顯感覺出這兩種思路寫出來的代碼時間效率大不一樣。
(15)－含有指針成員的類的拷貝
題目：下面是一個數組類的聲明與實作。請分析這個類有什麼問題，并針對存在的問題提出幾種解決方案。
template<typename T>class Array
{
public:
Array(unsignedarraySize):data(0), size(arraySize)
{
if(size> 0)
data = newT[size];
}
~Array()
{
if(data)delete[] data;
}
voidsetValue(unsigned index, const T& value)
{
if(index< size)
data[index] = value;
}
T getValue(unsignedindex) const
{
if(index< size)
returndata[index];
else
returnT();
}
private:
T* data;
unsignedsize;
};
分析：我們注意在類的内部封裝了用來存儲數組資料的指針。軟體存在的大部分問題通常都可以歸結指針的不正确處理。
這個類隻提供了一個構造函數，而沒有定義構造拷貝函數和重載拷貝運算符函數。當這個類的使用者按照下面的方式聲明并執行個體化該類的一個執行個體
Array A(10);
Array B(A);
或者按照下面的方式把該類的一個執行個體指派給另外一個執行個體
Array A(10);
Array B(10);
B=A;
編譯器将調用其自動生成的構造拷貝函數或者拷貝運算符的重載函數。在編譯器生成的預設的構造拷貝函數和拷貝運算符的重載函數，對指針實行的是按位拷貝，僅僅隻是拷貝指針的位址，而不會拷貝指針的内容。是以在執行完前面的代碼之後，A.data和B.data指向的同一位址。當A或者B中任意一個結束其生命周期調用析構函數時，會删除data。由于他們的data指向的是同一個地方，兩個執行個體的data都被删除了。但另外一個執行個體并不知道它的data已經被删除了，當企圖再次用它的data的時候，程式就會不可避免地崩潰。
由于問題出現的根源是調用了編譯器生成的預設構造拷貝函數和拷貝運算符的重載函數。一個最簡單的辦法就是禁止使用這兩個函數。于是我們可以把這兩個函數聲明為私有函數，如果類的使用者企圖調用這兩個函數，将不能通過編譯。實作的代碼如下：
private:
Array(constArray& copy);
constArray& operator = (constArray& copy);
最初的代碼存在問題是因為不同執行個體的data指向的同一位址，删除一個執行個體的data會把另外一個執行個體的data也同時删除。是以我們還可以讓構造拷貝函數或者拷貝運算符的重載函數拷貝的不隻是位址，而是資料。由于我們重新存儲了一份資料，這樣一個執行個體删除的時候，對另外一個執行個體沒有影響。這種思路我們稱之為深度拷貝。實作的代碼如下：
public:
Array(constArray& copy):data(0), size(copy.size)
{
if(size> 0)
{
data = newT[size];
for(int i = 0; i < size; ++ i)
setValue(i,copy.getValue(i));
}
}
constArray& operator = (constArray& copy)
{
if(this == ©)
return*this;
if(data!= NULL)
{
delete[]data;
data = NULL;
}
size = copy.size;
if(size> 0)
{
data = newT[size];
for(int i = 0; i < size; ++ i)
setValue(i,copy.getValue(i));
}
}
為了防止有多個指針指向的資料被多次删除，我們還可以儲存究竟有多少個指針指向該資料。隻有當沒有任何指針指向該資料的時候才可以被删除。這種思路通常被稱之為引用計數技術。在構造函數中，引用計數初始化為1；每當把這個執行個體指派給其他執行個體或者以參數傳給其他執行個體的構造拷貝函數的時候，引用計數加1，因為這意味着又多了一個執行個體指向它的data；每次需要調用析構函數或者需要把data指派為其他資料的時候，引用計數要減1，因為這意味着指向它的data的指針少了一個。當引用計數減少到0的時候，data已經沒有任何執行個體指向它了，這個時候就可以安全地删除。實作的代碼如下：
public:
Array(unsignedarraySize)
:data(0), size(arraySize), count(new unsigned int)
{
*count = 1;
if(size> 0)
data = newT[size];
}
Array(constArray& copy)
: size(copy.size), data(copy.data),count(copy.count)
{
++ (*count);
}
~Array()
{
Release();
}
constArray& operator = (constArray& copy)
{
if(data== copy.data)
return*this;
Release();
data = copy.data;
size = copy.size;
count = copy.count;
++(*count);
}
private:
voidRelease()
{
--(*count);
if(*count== 0)
{
if(data)
{
delete[]data;
data = NULL;
}
deletecount;
count = 0;
}
}
unsignedint *count;
(16)－O(logn)求Fibonacci數列
題目：定義Fibonacci數列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數列的第n項。
分析：在很多C語言教科書中講到遞歸函數的時候，都會用Fibonacci作為例子。是以很多程式員對這道題的遞歸解法非常熟悉，看到題目就能寫出如下的遞歸求解的代碼。
///
// Calculate the nth item of Fibonacci Series recursively
///
long longFibonacci_Solution1(unsigned int n)
{
intresult[2] = {0, 1};
if(n< 2)
returnresult[n];
returnFibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}
但是，教科書上反複用這個題目來講解遞歸函數，并不能說明遞歸解法最适合這道題目。我們以求解f(10)作為例子來分析遞歸求解的過程。要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和f(7)……我們用樹形結構來表示這種依賴關系
f(10)
/ \
f(9) f(8)
/ \ / \
f(8) f(7) f(6) f(5)
/ \ / \
f(7) f(6) f(6) f(5)
我們不難發現在這棵樹中有很多結點會重複的，而且重複的結點數會随着n的增大而急劇增加。這意味這計算量會随着n的增大而急劇增大。事實上，用遞歸方法計算的時間複雜度是以n的指數的方式遞增的。大家可以求Fibonacci的第100項試試，感受一下這樣遞歸會慢到什麼程度。在我的機器上，連續運作了一個多小時也沒有出來結果。
其實改進的方法并不複雜。上述方法之是以慢是因為重複的計算太多，隻要避免重複計算就行了。比如我們可以把已經得到的數列中間項儲存起來，如果下次需要計算的時候我們先查找一下，如果前面已經計算過了就不用再次計算了。
更簡單的辦法是從下往上計算，首先根據f(0)和f(1)算出f(2)，在根據f(1)和f(2)算出f(3)……依此類推就可以算出第n項了。很容易了解，這種思路的時間複雜度是O(n)。
///
// Calculate the nth item of Fibonacci Series iteratively
///
long longFibonacci_Solution2(unsigned n)
{
intresult[2] = {0, 1};
if(n< 2)
returnresult[n];
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
for(unsigned int i = 2; i<= n; ++ i)
{
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
returnfibN;
}
這還不是最快的方法。下面介紹一種時間複雜度是O(logn)的方法。在介紹這種方法之前，先介紹一個數學公式：
{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1
(注：{f(n+1), f(n), f(n), f(n-1)}表示一個矩陣。在矩陣中第一行第一列是f(n+1)，第一行第二列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)
有了這個公式，要求得f(n)，我們隻需要求得矩陣{1, 1, 1,0}的n-1次方，因為矩陣{1, 1, 1,0}的n-1次方的結果的第一行第一列就是f(n)。這個數學公式用數學歸納法不難證明。感興趣的朋友不妨自己證明一下。
現在的問題轉換為求矩陣{1, 1, 1, 0}的乘方。如果簡單第從0開始循環，n次方将需要n次運算，并不比前面的方法要快。但我們可以考慮乘方的如下性質：
/ an/2*an/2 n為偶數時
an=
\ a(n-1)/2*a(n-1)/2 n為奇數時
要求得n次方，我們先求得n/2次方，再把n/2的結果平方一下。如果把求n次方的問題看成一個大問題，把求n/2看成一個較小的問題。這種把大問題分解成一個或多個小問題的思路我們稱之為分治法。這樣求n次方就隻需要logn次運算了。
實作這種方式時，首先需要定義一個2×2的矩陣，并且定義好矩陣的乘法以及乘方運算。當這些運算定義好了之後，剩下的事情就變得非常簡單。完整的實作代碼如下所示。
#include <cassert>
///
// A 2 by 2 matrix
///
struct Matrix2By2
{
Matrix2By2
(
longlong m00 = 0,
longlong m01 = 0,
longlong m10 = 0,
longlong m11 = 0
)
:m_00(m00), m_01(m01), m_10(m10),m_11(m11)
{
}
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};
///
// Multiply two matrices
// Input: matrix1 - the first matrix
// matrix2 - the second matrix
//Output: the production of two matrices
///
Matrix2By2 MatrixMultiply
(
constMatrix2By2& matrix1,
constMatrix2By2& matrix2
)
{
returnMatrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01* matrix2.m_10,
matrix1.m_00 * matrix2.m_01 +matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 +matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 +matrix1.m_11 * matrix2.m_11);
}
///
// The nth power of matrix
// 1 1
// 1 0
///
Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > 0);
Matrix2By2 matrix;
if(n== 1)
{
matrix = Matrix2By2(1, 1, 1, 0);
}
else if(n % 2 == 0)
{
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix,matrix);
}
else if(n % 2 == 1)
{
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix,matrix);
matrix = MatrixMultiply(matrix,Matrix2By2(1, 1, 1, 0));
}
returnmatrix;
}
///
// Calculate the nth item of Fibonacci Series using devide and conquer
///
long longFibonacci_Solution3(unsigned int n)
{
intresult[2] = {0, 1};
if(n< 2)
returnresult[n];
Matrix2By2 PowerNMinus2 =MatrixPower(n - 1);
returnPowerNMinus2.m_00;
}
(17)－把字元串轉換成整數
題目：輸入一個表示整數的字元串，把該字元串轉換成整數并輸出。例如輸入字元串"345"，則輸出整數345。
分析：這道題盡管不是很難，學過C/C++語言一般都能實作基本功能，但不同程式員就這道題寫出的代碼有很大差別，可以說這道題能夠很好地反應出程式員的思維和程式設計習慣，是以已經被包括微軟在内的多家公司用作面試題。建議讀者在往下看之前自己先編寫代碼，再比較自己寫的代碼和下面的參考代碼有哪些不同。
首先我們分析如何完成基本功能，即如何把表示整數的字元串正确地轉換成整數。還是以"345"作為例子。當我們掃描到字元串的第一個字元'3'時，我們不知道後面還有多少位，僅僅知道這是第一位，是以此時得到的數字是3。當掃描到第二個數字'4'時，此時我們已經知道前面已經一個3了，再在後面加上一個數字4，那前面的3相當于30，是以得到的數字是3*10+4=34。接着我們又掃描到字元'5'，我們已經知道了'5'的前面已經有了34，由于後面要加上一個5，前面的34就相當于340了，是以得到的數字就是34*10+5=345。
分析到這裡，我們不能得出一個轉換的思路：每掃描到一個字元，我們把在之前得到的數字乘以10再加上目前字元表示的數字。這個思路用循環不難實作。
由于整數可能不僅僅之含有數字，還有可能以'+'或者'-'開頭，表示整數的正負。是以我們需要把這個字元串的第一個字元做特殊處理。如果第一個字元是'+'号，則不需要做任何操作；如果第一個字元是'-'号，則表明這個整數是個負數，在最後的時候我們要把得到的數值變成負數。
接着我們試着處理非法輸入。由于輸入的是指針，在使用指針之前，我們要做的第一件是判斷這個指針是不是為空。如果試着去通路空指針，将不可避免地導緻程式崩潰。另外，輸入的字元串中可能含有不是數字的字元。每當碰到這些非法的字元，我們就沒有必要再繼續轉換。最後一個需要考慮的問題是溢出問題。由于輸入的數字是以字元串的形式輸入，是以有可能輸入一個很大的數字轉換之後會超過能夠表示的最大的整數而溢出。
現在已經分析的差不多了，開始考慮編寫代碼。首先我們考慮如何聲明這個函數。由于是把字元串轉換成整數，很自然我們想到：
int StrToInt(const char*str);
這樣聲明看起來沒有問題。但當輸入的字元串是一個空指針或者含有非法的字元時，應該傳回什麼值呢？0怎麼樣？那怎麼區分非法輸入和字元串本身就是”0”這兩種情況呢？
接下來我們考慮另外一種思路。我們可以傳回一個布爾值來訓示輸入是否有效，而把轉換後的整數放到參數清單中以引用或者指針的形式傳入。于是我們就可以聲明如下：
bool StrToInt(const char*str, int& num);
這種思路解決了前面的問題。但是這個函數的使用者使用這個函數的時候會覺得不是很友善，因為他不能直接把得到的整數指派給其他整形變臉，顯得不夠直覺。
前面的第一種聲明就很直覺。如何在保證直覺的前提下當碰到非法輸入的時候通知使用者呢？一種解決方案就是定義一個全局變量，每當碰到非法輸入的時候，就标記該全局變量。使用者在調用這個函數之後，就可以檢驗該全局變量來判斷轉換是不是成功。
下面我們寫出完整的實作代碼。參考代碼：
enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;
///
// Convert a string into an integer
///
int StrToInt(constchar* str)
{
g_nStatus = kInvalid;
longlongnum = 0;
if(str!= NULL)
{
constchar* digit = str;
// thefirst char in the string maybe '+' or '-'
boolminus = false;
if(*digit== '+')
digit ++;
elseif(*digit == '-')
{
digit ++;
minus = true;
}
// theremaining chars in the string
while(*digit!= '\0')
{
if(*digit>= '0' && *digit <= '9')
{
num = num * 10 + (*digit - '0');
// overflow
if(num>std::numeric_limits<int>::max())
{
num = 0;
break;
}
digit++;
}
// ifthe char is not a digit, invalid input
else
{
num = 0;
break;
}
}
if(*digit== '\0')
{
g_nStatus = kValid;
if(minus)
num = 0 - num;
}
}
returnstatic_cast<int>(num);
}
讨論：在參考代碼中，我選用的是第一種聲明方式。不過在面試時，我們可以選用任意一種聲明方式進行實作。但當面試官問我們選擇的理由時，我們要對兩者的優缺點進行評價。第一種聲明方式對使用者而言非常直覺，但使用了全局變量，不夠優雅；而第二種思路是用傳回值來表明輸入是否合法，在很多API中都用這種方法，但該方法聲明的函數使用起來不夠直覺。
最後值得一提的是，在C語言提供的庫函數中，函數atoi能夠把字元串轉換整數。它的聲明是int atoi(const char *str)。該函數就是用一個全局變量來标志輸入是否合法的。
(18)－用兩個棧實作隊列
題目：某隊列的聲明如下：
template<typename T>class CQueue
{
public:
CQueue() {}
~CQueue() {}
voidappendTail(const T& node); // append a elementto tail
voiddeleteHead(); // remove a element from head
private:
T>m_stack1;
T>m_stack2;
};
分析：從上面的類的聲明中，我們發現在隊列中有兩個棧。是以這道題實質上是要求我們用兩個棧來實作一個隊列。相信大家對棧和隊列的基本性質都非常了解了：棧是一種後入先出的資料容器，是以對隊列進行的插入和删除操作都是在棧頂上進行；隊列是一種先入先出的資料容器，我們總是把新元素插入到隊列的尾部，而從隊列的頭部删除元素。
我們通過一個具體的例子來分析往該隊列插入和删除元素的過程。首先插入一個元素a，不妨把先它插入到m_stack1。這個時候m_stack1中的元素有{a}，m_stack2為空。再插入兩個元素b和c，還是插入到m_stack1中，此時m_stack1中的元素有{a,b,c}，m_stack2中仍然是空的。
這個時候我們試着從隊列中删除一個元素。按照隊列先入先出的規則，由于a比b、c先插入到隊列中，這次被删除的元素應該是a。元素a存儲在m_stack1中，但并不在棧頂上，是以不能直接進行删除。注意到m_stack2我們還一直沒有使用過，現在是讓m_stack2起作用的時候了。如果我們把m_stack1中的元素逐個pop出來并push進入m_stack2，元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。是以經過兩次pop和push之後，m_stack1為空，而m_stack2中的元素是{c,b,a}。這個時候就可以pop出m_stack2的棧頂a了。pop之後的m_stack1為空，而m_stack2的元素為{c,b}，其中b在棧頂。
這個時候如果我們還想繼續删除應該怎麼辦呢？在剩下的兩個元素中b和c，b比c先進入隊列，是以b應該先删除。而此時b恰好又在棧頂上，是以可以直接pop出去。這次pop之後，m_stack1中仍然為空，而m_stack2為{c}。
從上面的分析我們可以總結出删除一個元素的步驟：當m_stack2中不為空時，在m_stack2中的棧頂元素是最先進入隊列的元素，可以pop出去。如果m_stack2為空時，我們把m_stack1中的元素逐個pop出來并push進入m_stack2。由于先進入隊列的元素被壓到m_stack1的底端，經過pop和push之後就處于m_stack2的頂端了，又可以直接pop出去。
接下來我們再插入一個元素d。我們是不是還可以把它push進m_stack1？這樣會不會有問題呢？我們說不會有問題。因為在删除元素的時候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進入隊列的，可以直接pop；如果m_stack2為空，我們把m_stack1中的元素pop出來并push進入m_stack2。由于m_stack2中元素的順序和m_stack1相反，最先進入隊列的元素還是處于m_stack2的棧頂，仍然可以直接pop。不會出現任何沖突。
我們用一個表來總結一下前面的例子執行的步驟：
| 操作 | m_stack1 | m_stack2 |
| append a | {a} | {} |
| append b | {a,b} | {} |
| append c | {a,b,c} | {} |
| delete head | {} | {b,c} |
| delete head | {} | {c} |
| append d | {d} | {c} |
| delete head | {d} | {} |
總結完push和pop對應的過程之後，我們可以開始動手寫代碼了。參考代碼如下：
///
// Append a element at the tail of the queue
///
template<typename T>void CQueue<T>::appendTail(const T& element)
{
// push thenew element into m_stack1
m_stack1.push(element);
}
///
// Delete the head from the queue
///
template<typename T>void CQueue<T>::deleteHead()
{
// ifm_stack2is empty,and there are some
//elements inm_stack1, push them in m_stack2
if(m_stack2.size()<= 0)
{
while(m_stack1.size()>0)
{
T&data =m_stack1.top();
m_stack1.pop();
m_stack2.push(data);
}
}
// push theelement into m_stack2
assert(m_stack2.size()>0);
m_stack2.pop();
}
擴充：這道題是用兩個棧實作一個隊列。反過來能不能用兩個隊列實作一個棧？如果可以，該如何實作？
(19)－反轉連結清單
題目：輸入一個連結清單的頭結點，反轉該連結清單，并傳回反轉後連結清單的頭結點。連結清單結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應出程式員思維是否嚴密，在微軟之後已經有很多公司在面試時采用了這道題。
為了正确地反轉一個連結清單，需要調整指針的指向。與指針操作相關代碼總是容易出錯的，是以最好在動手寫程式之前作全面的分析。在面試的時候不急于動手而是一開始做仔細的分析和設計，将會給面試官留下很好的印象，因為在實際的軟體開發中，設計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠不如用較多的時間寫出一段健壯的代碼。
為了将調整指針這個複雜的過程分析清楚，我們可以借助圖形來直覺地分析。假設下圖中l、m和n是三個相鄰的結點：
aßbß…ßl mànà…
假設經過若幹操作，我們已經把結點l之前的指針調整完畢，這些結點的m_pNext指針都指向前面一個結點。現在我們周遊到結點m。當然，我們需要把調整結點的m_pNext指針讓它指向結點l。但注意一旦調整了指針的指向，連結清單就斷開了，如下圖所示：
aßbß…lßm nà…
因為已經沒有指針指向結點n，我們沒有辦法再周遊到結點n了。是以為了避免連結清單斷開，我們需要在調整m的m_pNext之前要把n儲存下來。
接下來我們試着找到反轉後連結清單的頭結點。不難分析出反轉後連結清單的頭結點是原始連結清單的尾位結點。什麼結點是尾結點？就是m_pNext為空指針的結點。
基于上述分析，我們不難寫出如下代碼：
///
// Reverse a list iteratively
// Input: pHead - the head of the original list
// Output: the head of the reversed head
///
ListNode*ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode!= NULL)
{
// getthe next node, and save it at pNext
ListNode* pNext =pNode->m_pNext;
// if thenext node is null, the currect is the end of original
//list, and it's the head of the reversed list
if(pNext== NULL)
pReversedHead = pNode;
//reverse the linkage between nodes
pNode->m_pNext = pPrev;
// moveforward on the the list
pPrev = pNode;
pNode = pNext;
}
returnpReversedHead;
}
擴充：本題也可以遞歸實作。感興趣的讀者請自己編寫遞歸代碼。
(20)－最長公共子串
題目：如果字元串一的所有字元按其在字元串中的順序出現在另外一個字元串二中，則字元串一稱之為字元串二的子串。注意，并不要求子串（字元串一）的字元必須連續出現在字元串二中。請編寫一個函數，輸入兩個字元串，求它們的最長公共子串，并列印出最長公共子串。
例如：輸入兩個字元串BDCABA和ABCBDAB，字元串BCBA和BDAB都是是它們的最長公共子串，則輸出它們的長度4，并列印任意一個子串。
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經典的動态規劃題，是以一些重視算法的公司像MicroStrategy都把它當作面試題。
完整介紹動态規劃将需要很長的篇幅，是以我不打算在此全面讨論動态規劃相關的概念，隻集中對LCS直接相關内容作讨論。如果對動态規劃不是很熟悉，請參考相關算法書比如算法讨論。
先介紹LCS問題的性質：記Xm={x0,x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個字元串，而Zk={z0,z1,…zk-1}是它們的LCS，則：
1. 如果xm-1=yn-1，那麼zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS；
2. 如果xm-1≠yn-1，那麼當zk-1≠xm-1時Z是Xm-1和Y的LCS；
3. 如果xm-1≠yn-1，那麼當zk-1≠yn-1時Z是Yn-1和X的LCS；
下面簡單證明一下這些性質：
1. 如果zk-1≠xm-1，那麼我們可以把xm-1（yn-1）加到Z中得到Z’，這樣就得到X和Y的一個長度為k+1的公共子串Z’。這就與長度為k的Z是X和Y的LCS相沖突了。是以一定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我們删除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個公共子串，現在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設有Xm-1和Yn-1有一個長度超過k-1的公共子串W，那麼我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長度超過k，這就和已知條件相沖突了。
2. 還是用反證法證明。假設Z不是Xm-1和Y的LCS，則存在一個長度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。沖突。
3. 證明同2。
有了上面的性質，我們可以得出如下的思路：求兩字元串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，如果xm-1=yn-1，那麼隻需求得Xm-1和Yn-1的LCS，并在其後添加xm-1（yn-1）即可；如果xm-1≠yn-1，我們分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個LCS中較長的一個為X和Y的LCS。
如果我們記字元串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求c[i,j]：
/ 0 if i<0 orj<0
c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj
\ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
上面的公式用遞歸函數不難求得。但從前面求Fibonacci第n項(本面試題系列第16題）的分析中我們知道直接遞歸會有很多重複計算，我們用從底向上循環求解的思路效率更高。
為了能夠采用循環求解的思路，我們用一個矩陣（參考代碼中的LCS_length）儲存下來目前已經計算好了的c[i,j]，當後面的計算需要這些資料時就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個方向計算得到，相當于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個各自移動到c[i,j]，是以在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中隻有向左上方移動時才表明找到LCS中的一個字元。于是我們需要用另外一個矩陣（參考代碼中的LCS_direction）儲存移動的方向。
參考代碼如下：
#include "string.h"
// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp,kLeftUp};
/
// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1 - the firststring
// pStr2 - the second string
// Output: the length of two strings' LCSs
/
int LCS(char*pStr1, char* pStr2)
{
if(!pStr1|| !pStr2)
return0;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(!length1|| !length2)
return0;
size_t i, j;
// initiate the length matrix
int**LCS_length;
LCS_length = (int**)(new int[length1]);
for(i= 0; i < length1; ++ i)
LCS_length[i] = (int*)new int[length2];
for(i= 0; i < length1; ++ i)
for(j= 0; j < length2; ++ j)
LCS_length[i][j] = 0;
// initiate the direction matrix
int**LCS_direction;
LCS_direction = (int**)(new int[length1]);
for( i= 0; i < length1; ++ i)
LCS_direction[i] = (int*)new int[length2];
for(i= 0; i < length1; ++ i)
for(j= 0; j < length2; ++ j)
LCS_direction[i][j] = kInit;
for(i= 0; i < length1; ++ i)
{
for(j= 0; j < length2; ++ j)
{
if(i== 0 || j == 0)
{
if(pStr1[i]== pStr2[j])
{
LCS_length[i][j] = 1;
LCS_direction[i][j]= kLeftUp;
}
else
LCS_length[i][j]= 0;
}
// achar of LCS is found,
//it comes from the left up entry in the direction matrix
elseif(pStr1[i] == pStr2[j])
{
LCS_length[i][j] =LCS_length[i - 1][j - 1] + 1;
LCS_direction[i][j] =kLeftUp;
}
// itcomes from the up entry in the direction matrix
elseif(LCS_length[i - 1][j] > LCS_length[i][j -1])
{
LCS_length[i][j] =LCS_length[i - 1][j];
LCS_direction[i][j] = kUp;
}
// itcomes from the left entry in the direction matrix
else
{
LCS_length[i][j] =LCS_length[i][j - 1];
LCS_direction[i][j] = kLeft;
}
}
}
LCS_Print(LCS_direction, pStr1, pStr2,length1 - 1, length2 - 1);
returnLCS_length[length1 - 1][length2 - 1];
}
/
// Print a LCS for two strings
// Input: LCS_direction - a 2d matrix which records the direction of
// LCS generation
// pStr1 - the first string
// pStr2 - the second string
// row - the row index in the matrixLCS_direction
// col - the column index in the matrixLCS_direction
/
void LCS_Print(int**LCS_direction,
char* pStr1, char* pStr2,
size_t row, size_t col)
{
if(pStr1== NULL || pStr2 == NULL)
return;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(length1 == 0 || length2 == 0 || !(row <length1 && col < length2))
return;
// kLeftUpimplies a char in the LCS is found
if(LCS_direction[row][col]== kLeftUp)
{
if(row> 0 && col > 0)
LCS_Print(LCS_direction, pStr1,pStr2, row - 1, col - 1);
// print the char
printf("%c", pStr1[row]);
}
else if(LCS_direction[row][col] == kLeft)
{
// moveto the left entry in the direction matrix
if(col> 0)
LCS_Print(LCS_direction, pStr1,pStr2, row, col - 1);
}
else if(LCS_direction[row][col] == kUp)
{
// moveto the up entry in the direction matrix
if(row> 0)
LCS_Print(LCS_direction, pStr1,pStr2, row - 1, col);
}
}
擴充：如果題目改成求兩個字元串的最長公共子字元串，應該怎麼求？子字元串的定義和子串的定義類似，但要求是連續分布在其他字元串中。比如輸入兩個字元串BDCABA和ABCBDAB的最長公共字元串有BD和AB，它們的長度都是2。
(21)－左旋轉字元串
題目：定義字元串的左旋轉操作：把字元串前面的若幹個字元移動到字元串的尾部。如把字元串abcdef左旋轉2位得到字元串cdefab。請實作字元串左旋轉的函數。要求時間對長度為n的字元串操作的複雜度為O(n)，輔助記憶體為O(1)。
分析：如果不考慮時間和空間複雜度的限制，最簡單的方法莫過于把這道題看成是把字元串分成前後兩部分，通過旋轉操作把這兩個部分交換位置。于是我們可以新開辟一塊長度為n+1的輔助空間，把原字元串後半部分拷貝到新空間的前半部分，在把原字元串的前半部分拷貝到新空間的後半部分。不難看出，這種思路的時間複雜度是O(n)，需要的輔助空間也是O(n)。
接下來的一種思路可能要稍微麻煩一點。我們假設把字元串左旋轉m位。于是我們先把第0個字元儲存起來，把第m個字元放到第0個的位置，在把第2m個字元放到第m個的位置…依次類推，一直移動到最後一個可以移動字元，最後在把原來的第0個字元放到剛才移動的位置上。接着把第1個字元儲存起來，把第m+1個元素移動到第1個位置…重複前面處理第0個字元的步驟，直到處理完前面的m個字元。
該思路還是比較容易了解，但當字元串的長度n不是m的整數倍的時候，寫程式會有些麻煩，感興趣的朋友可以自己試一下。由于下面還要介紹更好的方法，這種思路的代碼我就不提供了。
我們還是把字元串看成有兩段組成的，記位XY。左旋轉相當于要把字元串XY變成YX。我們先在字元串上定義一種翻轉的操作，就是翻轉字元串中字元的先後順序。把X翻轉後記為XT。顯然有(XT)T=X。
我們首先對X和Y兩段分别進行翻轉操作，這樣就能得到XTYT。接着再對XTYT進行翻轉操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我們期待的結果。
分析到這裡我們再回到原來的題目。我們要做的僅僅是把字元串分成兩段，第一段為前面m個字元，其餘的字元分到第二段。再定義一個翻轉字元串的函數，按照前面的步驟翻轉三次就行了。時間複雜度和空間複雜度都合乎要求。
參考代碼如下：
#include "string.h"
///
// Move the first n chars in a string to its end
///
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr!= NULL)
{
intnLength = static_cast<int>(strlen(pStr));
if(nLength> 0 || n == 0 || n > nLength)
{
char*pFirstStart = pStr;
char*pFirstEnd = pStr + n - 1;
char*pSecondStart = pStr + n;
char*pSecondEnd = pStr + nLength - 1;
//reverse the first part of the string
ReverseString(pFirstStart,pFirstEnd);
//reverse the second part of the strint
ReverseString(pSecondStart,pSecondEnd);
//reverse the whole string
ReverseString(pFirstStart,pSecondEnd);
}
}
returnpStr;
}
///
// Reverse the string between pStart and pEnd
///
void ReverseString(char* pStart, char*pEnd)
{
if(pStart== NULL || pEnd == NULL)
{
while(pStart<= pEnd)
{
chartemp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
(22)－整數的二進制表示中1的個數
題目：輸入一個整數，求該整數的二進制表達中有多少個1。例如輸入10，由于其二進制表示為1010，有兩個1，是以輸出2。
分析：這是一道很基本的考查位運算的面試題。包括微軟在内的很多公司都曾采用過這道題。
一個很基本的想法是，我們先判斷整數的最右邊一位是不是1。接着把整數右移一位，原來處于右邊第二位的數字現在被移到第一位了，再判斷是不是1。這樣每次移動一位，直到這個整數變成0為止。現在的問題變成怎樣判斷一個整數的最右邊一位是不是1了。很簡單，如果它和整數1作與運算。由于1除了最右邊一位以外，其他所有位都為0。是以如果與運算的結果為1，表示整數的最右邊一位是1，否則是0。
得到的代碼如下：
///
// Get how many 1s in an integer's binary expression
///
int NumberOf1_Solution1(inti)
{
intcount = 0;
while(i)
{
if(i& 1)
count ++;
i = i >> 1;
}
returncount;
}
可能有讀者會問，整數右移一位在數學上是和除以2是等價的。那可不可以把上面的代碼中的右移運算符換成除以2呢？答案是最好不要換成除法。因為除法的效率比移位運算要低的多，在實際程式設計中如果可以應盡可能地用移位運算符代替乘除法。
這個思路當輸入i是正數時沒有問題，但當輸入的i是一個負數時，不但不能得到正确的1的個數，還将導緻死循環。以負數0x80000000為例，右移一位的時候，并不是簡單地把最高位的1移到第二位變成0x40000000，而是0xC0000000。這是因為移位前是個負數，仍然要保證移位後是個負數，是以移位後的最高位會設為1。如果一直做右移運算，最終這個數字就會變成0xFFFFFFFF而陷入死循環。
為了避免死循環，我們可以不右移輸入的數字i。首先i和1做與運算，判斷i的最低位是不是為1。接着把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1……這樣反複左移，每次都能判斷i的其中一位是不是1。基于此，我們得到如下代碼：
///
// Get how many 1s in an integer's binary expression
///
int NumberOf1_Solution2(inti)
{
intcount = 0;
unsignedint flag = 1;
while(flag)
{
if(i& flag)
count ++;
flag = flag << 1;
}
returncount;
}
另外一種思路是如果一個整數不為0，那麼這個整數至少有一位是1。如果我們把這個整數減去1，那麼原來處在整數最右邊的1就會變成0，原來在1後面的所有的0都會變成1。其餘的所有位将不受到影響。舉個例子：一個二進制數1100，從右邊數起的第三位是處于最右邊的一個1。減去1後，第三位變成0，它後面的兩位0變成1，而前面的1保持不變，是以得到結果是1011。
我們發現減1的結果是把從最右邊一個1開始的所有位都取反了。這個時候如果我們再把原來的整數和減去1之後的結果做與運算，從原來整數最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000。也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0。那麼一個整數的二進制有多少個1，就可以進行多少次這樣的操作。
這種思路對應的代碼如下：
///
// Get how many 1s in an integer's binary expression
///
int NumberOf1_Solution3(inti)
{
intcount = 0;
while(i)
{
++ count;
i = (i - 1) & i;
}
returncount;
}
擴充：如何用一個語句判斷一個整數是不是二的整數次幂？
(23)－跳台階問題
題目：一個台階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間複雜度。
分析：這道題最近經常出現，包括MicroStrategy等比較重視算法的公司都曾先後選用過個這道題作為面試題或者筆試題。
首先我們考慮最簡單的情況。如果隻有1級台階，那顯然隻有一種跳法。如果有2級台階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級。
現在我們再來讨論一般情況。我們把n級台階時的跳法看成是n的函數，記為f(n)。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次隻跳1級，此時跳法數目等于後面剩下的n-1級台階的跳法數目，即為f(n-1)；另外一種選擇是第一次跳2級，此時跳法數目等于後面剩下的n-2級台階的跳法數目，即為f(n-2)。是以n級台階時的不同跳法的總數f(n)=f(n-1)+(f-2)。
我們把上面的分析用一個公式總結如下：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到這裡，相信很多人都能看出這就是我們熟悉的Fibonacci序列。至于怎麼求這個序列的第n項，請參考本面試題系列第16題，這裡就不在贅述了。
(24)－棧的push、pop序列
題目：輸入兩個整數序列。其中一個序清單示棧的push順序，判斷另一個序列有沒有可能是對應的pop順序。為了簡單起見，我們假設push序列的任意兩個整數都是不相等的。
比如輸入的push序列是1、2、3、4、5，那麼4、5、3、2、1就有可能是一個pop系列。因為可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
分析：這到題除了考查對棧這一基本資料結構的了解，還能考查我們的分析能力。
這道題的一個很直覺的想法就是建立一個輔助棧，每次push的時候就把一個整數push進入這個輔助棧，同樣需要pop的時候就把該棧的棧頂整數pop出來。
我們以前面的序列4、5、3、2、1為例。第一個希望被pop出來的數字是4，是以4需要先push到棧裡面。由于push的順序已經由push序列确定了，也就是在把4 push進棧之前，數字1，2，3都需要push到棧裡面。此時棧裡的包含4個數字，分别是1，2，3，4，其中4位于棧頂。把4 pop出棧後，剩下三個數字1，2，3。接下來希望被pop的是5，由于仍然不是棧頂數字，我們接着在push序列中4以後的數字中尋找。找到數字5後再一次push進棧，這個時候5就是位于棧頂，可以被pop出來。接下來希望被pop的三個數字是3，2，1。每次操作前都位于棧頂，直接pop即可。
再來看序列4、3、5、1、2。pop數字4的情況和前面一樣。把4 pop出來之後，3位于棧頂，直接pop。接下來希望pop的數字是5，由于5不是棧頂數字，我們到push序列中沒有被push進棧的數字中去搜尋該數字，幸運的時候能夠找到5，于是把5 push進入棧。此時pop 5之後，棧内包含兩個數字1、2，其中2位于棧頂。這個時候希望pop的數字是1，由于不是棧頂數字，我們需要到push序列中還沒有被push進棧的數字中去搜尋該數字。但此時push序列中所有數字都已被push進入棧，是以該序列不可能是一個pop序列。
也就是說，如果我們希望pop的數字正好是棧頂數字，直接pop出棧即可；如果希望pop的數字目前不在棧頂，我們就到push序列中還沒有被push到棧裡的數字中去搜尋這個數字，并把在它之前的所有數字都push進棧。如果所有的數字都被push進棧仍然沒有找到這個數字，表明該序列不可能是一個pop序列。
基于前面的分析，我們可以寫出如下的參考代碼：
#include <stack>
/
// Given a push order of a stack, determine whether an array is possible to
// be its corresponding pop order
// Input: pPush - an array of integers,the push order
// pPop - an array of integers, the pop order
// nLength - the length of pPushand pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
// Otherwise return false
/
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
boolbPossible = false;
if(pPush&& pPop && nLength > 0)
{
constint *pNextPush = pPush;
constint *pNextPop = pPop;
//ancillary stack
std::stack<int>stackData;
// checkevery integers in pPop
while(pNextPop- pPop < nLength)
{
//while the top of the ancillary stack is not the integer
//to be poped, try to push some integers into the stack
while(stackData.empty()|| stackData.top() != *pNextPop)
{
//pNextPush == NULL means all integers have been
// pushed into the stack, can't push any longer
if(!pNextPush)
break;
stackData.push(*pNextPush);
//if there are integers left in pPush, move
// pNextPush forward, otherwise set it to be NULL
if(pNextPush - pPush <nLength - 1)
pNextPush ++;
else
pNextPush = NULL;
}
//After pushing, the top of stack is still not same as
//pPextPop, pPextPop is not in a pop sequence
//corresponding to pPush
if(stackData.top()!= *pNextPop)
break;
//Check the next integer in pPop
stackData.pop();
pNextPop ++;
}
// if allintegers in pPop have been check successfully,
//pPop is a pop sequence corresponding to pPush
if(stackData.empty()&& pNextPop - pPop == nLength)
bPossible = true;
}
returnbPossible;
}
(25)-在從1到n的正數中1出現的次數
題目：輸入一個整數n，求從1到n這n個整數的十進制表示中1出現的次數。
例如輸入12，從1到12這些整數中包含1 的數字有1，10，11和12，1一共出現了5次。
分析：這是一道廣為流傳的google面試題。用最直覺的方法求解并不是很難，但遺憾的是效率不是很高；而要得出一個效率較高的算法，需要比較強的分析能力，并不是件很容易的事情。當然，google的面試題中簡單的也沒有幾道。
首先我們來看最直覺的方法，分别求得1到n中每個整數中1出現的次數。而求一個整數的十進制表示中1出現的次數，就和本面試題系列的第22題很相像了。我們每次判斷整數的個位數字是不是1。如果這個數字大于10，除以10之後再判斷個位數字是不是1。基于這個思路，不難寫出如下的代碼：
int NumberOf1(unsignedint n);
/
// Find the number of 1 in the integers between 1 and n
// Input: n - an integer
// Output: the number of 1 in the integers between 1 and n
/
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
intnumber = 0;
// Find thenumber of 1 in each integer between 1 and n
for(unsigned int i = 1; i<= n; ++ i)
number += NumberOf1(i);
returnnumber;
}
/
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/
int NumberOf1(unsignedint n)
{
intnumber = 0;
while(n)
{
if(n% 10 == 1)
number ++;
n = n / 10;
}
returnnumber;
}
這個思路有一個非常明顯的缺點就是每個數字都要計算1在該數字中出現的次數，是以時間複雜度是O(n)。當輸入的n非常大的時候，需要大量的計算，運算效率很低。我們試着找出一些規律，來避免不必要的計算。
我們用一個稍微大一點的數字21345作為例子來分析。我們把從1到21345的所有數字分成兩段，即1-1235和1346-21345。
先來看1346-21345中1出現的次數。1的出現分為兩種情況：一種情況是1出現在最高位（萬位）。從1到21345的數字中，1出現在10000-19999這10000個數字的萬位中，一共出現了10000（104）次；另外一種情況是1出現在除了最高位之外的其他位中。例子中1346-21345，這20000個數字中後面四位中1出現的次數是2000次（2*103，其中2的第一位的數值，103是因為數字的後四位數字其中一位為1，其餘的三位數字可以在0到9這10個數字任意選擇，由排列組合可以得出總次數是2*103）。
至于從1到1345的所有數字中1出現的次數，我們就可以用遞歸地求得了。這也是我們為什麼要把1-21345分為1-1235和1346-21345兩段的原因。因為把21345的最高位去掉就得到1345，便于我們采用遞歸的思路。
分析到這裡還有一種特殊情況需要注意：前面我們舉例子是最高位是一個比1大的數字，此時最高位1出現的次數104（對五位數而言）。但如果最高位是1呢？比如輸入12345，從10000到12345這些數字中，1在萬位出現的次數就不是104次，而是2346次了，也就是除去最高位數字之後剩下的數字再加上1。
基于前面的分析，我們可以寫出以下的代碼。在參考代碼中，為了程式設計友善，我把數字轉換成字元串了。
#include "string.h"
#include "stdlib.h"
int NumberOf1(constchar* strN);
int PowerBase10(unsignedint n);
/
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/
intNumberOf1BeforeBetween1AndN_Solution2(int n)
{
if(n<= 0)
return0;
// convertthe integer into a string
charstrN[50];
sprintf(strN, "%d",n);
returnNumberOf1(strN);
}
/
// Find the number of 1 in an integer with radix 10
// Input: strN - a string, which represents an integer
// Output: the number of 1 in n with radix
/
int NumberOf1(const char* strN)
{
if(!strN|| *strN < '0' || *strN > '9' || *strN == '\0')
return0;
intfirstDigit = *strN - '0';
unsignedint length = static_cast<unsigned int>(strlen(strN));
// theinteger contains only one digit
if(length== 1 && firstDigit == 0)
return0;
if(length== 1 && firstDigit > 0)
return1;
// supposethe integer is 21345
//numFirstDigit is the number of 1 of 10000-19999 due to the first digit
intnumFirstDigit = 0;
//numOtherDigits is the number of 1 01346-21345 due to all digits
//except the first one
intnumOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
//numRecursive is the number of 1 of integer 1345
intnumRecursive = NumberOf1(strN + 1);
// if thefirst digit is greater than 1, suppose in integer 21345
//number of 1 due to the first digit is 10^4. It's 10000-19999
if(firstDigit> 1)
numFirstDigit = PowerBase10(length- 1);
// if thefirst digit equals to 1, suppose in integer 12345
//number of 1 due to the first digit is 2346. It's 10000-12345
elseif(firstDigit == 1)
numFirstDigit = atoi(strN + 1) + 1;
returnnumFirstDigit + numOtherDigits + numRecursive;
}
/
// Calculate 10^n
/
int PowerBase10(unsignedint n)
{
intresult = 1;
for(unsigned int i = 0; i< n; ++ i)
result *= 10;
returnresult;
}
(26)-和為n連續正數序列
題目：輸入一個正數n，輸出所有和為n連續正數序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，是以輸出3個連續序列1-5、4-6和7-8。
分析：這是網易的一道面試題。
這道題和本面試題系列的第10題有些類似。我們用兩個數small和big分别表示序列的最小值和最大值。首先把small初始化為1，big初始化為2。如果從small到big的序列的和大于n的話，我們向右移動small，相當于從序列中去掉較小的數字。如果從small到big的序列的和小于n的話，我們向右移動big，相當于向序列中添加big的下一個數字。一直到small等于(1+n)/2，因為序列至少要有兩個數字。
基于這個思路，我們可以寫出如下代碼：
void PrintContinuousSequence(intsmall, int big);
/
// Find continuous sequence, whose sum is n
/
void FindContinuousSequence(int n)
{
if(n< 3)
return;
intsmall = 1;
intbig = 2;
intmiddle = (1 + n) / 2;
intsum = small + big;
while(small< middle)
{
// we arelucky and find the sequence
if(sum== n)
PrintContinuousSequence(small,big);
// if thecurrent sum is greater than n,
//move small forward
while(sum> n)
{
sum -= small;
small ++;
// weare lucky and find the sequence
if(sum== n)
PrintContinuousSequence(small,big);
}
// movebig forward
big ++;
sum += big;
}
}
/
// Print continuous sequence between small and big
/
void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d", i);
printf("\n");
}
(27)-二進制樹的深度
題目：輸入一棵二進制樹的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
例如：輸入二進制樹：
10
/ \
6 14
/ / \
4 12 16
輸出該樹的深度3。
二進制樹的結點定義如下：
struct SBinaryTreeNode // anode of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // rightchild of node
};
分析：這道題本質上還是考查二進制樹的周遊。
題目給出了一種樹的深度的定義。當然，我們可以按照這種定義去得到樹的所有路徑，也就能得到最長路徑以及它的長度。隻是這種思路用來寫程式有點麻煩。
我們還可以從另外一個角度來了解樹的深度。如果一棵樹隻有一個結點，它的深度為1。如果根結點隻有左子樹而沒有右子樹，那麼樹的深度應該是其左子樹的深度加1；同樣如果根結點隻有右子樹而沒有左子樹，那麼樹的深度應該是其右子樹的深度加1。如果既有右子樹又有左子樹呢？那該樹的深度就是其左、右子樹深度的較大值再加1。
上面的這個思路用遞歸的方法很容易實作，隻需要對周遊的代碼稍作修改即可。參考代碼如下：
///
// Get depth of a binary tree
// Input: pTreeNode - the head of a binary tree
// Output: the depth of a binary tree
///
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
// the depthof a empty tree is 0
if(!pTreeNode)
return0;
// the depthof left sub-tree
intnLeft = TreeDepth(pTreeNode->m_pLeft);
// the depthof right sub-tree
intnRight = TreeDepth(pTreeNode->m_pRight);
// depth isthe binary tree
return(nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
(28)-字元串的排列
題目：輸入一個字元串，列印出該字元串中字元的所有排列。例如輸入字元串abc，則輸出由字元a、b、c所能排列出來的所有字元串abc、acb、bac、bca、cab和cba。
分析：這是一道很好的考查對遞歸了解的程式設計題，是以在過去一年中頻繁出現在各大公司的面試、筆試題中。
我們以三個字元abc為例來分析一下求字元串排列的過程。首先我們固定第一個字元a，求後面兩個字元bc的排列。當兩個字元bc的排列求好之後，我們把第一個字元a和後面的b交換，得到bac，接着我們固定第一個字元b，求後面兩個字元ac的排列。現在是把c放到第一位置的時候了。記住前面我們已經把原先的第一個字元a和後面的b做了交換，為了保證這次c仍然是和原先處在第一位置的a交換，我們在拿c和第一個字元交換之前，先要把b和a交換回來。在交換b和a之後，再拿c和處在第一位置的a進行交換，得到cba。我們再次固定第一個字元c，求後面兩個字元b、a的排列。
既然我們已經知道怎麼求三個字元的排列，那麼固定第一個字元之後求後面兩個字元的排列，就是典型的遞歸思路了。
基于前面的分析，我們可以得到如下的參考代碼：
void Permutation(char*pStr, char* pBegin);
/
// Get the permutation of a string,
// for example, input string abc, its permutation is
// abc acb bac bca cba cab
/
void Permutation(char* pStr)
{
Permutation(pStr, pStr);
}
/
// Print the permutation of a string,
// Input: pStr - input string
// pBegin - points to the beginchar of string
// which we want topermutate in this recursion
/
void Permutation(char* pStr, char* pBegin)
{
if(!pStr|| !pBegin)
return;
// if pBeginpoints to the end of string,
//this round of permutation is finished,
//print the permuted string
if(*pBegin== '\0')
{
printf("%s\n",pStr);
}
//otherwise, permute string
else
{
for(char* pCh = pBegin; *pCh != '\0';++ pCh)
{
//swap pCh and pBegin
chartemp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
//restore pCh and pBegin
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
擴充1：如果不是求字元的所有排列，而是求字元的所有組合，應該怎麼辦呢？當輸入的字元串中含有相同的字元串時，相同的字元交換位置是不同的排列，但是同一個組合。舉個例子，如果輸入aaa，那麼它的排列是6個aaa，但對應的組合隻有一個。
擴充2：輸入一個含有8個數字的數組，判斷有沒有可能把這8個數字分别放到正方體的8個頂點上，使得正方體上三組相對的面上的4個頂點的和相等。
(29)-調整數組順序使奇數位于偶數前面
題目：輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分，所有偶數位于數組的後半部分。要求時間複雜度為O(n)。
分析：如果不考慮時間複雜度，最簡單的思路應該是從頭掃描這個數組，每碰到一個偶數時，拿出這個數字，并把位于這個數字後面的所有數字往前挪動一位。挪完之後在數組的末尾有一個空位，這時把該偶數放入這個空位。由于碰到一個偶數，需要移動O(n)個數字，是以總的時間複雜度是O(n２)。
要求的是把奇數放在數組的前半部分，偶數放在數組的後半部分，是以所有的奇數應該位于偶數的前面。也就是說我們在掃描這個數組的時候，如果發現有偶數出現在奇數的前面，我們可以交換他們的順序，交換之後就符合要求了。
是以我們可以維護兩個指針，第一個指針初始化為數組的第一個數字，它隻向後移動；第二個指針初始化為數組的最後一個數字，它隻向前移動。在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數，我們就交換這兩個數字。
基于這個思路，我們可以寫出如下的代碼：
voidReorder(int*pData,unsignedintlength,bool(*func)(int));
boolisEven(intn);
/
// Devide an array of integers into two parts, odd in the first part,
// and even in the second part
// Input: pData - an array of integers
// length - the length of array
/
void ReorderOddEven(int*pData, unsigned intlength)
{
if(pData== NULL || length == 0)
return;
Reorder(pData, length, isEven);
}
/
// Devide an array of integers into two parts, the intergers which
// satisfy func in the first part, otherwise in the second part
// Input: pData - an array of integers
// length - the length of array
// func - a function
/
void Reorder(int*pData, unsigned intlength, bool (*func)(int))
{
if(pData== NULL || length == 0)
return;
int*pBegin = pData;
int*pEnd = pData + length - 1;
while(pBegin< pEnd)
{
// if*pBegin does not satisfy func, move forward
if(!func(*pBegin))
{
pBegin ++;
continue;
}
// if*pEnd does not satisfy func, move backward
if(func(*pEnd))
{
pEnd --;
continue;
}
// if*pBegin satisfy func while *pEnd does not,
//swap these integers
inttemp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
/
// Determine whether an integer is even or not
// Input: an integer
// otherwise return false
/
bool isEven(intn)
{
return(n & 1) == 0;
}
讨論：
上面的代碼有三點值得提出來和大家讨論：
１．函數isEven判斷一個數字是不是偶數并沒有用%運算符而是用&。理由是通常情況下位運算符比%要快一些；
２．這道題有很多變種。這裡要求是把奇數放在偶數的前面，如果把要求改成：把負數放在非負數的前面等，思路都是都一樣的。
３．在函數Reorder中，用函數指針func指向的函數來判斷一個數字是不是符合給定的條件，而不是用在代碼直接判斷（hard code）。這樣的好處是把調整順序的算法和調整的标準分開了（即解耦，decouple）。當調整的标準改變時，Reorder的代碼不需要修改，隻需要提供一個新的确定調整标準的函數即可，提高了代碼的可維護性。例如要求把負數放在非負數的前面，我們不需要修改Reorder的代碼，隻需添加一個函數來判斷整數是不是非負數。這樣的思路在很多庫中都有廣泛的應用，比如在ＳＴＬ的很多算法函數中都有一個仿函數（functor）的參數（當然仿函數不是函數指針，但其思想是一樣的）。如果在面試中能夠想到這一層，無疑能給面試官留下很好的印象。
(30)-異常安全的指派運算符重載函數
題目：類CMyString的聲明如下：
class CMyString
{
public:
CMyString(char*pData = NULL);
CMyString(constCMyString& str);
~CMyString(void);
CMyString& operator = (const CMyString&str);
private:
char*m_pData;
};
請實作其指派運算符的重載函數，要求異常安全，即當對一個對象進行指派時發生異常，對象的狀态不能改變。
分析：首先我們來看一般C++教科書上給出的指派運算符的重載函數：
CMyString& CMyString::operator =(constCMyString &str)
{
if(this == &str)
return*this;
delete[]m_pData;
m_pData = NULL;
m_pData = newchar[strlen(str.m_pData) + 1];
strcpy(m_pData, str.m_pData);
return*this;
}
我們知道，在配置設定記憶體時有可能發生異常。當執行語句new char[strlen(str.m_pData) + 1]發生異常時，程式将從該指派運算符的重載函數退出不再執行。注意到這個時候語句delete []m_pData已經執行了。也就是說指派操作沒有完成，但原來對象的狀态已經改變。也就是說不滿足題目的異常安全的要求。
為了滿足異常安全這個要求，一個簡單的辦法是掉換new、delete的順序。先把記憶體new出來用一個臨時指針儲存起來，隻有這個語句正常執行完成之後再執行delete。這樣就能夠保證異常安全了。
下面給出的是一個更加優雅的實作方案：
CMyString& CMyString::operator =(constCMyString &str)
{
if(this != &str)
{
CMyString strTemp(str);
char*pTemp = strTemp.m_pData;
strTemp.m_pData = m_pData;
m_pData = pTemp;
}
return*this;
}
該方案通過調用構造拷貝函數建立一個臨時對象來配置設定記憶體。此時即使發生異常，對原來對象的狀态沒有影響。交換臨時對象和需要指派的對象的字元串指針之後，由于臨時對象的生命周期結束，自動調用其析構函數釋放需指派對象的原來的字元串空間。整個函數不需要顯式用到new、delete，記憶體的配置設定和釋放都自動完成，是以代碼顯得比較優雅。
(31)-從尾到頭輸對外連結表
題目：輸入一個連結清單的頭結點，從尾到頭反過來輸出每個結點的值。連結清單結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。該題以及它的變體經常出現在各大公司的面試、筆試題中。
看到這道題後，第一反應是從頭到尾輸出比較簡單。于是很自然地想到把連結清單中連結結點的指針反轉過來，改變連結清單的方向。然後就可以從頭到尾輸出了。反轉連結清單的算法詳見本人面試題精選系列的第19題，在此不再細述。但該方法需要額外的操作，應該還有更好的方法。
接下來的想法是從頭到尾周遊連結清單，每經過一個結點的時候，把該結點放到一個棧中。當周遊完整個連結清單後，再從棧頂開始輸出結點的值，此時輸出的結點的順序已經反轉過來了。該方法需要維護一個額外的棧，實作起來比較麻煩。
既然想到了棧來實作這個函數，而遞歸本質上就是一個棧結構。于是很自然的又想到了用遞歸來實作。要實作反過來輸對外連結表，我們每通路到一個結點的時候，先遞歸輸出它後面的結點，再輸出該結點自身，這樣連結清單的輸出結果就反過來了。
基于這樣的思路，不難寫出如下代碼：
///
//Print a list from end to beginning
//Input: pListHead - the head of list
///
void PrintListReversely(ListNode* pListHead)
{
if(pListHead != NULL)
{
// Print thenext node first
if (pListHead->m_pNext!= NULL)
{
PrintListReversely(pListHead->m_pNext);
}
// Print thisnode
printf("%d", pListHead->m_nKey);
}
}
擴充：該題還有兩個常見的變體：
1. 從尾到頭輸出一個字元串；
2. 定義一個函數求字元串的長度，要求該函數體内不能聲明任何變量。
(32)-不能被繼承的類
題目：用C++設計一個不能被繼承的類。
分析：這是Adobe公司2007年校園招聘的最新筆試題。這道題除了考察應聘者的C++基本功底外，還能考察反應能力，是一道很好的題目。
在Java中定義了關鍵字final，被final修飾的類不能被繼承。但在C++中沒有final這個關鍵字，要實作這個要求還是需要花費一些精力。
首先想到的是在C++ 中，子類的構造函數會自動調用父類的構造函數。同樣，子類的析構函數也會自動調用父類的析構函數。要想一個類不能被繼承，我們隻要把它的構造函數和析構函數都定義為私有函數。那麼當一個類試圖從它那繼承的時候，必然會由于試圖調用構造函數、析構函數而導緻編譯錯誤。
可是這個類的構造函數和析構函數都是私有函數了，我們怎樣才能得到該類的執行個體呢？這難不倒我們，我們可以通過定義靜态來建立和釋放類的執行個體。基于這個思路，我們可以寫出如下的代碼：
///
//Define a class which can't be derived from
///
class FinalClass1
{
public:
static FinalClass1* GetInstance()
{
return new FinalClass1;
}
static void DeleteInstance(FinalClass1* pInstance)
{
delete pInstance;
pInstance= 0;
}
private:
FinalClass1(){}
~FinalClass1(){}
};
這個類是不能被繼承，但在總覺得它和一般的類有些不一樣，使用起來也有點不友善。比如，我們隻能得到位于堆上的執行個體，而得不到位于棧上執行個體。
能不能實作一個和一般類除了不能被繼承之外其他用法都一樣的類呢？辦法總是有的，不過需要一些技巧。請看如下代碼：
///
//Define a class which can't be derived from
///
template <typenameT> class MakeFinal
{
friend T;
private:
MakeFinal(){}
~MakeFinal(){}
};
class FinalClass2: virtual publicMakeFinal<FinalClass2>
{
public:
FinalClass2(){}
~FinalClass2(){}
};
這個類使用起來和一般的類沒有差別，可以在棧上、也可以在堆上建立執行個體。盡管類MakeFinal<FinalClass2>的構造函數和析構函數都是私有的，但由于類FinalClass2是它的友元函數，是以在FinalClass2中調用MakeFinal<FinalClass2>的構造函數和析構函數都不會造成編譯錯誤。
但當我們試圖從FinalClass2繼承一個類并建立它的執行個體時，卻不同通過編譯。
class Try: public FinalClass2
{
public:
Try() {}
~Try() {}
};
Try temp;
由于類FinalClass2是從類MakeFinal<FinalClass2>虛繼承過來的，在調用Try的構造函數的時候，會直接跳過FinalClass2而直接調用MakeFinal<FinalClass2>的構造函數。非常遺憾的是，Try不是MakeFinal<FinalClass2>的友元，是以不能調用其私有的構造函數。
基于上面的分析，試圖從FinalClass2繼承的類，一旦執行個體化，都會導緻編譯錯誤，是以是FinalClass2不能被繼承。這就滿足了我們設計要求。
(33)-在O(1)時間删除連結清單結點
題目：給定連結清單的頭指針和一個結點指針，在O(1)時間删除該結點。連結清單結點的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數的聲明如下：
void DeleteNode(ListNode* pListHead,ListNode* pToBeDeleted);
分析：這是一道廣為流傳的Google面試題，能有效考察我們的程式設計基本功，還能考察我們的反應速度，更重要的是，還能考察我們對時間複雜度的了解。
在連結清單中删除一個結點，最正常的做法是從連結清單的頭結點開始，順序查找要删除的結點，找到之後再删除。由于需要順序查找，時間複雜度自然就是O(n) 了。
我們之是以需要從頭結點開始查找要删除的結點，是因為我們需要得到要删除的結點的前面一個結點。我們試着換一種思路。我們可以從給定的結點得到它的下一個結點。這個時候我們實際删除的是它的下一個結點，由于我們已經得到實際删除的結點的前面一個結點，是以完全是可以實作的。當然，在删除之前，我們需要需要把給定的結點的下一個結點的資料拷貝到給定的結點中。此時，時間複雜度為O(1)。
上面的思路還有一個問題：如果删除的結點位于連結清單的尾部，沒有下一個結點，怎麼辦？我們仍然從連結清單的頭結點開始，順便周遊得到給定結點的前序結點，并完成删除操作。這個時候時間複雜度是O(n)。
那題目要求我們需要在O(1)時間完成删除操作，我們的算法是不是不符合要求？實際上，假設連結清單總共有n個結點，我們的算法在n-1總情況下時間複雜度是O(1)，隻有當給定的結點處于連結清單末尾的時候，時間複雜度為O(n)。那麼平均時間複雜度[(n-1)*O(1)+O(n)]/n，仍然為O(1)。
基于前面的分析，我們不難寫出下面的代碼。
參考代碼：
///
//Delete a node in a list
//Input: pListHead - the head of list
// pToBeDeleted - the node to be deleted
///
void DeleteNode(ListNode* pListHead,ListNode* pToBeDeleted)
{
if(!pListHead || !pToBeDeleted)
return;
// if pToBeDeletedis not the last node in the list
if(pToBeDeleted->m_pNext!= NULL)
{
// copy datafrom the node next to pToBeDeleted
ListNode*pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nKey = pNext->m_nKey;
pToBeDeleted->m_pNext = pNext->m_pNext;
// delete thenode next to the pToBeDeleted
delete pNext;
pNext= NULL;
}
// if pToBeDeletedis the last node in the list
else
{
// get the nodeprior to pToBeDeleted
ListNode*pNode = pListHead;
while(pNode->m_pNext!= pToBeDeleted)
{
pNode= pNode->m_pNext;
}
// deletedpToBeDeleted
pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted= NULL;
}
}
值得注意的是，為了讓代碼看起來簡潔一些，上面的代碼基于兩個假設：（1）給定的結點的确在連結清單中；（2）給定的要删除的結點不是連結清單的頭結點。不考慮第一個假設對代碼的魯棒性是有影響的。至于第二個假設，當整個清單隻有一個結點時，代碼會有問題。但這個假設不算很過分，因為在有些連結清單的實作中，會建立一個虛拟的連結清單頭，并不是一個實際的連結清單結點。這樣要删除的結點就不可能是連結清單的頭結點了。當然，在面試中，我們可以把這些假設和面試官交流。這樣，面試官還是會覺得我們考慮問題很周到的。
(34)-找出數組中兩個隻出現一次的數字
題目：一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程式找出這兩個隻出現一次的數字。要求時間複雜度是O(n)，空間複雜度是O(1)。
分析：這是一道很新穎的關于位運算的面試題。
首先我們考慮這個問題的一個簡單版本：一個數組裡除了一個數字之外，其他的數字都出現了兩次。請寫程式找出這個隻出現一次的數字。
這個題目的突破口在哪裡？題目為什麼要強調有一個數字出現一次，其他的出現兩次？我們想到了異或運算的性質：任何一個數字異或它自己都等于0。也就是說，如果我們從頭到尾依次異或數組中的每一個數字，那麼最終的結果剛好是那個隻出現依次的數字，因為那些出現兩次的數字全部在異或中抵消掉了。
有了上面簡單問題的解決方案之後，我們回到原始的問題。如果能夠把原數組分為兩個子數組。在每個子數組中，包含一個隻出現一次的數字，而其他數字都出現兩次。如果能夠這樣拆分原數組，按照前面的辦法就是分别求出這兩個隻出現一次的數字了。
我們還是從頭到尾依次異或數組中的每一個數字，那麼最終得到的結果就是兩個隻出現一次的數字的異或結果。因為其他數字都出現了兩次，在異或中全部抵消掉了。由于這兩個數字肯定不一樣，那麼這個異或結果肯定不為0，也就是說在這個結果數字的二進制表示中至少就有一位為1。我們在結果數字中找到第一個為1的位的位置，記為第N位。現在我們以第N位是不是1為标準把原數組中的數字分成兩個子數組，第一個子數組中每個數字的第N位都為1，而第二個子數組的每個數字的第N位都為0。
現在我們已經把原數組分成了兩個子數組，每個子數組都包含一個隻出現一次的數字，而其他數字都出現了兩次。是以到此為止，所有的問題我們都已經解決。
基于上述思路，我們不難寫出如下代碼：
///
//Find two numbers which only appear once in an array
//Input: data - an array contains two number appearing exactly once,
// while others appearing exactlytwice
// length - the length of data
//Output: num1 - the first number appearing once in data
// num2 - the second number appearing oncein data
///
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
if (length < 2)
return;
// get num1 ^ num2
int resultExclusiveOR = 0;
for (int i = 0; i < length;++ i)
resultExclusiveOR^= data[i];
// get indexof the first bit, which is 1 in resultExclusiveOR
unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
num1 = num2 = 0;
for (int j = 0; j < length;++ j)
{
// divide thenumbers in data into two groups,
// the indexOf1bit of numbers in the first group is 1,
// while in thesecond group is 0
if(IsBit1(data[j], indexOf1))
num1^= data[j];
else
num2^= data[j];
}
}
///
//Find the index of first bit which is 1 in num (assuming not 0)
///
unsigned intFindFirstBitIs1(intnum)
{
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 32))
{
num = num >> 1;
++ indexBit;
}
return indexBit;
}
///
//Is the indexBit bit of num 1?
///
bool IsBit1(int num, unsigned int indexBit)
{
num = num >> indexBit;
return (num & 1);
}
(35)-找出兩個連結清單的第一個公共結點
題目：兩個單向連結清單，找出它們的第一個公共結點。
連結清單的結點定義為：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道微軟的面試題。微軟非常喜歡與連結清單相關的題目，是以在微軟的面試題中，連結清單出現的機率相當高。
如果兩個單向連結清單有公共的結點，也就是說兩個連結清單從某一結點開始，它們的m_pNext都指向同一個結點。但由于是單向連結清單的結點，每個結點隻有一個m_pNext，是以從第一個公共結點開始，之後它們所有結點都是重合的，不可能再出現分叉。是以，兩個有公共結點而部分重合的連結清單，拓撲形狀看起來像一個Y，而不可能像X。
看到這個題目，第一反應就是蠻力法：在第一連結清單上順序周遊每個結點。每周遊一個結點的時候，在第二個連結清單上順序周遊每個結點。如果此時兩個連結清單上的結點是一樣的，說明此時兩個連結清單重合，于是找到了它們的公共結點。如果第一個連結清單的長度為m，第二個連結清單的長度為n，顯然，該方法的時間複雜度為O(mn)。
接下來我們試着去尋找一個線性時間複雜度的算法。我們先把問題簡化：如何判斷兩個單向連結清單有沒有公共結點？前面已經提到，如果兩個連結清單有一個公共結點，那麼該公共結點之後的所有結點都是重合的。那麼，它們的最後一個結點必然是重合的。是以，我們判斷兩個連結清單是不是有重合的部分，隻要分别周遊兩個連結清單到最後一個結點。如果兩個尾結點是一樣的，說明它們用重合；否則兩個連結清單沒有公共的結點。
在上面的思路中，順序周遊兩個連結清單到尾結點的時候，我們不能保證在兩個連結清單上同時到達尾結點。這是因為兩個連結清單不一定長度一樣。但如果假設一個連結清單比另一個長l個結點，我們先在長的連結清單上周遊l個結點，之後再同步周遊，這個時候我們就能保證同時到達最後一個結點了。由于兩個連結清單從第一個公共結點考試到連結清單的尾結點，這一部分是重合的。是以，它們肯定也是同時到達第一公共結點的。于是在周遊中，第一個相同的結點就是第一個公共的結點。
在這個思路中，我們先要分别周遊兩個連結清單得到它們的長度，并求出兩個長度之差。在長的連結清單上先周遊若幹次之後，再同步周遊兩個連結清單，知道找到相同的結點，或者一直到連結清單結束。此時，如果第一個連結清單的長度為m，第二個連結清單的長度為n，該方法的時間複雜度為O(m+n)。
基于這個思路，我們不難寫出如下的代碼：
///
//Find the first common node in the list with head pHead1 and
//the list with head pHead2
//Input: pHead1 - the head of the first list
// pHead2 - the head of the second list
//Return: the first common node in two list. If there is no common
// nodes, return NULL
///
ListNode* FindFirstCommonNode(ListNode *pHead1,ListNode *pHead2)
{
// Get the lengthof two lists
unsigned int nLength1 = ListLength(pHead1);
unsigned int nLength2 = ListLength(pHead2);
int nLengthDif = nLength1- nLength2;
// Get the longerlist
ListNode*pListHeadLong = pHead1;
ListNode*pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong= pHead2;
pListHeadShort= pHead1;
nLengthDif= nLength2 - nLength1;
}
// Move on thelonger list
for(int i = 0; i < nLengthDif;++ i)
pListHeadLong= pListHeadLong->m_pNext;
// Move on bothlists
while((pListHeadLong != NULL)&&
(pListHeadShort!= NULL) &&
(pListHeadLong!= pListHeadShort))
{
pListHeadLong= pListHeadLong->m_pNext;
pListHeadShort= pListHeadShort->m_pNext;
}
// Get the firstcommon node in two lists
ListNode*pFisrtCommonNode = NULL;
if(pListHeadLong == pListHeadShort)
pFisrtCommonNode= pListHeadLong;
return pFisrtCommonNode;
}
///
//Get the length of list with head pHead
//Input: pHead - the head of list
//Return: the length of list
///
unsigned intListLength(ListNode*pHead)
{
unsigned int nLength = 0;
ListNode*pNode = pHead;
while(pNode != NULL)
{
++ nLength;
pNode= pNode->m_pNext;
}
return nLength;
}
(36)-在字元串中删除特定的字元
題目：輸入兩個字元串，從第一字元串中删除第二個字元串中所有的字元。例如，輸入”They are students.” 和”aeiou” ，則删除之後的第一個字元串變成”Thy r stdnts.” 。
分析：這是一道微軟面試題。在微軟的常見面試題中，與字元串相關的題目占了很大的一部分，因為寫程式操作字元串能很好的反映我們的程式設計基本功。
要程式設計完成這道題要求的功能可能并不難。畢竟，這道題的基本思路就是在第一個字元串中拿到一個字元，在第二個字元串中查找一下，看它是不是在第二個字元串中。如果在的話，就從第一個字元串中删除。但如何能夠把效率優化到讓人滿意的程度，卻也不是一件容易的事情。也就是說，如何在第一個字元串中删除一個字元，以及如何在第二字元串中查找一個字元，都是需要一些小技巧的。
首先我們考慮如何在字元串中删除一個字元。由于字元串的記憶體配置設定方式是連續配置設定的。我們從字元串當中删除一個字元，需要把後面所有的字元往前移動一個位元組的位置。但如果每次删除都需要移動字元串後面的字元的話，對于一個長度為n 的字元串而言，删除一個字元的時間複雜度為O(n) 。而對于本題而言，有可能要删除的字元的個數是n ，是以該方法就删除而言的時間複雜度為O(n2)。
事實上，我們并不需要在每次删除一個字元的時候都去移動後面所有的字元。我們可以設想，當一個字元需要被删除的時候，我們把它所占的位置讓它後面的字元來填補，也就相當于這個字元被删除了。在具體實作中，我們可以定義兩個指針(pFast 和pSlow)，初始的時候都指向第一字元的起始位置。當pFast 指向的字元是需要删除的字元，則pFast 直接跳過，指向下一個字元。如果pFast 指向的字元是不需要删除的字元，那麼把pFast 指向的字元指派給pSlow 指向的字元，并且pFast 和pStart同時向後移動指向下一個字元。這樣，前面被pFast 跳過的字元相當于被删除了。用這種方法，整個删除在O(n) 時間内就可以完成。
接下來我們考慮如何在一個字元串中查找一個字元。當然，最簡單的辦法就是從頭到尾掃描整個字元串。顯然，這種方法需要一個循環，對于一個長度為n 的字元串，時間複雜度是O(n) 。
由于字元的總數是有限的。對于八位的char 型字元而言，總共隻有28=256 個字元。我們可以建立一個大小為256 的數組，把所有元素都初始化為0 。然後對于字元串中每一個字元，把它的ASCII 碼映射成索引，把數組中該索引對應的元素設為１。這個時候，要查找一個字元就變得很快了：根據這個字元的ASCII 碼，在數組中對應的下标找到該元素，如果為0 ，表示字元串中沒有該字元，否則字元串中包含該字元。此時，查找一個字元的時間複雜度是O(1) 。其實，這個數組就是一個hash 表。這種思路的詳細說明，詳見本面試題系列的第13 題。
基于上述分析，我們可以寫出如下代碼：
///
// Delete all characters in pStrDelete frompStrSource
///
voidDeleteChars(char* pStrSource, constchar* pStrDelete)
{
if(NULL == pStrSource || NULL == pStrDelete)
return;
// Initialize an array,the index in this array is ASCII value.
// All entries in thearray, whose index is ASCII value of a
// character in thepStrDelete, will be set as 1.
// Otherwise, they willbe set as 0.
constunsignedintnTableSize = 256;
inthashTable[nTableSize];
memset(hashTable, 0, sizeof(hashTable));
constchar* pTemp = pStrDelete;
while ('\0' != *pTemp)
{
hashTable[*pTemp] = 1;
++ pTemp;
}
char* pSlow = pStrSource;
char* pFast = pStrSource;
while ('\0' != *pFast)
{
// if the character isin pStrDelete, move both pStart and
// pEnd forward, andcopy pEnd to pStart.
// Otherwise, move onlypEnd forward, and the character
// pointed by pEnd isdeleted
if(1 != hashTable[*pFast])
{
*pSlow = *pFast;
++ pSlow;
}
++pFast;
}
*pSlow = '\0';
}
IT公司筆試題算法部分
1、将一整數逆序後放入一數組中（要求遞歸實作）
void convert(int *result, int n)
{
if(n>=10)
convert(result+1,n/10);
*result= n%10;
}
int main(int argc, char*argv[])
{
int n = 123456789, result[20]={};
convert(result,n);
printf("%d:",n);
for(int i=0; i<9;i++)
printf("%d",result[i]);
return getchar();
}
2、求高于平均分的學生學号及成績（學号和成績人工輸入）
double find(int total, int n)
{
int number, score, average;
scanf("%d",&number);
if(number != 0){
scanf("%d",&score);
average= find(total+score, n+1);
if(score >= average)
printf("%d:%d\n",number, score);
return average;
}else{
printf("Average=%d\n",total/n);
return total/n;
}
}
int main(int argc, char*argv[])
{
find(0,0);
return getchar();
}
3、遞歸實作回文判斷（如：abcdedbca就是回文）
int find(char *str, intn)
{
if(n<=1) return 1;
else if(str[0]==str[n-1]) returnfind(str+1, n-2);
else return 0;
}
int main(int argc, char*argv[])
{
char *str = "abcdedcba";
printf("%s:%s\n", str, find(str,
strlen(str)) ? "Yes" :"No");
return getchar();
}
4、組合問題（從M個不同字元中任取N個字元的所有組合）
void find(char*source, char *result, int n)
{
if(n==1){
while(*source)
printf("%s%c\n", result,*source++);
}else{
int i, j;
for(i=0; source[i] != 0; i++);
for(j=0; result[j] != 0; j++);
for(; i>=n; i--)
{
result[j]= *source++;
result[j+1]= '\0';
find(source,result, n-1);
}
}
}
int main(int argc, char*argv[])
{
int const n = 3;
char *source = "ABCDE", result[n+1] = {0};
if(n>0 && strlen(source)>0 &&n<=strlen(source))
find(source,result, 3);
return getchar();
}
5、分解成質因數(如435234=251*17*17*3*2)
void prim(int m, intn)
{
if(m>n){
while(m%n != 0) n++;
m/= n;
prim(m,n);
printf("%d*",n);
}
}
int main(int argc, char*argv[])
{
int n = 435234;
printf("%d=",n);
prim(n,2);
return getchar();
}
6、尋找迷宮的一條出路（o：通路； X障礙）
#define MAX_SIZE 8
int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};
char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},
{'o','o','o','o','o','X','X','X'},
{'X','o','X','X','o','o','o','X'},
{'X','o','X','X','o','X','X','o'},
{'X','o','X','X','X','X','X','X'},
{'X','o','X','X','o','o','o','X'},
{'X','o','o','o','o','X','o','o'},
{'X','X','X','X','X','X','X','X'}};
void FindPath(int X, intY)
{
if(X == MAX_SIZE || Y == MAX_SIZE){
for(int i = 0; i < MAX_SIZE; i++)
for(int j = 0; j < MAX_SIZE; j++)
printf("%c%c",Maze[i][j], j < MAX_SIZE-1 ? ' ' : '\n');
}else for(int k = 0; k <4; k++)
if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X< MAX_SIZE && 'o' == Maze[X][Y]){
Maze[X][Y] = ' ';
FindPath(X+V[k],Y+H[k]);
Maze[X][Y] ='o';
}
}
int main(int argc, char*argv[])
{
FindPath(1,0);
return getchar();
}
7、随機配置設定座位，共50個學生，使學号相鄰的同學座位不能相鄰(早些時候用C#寫的，沒有用C改寫）。
static void Main(string[] args)
{
int Tmp = 0, Count = 50;
int[] Seats = new int[Count];
bool[] Students = newbool[Count];
System.RandomRandStudent=new System.Random();
Students[Seats[0]=RandStudent.Next(0,Count)]=true;
for(int i = 1; i <Count; )
{
Tmp=(int)RandStudent.Next(0,Count);
if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1)&& (Seats[i-1] - Tmp) != -1){
Seats[i++]= Tmp;
Students[Tmp] = true;
}
}
foreach(int Student in Seats)
System.Console.Write(Student + "");
System.Console.Read();
}
8、求網格中的黑點分布（有6*7的網格，在某些格子中有黑點，已知各行與各列中有黑點的點數之和）
#define ROWS 6
#define COLS 7
int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0}; // 各行黑點數和的情況
int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1}; // 各列黑點數和的情況
int iCount, iFound;
int iSumR[ROWS], iSumC[COLS],Grid[ROWS][COLS];
int Set(int iRowNo)
{
if(iRowNo == ROWS){
for(intiColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo];iColNo++)
if(iColNo== COLS-1){
printf("\nNo.%d:\n",++iCount);
for(int i=0; i < ROWS; i++)
for(int j=0; j < COLS; j++)
printf("%d%c",Grid[i][j], (j+1) % COLS ? ' ' : '\n');
iFound = 1; // iFound = 1，有解
}
}else{
for(intiColNo=0; iColNo < COLS; iColNo++)
{
if(iPointsR[iRowNo]== 0){
Set(iRowNo + 1);
}else if(Grid[iRowNo][iColNo]==0){
Grid[iRowNo][iColNo] = 1;
iSumR[iRowNo]++; iSumC[iColNo]++; if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo])
Set(iRowNo);
else if(iSumR[iRowNo]==iPointsR[iRowNo]&& iRowNo < ROWS)
Set(iRowNo + 1);
Grid[iRowNo][iColNo] = 0;
iSumR[iRowNo]--;iSumC[iColNo]--;
}
}
}
return iFound; // 用于判斷是否有解
}
int main(int argc, char*argv[])
{
if(!Set(0))
printf("Failure!");
return getchar();
}
9、有4種面值（面值為1, 4, 12, 21）的郵票很多枚，從中最多任取5張進行組合，求郵票最大連續組合值
#define N 5
#define M 5
int k, Found, Flag[N];
int Stamp[M] = {0, 1, 4, 12, 21};
//在剩餘張數n中組合出面值和Value
int Combine(intn, int Value)
{
if(n>= 0 && Value == 0){
Found = 1;
intSum = 0;
for(int i=0; i<N && Flag[i] != 0; i++){
Sum += Stamp[Flag[i]];
printf("%d ",Stamp[Flag[i]]);
}
printf("\tSum=%d\n\n",Sum);
}else for(int i=1; i<M&& !Found && n>0; i++)
if(Value-Stamp[i]>= 0){
Flag[k++] = i;
Combine(n-1,Value-Stamp[i]);
Flag[--k] = 0;
}
returnFound;
}
int main(intargc, char* argv[])
{
for(int i=1; Combine(N, i); i++, Found=0);
returngetchar();
}
10、大整數數相乘的問題。
void Multiple(charA[], char B[], charC[])
{
int TMP,In=0, LenA=-1, LenB=-1;
while(A[++LenA] != '\0');
while(B[++LenB]!= '\0');
int Index,Start = LenA + LenB - 1;
for(int i=LenB-1; i>=0; i--)
{
Index = Start--;
if(B[i]!= '0'){
for(int In=0, j=LenA-1; j>=0; j--)
{
TMP = (C[Index]-'0') +(A[j]-'0') * (B[i] - '0') + In;
C[Index--] = TMP % 10 + '0';
In = TMP / 10;
}
C[Index] = In + '0';
}
}
}
int main(intargc, char* argv[])
{
char A[] ="21839244444444448880088888889";
char B[] ="38888888888899999999999999988";
char C[sizeof(A)+ sizeof(B) - 1];
for(int k=0; k<sizeof(C);k++)
C[k] = '0';
C[sizeof(C)-1]= '\0';
Multiple(A, B, C);
for(int i=0; C[i] != '\0'; i++)
printf("%c", C[i]);
returngetchar();
}
11、求最大連續遞增數字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
int GetSubString(char*strSource, char *strResult)
{
int iTmp=0,iHead=0, iMax=0;
for(int Index=0, iLen=0; strSource[Index]; Index++)
{
if(strSource[Index]>= '0' && strSource[Index] <= '9'
&&strSource[Index-1] > '0' && strSource[Index] == strSource[Index-1]+1)
{
iLen++; //連續數字的長度增1
}else{ // 出現字元或不連續數字
if(iLen> iMax)
{
iMax = iLen;
iHead = iTmp;
}
// 該字元是數字，但數字不連續
if(strSource[Index]>= '0' && strSource[Index] <= '9'){
iTmp = Index;
iLen = 1;
}
}
}
for(iTmp=0; iTmp < iMax; iTmp++) // 将原字元串中最長的連續數字串指派給結果串
strResult[iTmp] = strSource[iHead++];
strResult[iTmp]='\0';
returniMax; // 傳回連續數字的最大長度
}
int main(intargc, char* argv[])
{
charstrSource[]="ads3sl456789DF3456ld345AA", charstrResult[sizeof(strSource)];
printf("Len=%d, strResult=%s \nstrSource=%s\n", GetSubString(strSource,strResult),
strResult,strSource);
returngetchar();
}
12、四個勞工，四個任務，每個人做不同的任務需要的時間不同，求任務配置設定的最優方案。（2005年5月29日全國計算機軟體資格水準考試——軟體設計師的算法題）。
#include "stdafx.h"
#define N 4
int Cost[N][N]= { {2, 12, 5, 32}, // 行号：任務序号，列号：勞工序号
{8, 15, 7, 11}, // 每行元素值表示這個任務由不同勞工完成所需要的時間
{24, 18, 9, 6},
{21, 1, 8, 28}};
int MinCost=1000;
int Task[N], TempTask[N], Worker[N];
void Assign(intk, int cost)
{
if(k==N)
{
MinCost = cost;
for(int i=0; i<N; i++)
TempTask[i] = Task[i];
}else{
for(int i=0; i<N; i++){
if(Worker[i]==0&& cost+Cost[k][i] < MinCost)
{
Worker[i] = 1; Task[k] = i;
Assign(k+1,cost+Cost[k][i]);
Worker[i] = 0;Task[k] = 0;
}
}
}
}
int main(intargc, char* argv[])
{
Assign(0, 0);
printf("最佳方案總費用=%d\n", MinCost);
for(int i=0; i<N; i++)
printf("\t任務%d由勞工%d來做：%d\n", i, TempTask[i], Cost[i][TempTask[i]]);
returngetchar();
}
13、八皇後問題（輸出所有情況，不過有些結果隻是旋轉了90度而已）。哈哈：）回溯算法的典型例題
#define N 8
int Board[N][N];
int Valid(inti, int j) // 所下棋子有效性的嚴正
{
int k =1;
for(k=1;i>=k && j>=k;k++)
if(Board[i-k][j-k]) return 0;
for(k=1;i>=k;k++)
if(Board[i-k][j]) return0;
for(k=1;i>=k && j+k<N;k++)
if(Board[i-k][j+k]) return 0;
return 1;
}
void Trial(inti, int n)
{
if(i==n){
for(int k=0; k<n; k++){
for(int m=0; m<n; m++)
printf("%d", Board[k][m]);
printf("\n");
}
printf("\n");
}else{
for(int j=0; j<n; j++){
Board[i][j] = 1;
if(Valid(i,j))
Trial(i+1, n);
Board[i][j] = 0;
}
}
}
int main(intargc, char* argv[])
{
Trial(0, N);
returngetchar();
}
14、實作strstr功能（尋找子串在父串中首次出現的位置）
char * strstring(char*ParentString, char *SubString)
{
char*pSubString, *pPareString;
for(char *pTmp=ParentString; *pTmp; pTmp++)
{
pSubString = SubString;
pPareString = pTmp;
while(*pSubString== *pPareString && *pSubString != '\0')
{
pSubString++;
pPareString++;
}
if(*pSubString== '\0') returnpTmp;
}
returnNULL;
}
int main(intargc, char* argv[])
{
char*ParentString = "happy birthday to you!";
char*SubString = "birthday";
printf("%s",strstring(ParentString,SubString));
returngetchar();
}}
15、現在小明一家過一座橋，過橋的時候是黑夜，是以必須有燈。現在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要八秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃後30秒就會熄滅。問小明一家如何過橋？（原本是個智力題，這裡用程式來求解）
#include "stdafx.h"
#define N 5
#define SIZE 64
//将人員編号：小明-0，弟弟-1，爸爸-2，媽媽-3，爺爺-4
//每個人的目前位置：0--在橋左邊， 1--在橋右邊
int Position[N];
//過橋臨時方案的數組下标；臨時方案；最小時間方案；
int Index, TmpScheme[SIZE], Scheme[SIZE];
//最小過橋時間總和，初始值100；每個人過橋所需要的時間
int MinTime=100, Time[N]={1, 3, 6, 8,12};
//尋找最佳過橋方案。Remnant:未過橋人數; CurTime:目前已用時間;
//Direction:過橋方向,1--向右,0--向左
void Find(intRemnant, int CurTime, intDirection)
{
if(Remnant==0){ // 所有人已經過橋，更新最少時間及方案
MinTime=CurTime;
for(int i=0; i<SIZE && TmpScheme[i]>=0;i++)
{
Scheme[i]=TmpScheme[i];
}
}else if(Direction==1){ // 過橋方向向右，從橋左側選出兩人過橋
for(int i=0; i<N; i++)
{
if(Position[i]==0&& CurTime+Time[i]<MinTime){
TmpScheme[Index++] = i;
Position[i] = 1;
for(int j=0; j<N; j++)
{
intTmpMax = (Time[i]>Time[j] ? Time[i] : Time[j]);
if(Position[j]==0&& CurTime+TmpMax<MinTime)
{
TmpScheme[Index++] =j;
Position[j] = 1;
Find(Remnant-2, CurTime+TmpMax,!Direction);
Position[j] = 0;
TmpScheme[--Index] =-1;
}
}
Position[i] = 0;
TmpScheme[--Index] = -1;
}
}
}else{ // 過橋方向向左，從橋右側選出一個人回來送燈
for(int j=0; j<N; j++)
{
if(Position[j]==1&& CurTime+Time[j] < MinTime)
{
TmpScheme[Index++] = j;
Position[j] = 0;
Find(Remnant+1,CurTime+Time[j], !Direction);
Position[j] = 1;
TmpScheme[--Index] = -1;
}
}
}
}
int main(intargc, char* argv[])
{
for(int i=0; i<SIZE; i++) // 初始方案内容為負值，避免和人員标号沖突
Scheme[i] = TmpScheme[i] = -1;
Find(N, 0,1); // 查找最佳方案
printf("MinTime=%d:", MinTime); // 輸出最佳方案
for(int i=0; i<SIZE && Scheme[i]>=0; i+=3)
printf(" %d-%d %d", Scheme[i], Scheme[i+1], Scheme[i+2]);
printf("\b\b ");
returngetchar();
}
16、2005年11月金山筆試題。編碼完成下面的處理函數。函數将字元串中的字元'*'移到串的前部分，前面的非'*'字元後移，但不能改變非'*'字元的先後順序，函數傳回串中字元'*'的數量。如原始串為：ab**cd**e*12，處理後為*****abcde12，函數并傳回值為5。（要求使用盡量少的時間和輔助空間）
int change(char*str)
{
int count= 0;
for(int i=0, j=0; str[i]; i++)
{
if(str[i]=='*'){
for(j=i-1;str[j]!='*'&&j>=0; j--)
str[j+1]=str[j];
str[j+1] = '*';
count++;
}
}
returncount;
}
int main(intargc, char* argv[])
{
char str[] ="ab**cd**e*12";
printf("str1=%s\n", str);
printf("str2=%s, count=%d",str, change(str));
returngetchar();
}
//終于得到一個比較高效的算法，一個網友提供，應該和金山面試官的想法一緻。算法如下：
int change(char*str)
{
inti,j=strlen(str)-1;
for(i=j;j>=0; j--)
{
if(str[i]!='*'){
i--;
}elseif(str[j]!='*'){
str[i] = str[j];
str[j] = '*';
i--;
}
}
returni+1;
}
17、2005年11月15日華為軟體研發筆試題。實作一單連結清單的逆轉。
#include "stdafx.h"
typedef chareleType; // 定義連結清單中的資料類型
typedef structlistnode // 定義單連結清單結構
{
eleType data;
structlistnode *next;
}node;
node *create(int n) // 建立單連結清單，n為節點個數
{
node *p = (node *)malloc(sizeof(node));
node *head= p; head->data = 'A';
for(int i='B'; i<'A'+n; i++)
{
p = (p->next = (node *)malloc(sizeof(node)));
p->data = i;
p->next = NULL;
}
returnhead;
}
void print(node *head) // 按連結清單順序輸對外連結表中元素
{
for(;head; head = head->next)
printf("%c ",head->data);
printf("\n");
}
node*reverse(node *head, node *pre) // 逆轉單連結清單函數。這是筆試時需要寫的最主要函數
{
node *p=head->next;
head->next = pre;
if(p)
returnreverse(p, head);
else
returnhead;
}
int main(intargc, char* argv[])
{
node *head = create(6);
print(head);
head = reverse(head, NULL);
print(head);
returngetchar();
}
18、編碼實作字元串轉整型的函數（實作函數atoi的功能），據說是神州數位筆試題。如将字元串 ”+123”à123, ”-0123”à-123, “123CS45”à123, “123.45CS”à123, “CS123.45”à0
#include "stdafx.h"
int str2int(constchar *str) // 字元串轉整型函數
{
int i=0,sign=1, value = 0;
if(str==NULL) returnNULL; //空串直接傳回 NULL
if(str[0]=='-'|| str[0]=='+'){ // 判斷是否存在符号位
i = 1;
sign = (str[0]=='-' ? -1 : 1);
}
for(;str[i]>='0' && str[i]<='9'; i++) // 如果是數字，則繼續轉換
value = value * 10 + (str[i] -'0');
returnsign * value;
}
int main(intargc, char *argv[])
{
char *str= "-123.45CS67";
int val =str2int(str);
printf("str=%s\tval=%d\n", str,val);
returngetchar();
}
19、歌德巴赫猜想。任何一個偶數都可以分解為兩個素數之和。
#include "stdafx.h"
#include "math.h"
int main(intargc, char* argv[])
{
intEven=78, Prime1, Prime2, Tmp1, Tmp2;
for(Prime1=3;Prime1<=Even/2; Prime1+=2)
{
for(Tmp1=2,Tmp2=sqrt(float(Prime1)); Tmp1<=Tmp2 && Prime1%Tmp1!= 0; Tmp1++);
if(Tmp1<=Tmp2)continue;
Prime2 = Even-Prime1;
for(Tmp1=2,Tmp2=sqrt(float(Prime2)); Tmp1<=Tmp2 && Prime2%Tmp1!= 0; Tmp1++);
if(Tmp1<=Tmp2)continue;
printf("%d=%d+%d\n",Even, Prime1, Prime2);
}
returngetchar();
}
20、快速排序（東軟喜歡考類似的算法填空題，又如堆排序的算法等）
#include "stdafx.h"
#define N 10
int part(int list[], int low, inthigh) // 一趟排序，傳回分割點位置
{
int tmp =list[low];
while(low<high){
while(low<high&& list[high]>=tmp) --high;
list[low] = list[high];
while(low<high&& list[low]<=tmp) ++low;
list[high] = list[low];
}
list[low] = tmp;
return low;
}
void QSort(int list[], int low, int high) // 應用遞歸進行快速排序
{
if(low<high){
intmid = part(list, low, high);
QSort(list, low, mid-1);
QSort(list, mid+1, high);
}
}
void show(int list[], intn) // 輸出清單中元素
{
for(int i=0; i<n; i++)
printf("%d ",list[i]);
printf("\n");
}
int main(int argc, char* argv[])
{
int list[N] ={23, 65, 26, 1, 6, 89, 3, 12, 33, 8};
show(list,N); // 輸出排序前序列
QSort(list, 0,N-1); // 快速排序
show(list,N); // 輸出排序後序列
return getchar();
}
21、2005年11月23日慧通筆試題：寫一函數判斷某個整數是否為回文數，如12321為回文數。可以用判斷入棧和出棧是否相同來實作（略微複雜些），這裡是将整數逆序後形成另一整數，判斷兩個整數是否相等來實作的。
#include "stdafx.h"
int IsEchoNum(int num)
{
int m = 0;
for(int n = num; n; n/=10)
m = m*10 + n%10;
return m==num;
}
int main(int argc, char* argv[])
{
int num = 12321;
printf("%d %d\n", num, IsEchoNum(num));
return getchar();
}
22、删除字元串中的數字并壓縮字元串（神州數位以前筆試題），如字元串”abc123de4fg56”處理後變為”abcdefg”。注意空間和效率。（下面的算法隻需要一次周遊，不需要開辟新空間，時間複雜度為O(N)）
#include "stdafx.h"
void delNum(char *str)
{
int i, j=0;
for(i=j=0; str[i]&& (str[i]<'0' || str[i]>'9'); j=++i);//找到串中第一個數字的位子
for(; str[i];i++) // 從串中第一個數字的位置開始，逐個放入後面的非數字字元
if(str[i]<'0'|| str[i]>'9')
str[j++] = str[i];
str[j] = '\0';
}
int main(int argc, char* argv[])
{
char str[] ="abc123ef4g4h5";
printf("%s\n", str);
delNum(str);
printf("%s\n", str);
return getchar();
}
23、求兩個串中的第一個最長子串（神州數位以前試題）。如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。
#include "stdafx.h"
char *MaxSubString(char*str1, char *str2)
{
int i, j, k,index, max=0;
for(i=0; str1[i];i++)
for(j=0;str2[j]; j++)
{
for(k=0; str1[i+k]==str2[j+k] &&(str2[i+k] || str1[i+k]); k++);
if(k>max){ // 出現大于目前子串長度的子串，則替換子串位置和程度
index = j; max = k;
}
}
char *strResult =(char *)calloc(sizeof(char), max+1);
for(i=0; i<max;i++)
strResult[i] =str2[index++];
return strResult;
}
int main(int argc, char* argv[])
{
char str1[] ="abractyeyt", str2[] = "dgdsaeactyey";
char *strResult =MaxSubString(str1, str2);
printf("str1=%s\nstr2=%s\nMaxSubString=%s\n",str1, str2, strResult);
return getchar();
}
24、不開辟新空間完成字元串的逆序
#include "stdafx.h"
void change(char *str)
{
for(int i=0,j=strlen(str)-1; i<j; i++, j--)
{
str[i] ^= str[j] ^=str[i] ^= str[j];
}
}
int main(int argc, char* argv[])
{
char str[] ="abcdefg";
printf("strSource=%s\n", str);
change(str);
printf("strResult=%s\n", str);
return getchar();
}
25、删除串中指定的字元
#include"stdafx.h"
void delChar(char *str,char c)
{
int i, j=0;
for(i=0; str[i];i++)
if(str[i]!=c)str[j++]=str[i];
str[j] = '\0';
}
int main(int argc, char* argv[])
{
char str[] ="abcdefgh"; // 注意，此處不能寫成char *str ="abcdefgh";
printf("%s\n", str);
delChar(str, 'c');
printf("%s\n", str);
return getchar();
}
26、判斷單連結清單中是否存在環（網上說的筆試題）
#include "stdafx.h"
typedef chareleType; // 定義連結清單中的資料類型
typedef structlistnode // 定義單連結清單結構
{
eleType data;
struct listnode*next;
}node;
node *create(intn) // 建立單連結清單，n為節點個數
{
node *p = (node *)malloc(sizeof(node));
node *head = p; head->data = 'A';
for(int i='B'; i<'A'+n; i++)
{
p = (p->next = (node*)malloc(sizeof(node)));
p->data = i;
p->next = NULL;
}
return head;
}
void addCircle(node *head, intn) // 增加環，将鍊尾指向鍊中第n個節點
{
node *q, *p = head;
for(int i=1; p->next; i++)
{
if(i==n)q = p;
p = p->next;
}
p->next = q;
}
int isCircle(node *head) // 這是筆試時需要寫的最主要函數，其他函數可以不寫
{
node *p=head,*q=head;
while( p->next&& q->next)
{
p = p->next;
if(NULL == (q=q->next->next)) return 0;
if(p == q)
return 1;
}
return 0;
}
int main(int argc, char* argv[])
{
node *head = create(12);
addCircle(head,8); //注釋掉此行，連表就沒有環了
printf("%d\n", isCircle(head));
return getchar();
}
難題
喝酒問題
由n元組(x1,x2,……，xn)組成的一個狀态空間 E={(x1,x2,……，xn) | xi ∈Si, i=1,2,..,n}，給定關于n元組中的分量的一個限制集D，要求E中滿足D的全部限制的所有n元組。其中Si是分量xi的定義域且|Si|有限，i=1,2,...n。我們稱E中滿足D的全部限制條件的任一n元組為問題P的一個解。
對于n元組(x1,x2,……，xn)中分量的限制，一般分為兩類，一類是顯限制，它給出對于n元組中分量的顯式限制，比如當i≠j時xi≠xj；另一類是隐限制，它給出對于n元組中分量的隐式限制，比如：f(x1,x2,……，xn)≠ 0，其中f是隐函數。不過隐式顯式并不絕對，兩者可以互相轉換。
解問題P的最樸素的方法是窮舉法，即對E中的所有n元組，逐一地檢測其是否滿足D的全部限制。全部滿足，才是問題p的解;隻要有一個不滿足，就不是問題P的解。顯然，如果記m(i)=|S(i+1)|,i=0,1,...n-1，那麼，窮舉法需要對m=m(0)*m(1)*...*m(n-1)個n元組一個不漏地加以檢測。可想而知，其計算量是非常之大的。
我們發現，對于許多問題，所給定的限制集D具有完備性，即i元組(x1,x2,……，xi)滿足D中僅涉及到x1,x2,……，xi的所有限制意味着j(j<i)元組(x1,x2,……，xj)一定也滿足D中僅涉及到x1,x2,……，xj的所有限制，i=1,2,……,n。換句話說，隻要存在O≤j≤n-1，使得(x1,x2,……，xj)違反D中僅涉及到x1,x2,……，xj的限制之一，以(x1,x2,……，xj)為字首的任何n元組(x1,x2,……,xj,……,xn)一定也違反D中僅涉及到又x1,x2,……，xi的一個限制，其中n≥i≥j。
這個發現告訴我們，對于限制集D具有完備性的問題P，一旦檢測斷定某個j元組(x1,x2,……,xj)違反D中僅涉及x1,x2,……,xj的一個限制，就可以肯定，以(x1,x2,……,xj)為字首的任何n元組(x1,x2,……,xj,……,xn)都不會是問題的解，因而就不必去搜尋它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比窮舉法效率高得多的算法。
回溯法首先将問題P的n元組的狀态空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜尋問題P的所有解。樹T類似于檢索樹。它可這樣構造：設Si中的元素可排成x(i,1),x(i,2),……,x(i,m(i-1)),i=1,2,……,n。從根開始，讓T的第i層的每一個結點都有m(i)個兒子。這m(i)個兒子到它們的共同父親的邊，按從左到右的次序分别帶權x(i+1,1),x(i+1,2),……,x(i+1,m(i)),i=0,1,2,……,n-1。照這種構造方式，E中的一個n元組(x1,x2,……，xn)對應于T中的一個葉結點，T的根到這個葉結點的路上依次的n條邊分别以x1,x2,……，xn為其權，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組(x1,x2,……，xn)的一個字首i元組(x1,x2,……，xi)對應于T中的一個非葉結點，T的根到這個非葉結點的路上依次的i條邊分别以了x1,x2,……，xi為其權，反之亦然。特别，E中的任意一個n元組的空字首()，對應于T的根。
因而，在E中尋找問題P的一個解等價于在T中搜尋一個葉結點，要求從T的根到該葉結點的路上依次的n條邊相應帶的n個權x1,x2,……，xn滿足限制集D的全部限制。在T中搜尋所要求的葉結點，很自然的一種方式是從根出發逐漸深入，讓路逐漸延伸，即依次搜尋滿足約柬條件的字首1元組(xl)，字首2元組(xl,x2)，字首i元組(x1,x2,……，xi)，……，直到i=n為止。注意，在這裡，我們把(x1,x2,……，xi)應該滿足的D中僅涉及x1,x2,……，xi的所有限制當做判斷(x1,x2,……，xi)是問題p的解的必要條件，隻有當這個必要條件加上條件i=n才是充要條件。為了差別，我們稱使積累的判别條件成為充要條件的那個條件(如條件i=n)為終結條件。
在回溯法中，上面引入的樹T被稱為問題P的狀态空間樹;樹T上的任意一個結點被稱為問題p的狀态結點;樹T上的任意一個葉結點被稱為問題P的一個解狀态結點;樹T上滿足限制集D的全部約柬的任意一個葉結點被稱為問題P的一個回答狀态結點，簡稱為回答結點或回答狀态，它對應于問題P的一個解。
例如8皇後問題，就是要确定一個8元組（x1,x2,..,x8)，xi表示第i行的皇後所在的列，這樣的問題很容易應用上面的搜尋樹模型；然而，有些問題的解無法表示成一個n元組，因為事先無法确定這個n是多少，比如這個喝酒問題，問題的解就是一系列的倒酒喝酒政策，但是事先無法确定究竟需要進行多少步；還有著名的8數位問題（文曲星上的那個9x9方格中移數字的遊戲），那個問題也是預先不知道需要移動多少步才能達到目标。不過這并不影響回溯法的使用，隻要該問題有解，一定可以将解用有限的變元來表示，我們可以假設n就是問題的一個解的變元的個數，這樣就可以繼續利用上面的搜尋樹模型了。事實上，這棵搜尋樹并非預先生成的，而是在搜尋的過程中逐漸生成的，是以不知道樹的深度n并不影響在樹中搜尋葉子節點。但是有一點很重要，如果問題根本不存在有限的解，或者問題的狀态空間無窮大，那麼沿着某條道路從根出發搜尋葉節點，可能永遠無法達到葉結點，因為搜尋樹會不斷地擴充，然而葉結點也許是确實存在的，隻要換一條道路就可以找到，隻不過一開始就走錯了路，而這條錯路是永遠無法終止的。為了避免這種情況我們一般都規定狀态空間是有限的，這樣即使搜尋整個狀态空間的每個狀态也可以在有限時間内完成，否則的話回溯法很可能不适用。
搜尋樹的每一個節點表示一個狀态，節點i要生成節點j必須滿足限制集D中的限制條件，我們也可以将這個限制條件稱為“狀态轉移規則”或者“産生規則”（意指從節點i産生節點j的規則，這是從“産生式系統”理論的角度來解釋回溯法）。是以回溯法的實質是在一個狀态空間中，從起始狀态（搜尋樹的根）搜尋到一條到達目标狀态（搜尋樹的葉結點）的路徑（就和走迷宮差不多，這是從圖論的角度來解釋回溯法）。一般來說，為了防止搜尋的過程中出現回路，必須記錄已經走過的節點（狀态），在同一條路徑中不能重複走過的節點（狀态），這樣隻要狀态空間是有限的，回溯法總是可以終止的。
===========================================================================================
下面我們就根據回溯法來解決這個喝酒問題
（1）狀态的表示
一個狀态用一個7元組表示 X=（x1,x2,x3,x4,x5,x6,x7)；，其中x1~x3分别表示a,b,c三個酒瓶中的酒，x4~x7分别表示A,B,C，D四個人已經喝的酒；
（2）限制條件
1。每個人喝的酒不能超過4兩；
2。每個瓶中容納的酒不能超過該瓶的容量；
為了友善設第k個人喝的酒不超過C[k], 第i個酒瓶的容量為C， 則
C[1]=C[2]=8, C[3]=3, C[4]=C[5]=C[6]=C[7]=4;
限制條件為
0<= X <= C;
（3）狀态的轉移規則（狀态産生規則）
從某個狀态X轉移到另一個狀态Y有以下幾種情況：
1。i瓶中的酒倒入j瓶中，并将j瓶裝滿: Y = X - (C[j]-X[j]) , Y[j] = C[j], i,j∈[1,3]
2。i瓶中的酒倒入j瓶中，并将i瓶倒空: Y = 0 , Y[j] = X[j] + X , i,j∈[1,3]
3。某個人j喝光了i瓶中的酒: Y = 0; Y[j] = X[j] + X, i∈[1,3], j∈[4,7]
當然狀态Y必須滿足（2）中的限制條件；
（4）初始狀态
a,b兩個瓶中裝滿酒，c中為空： X0[1]=C[1], X0[2]=C[2], X0[3]=C[3], X0[4]=X0[5]=X0[6]=X0[7]=0；
（5）目标狀态
所有的瓶中的酒為空，每個人都喝飽了酒： Xn[1]=Xn[2]=Xn[3]=0 , Xn[4]=C[4]， Xn[5]=C[5]， Xn[6]=C[6]， Xn[7]=C[7];
下面給出一個通用的回溯法僞代碼：
void DFS_TRY( s )
{
if (狀态s是目标狀态) {
列印結果；
退出； // 如果要求輸出所有的解，這裡退出函數，如果隻要求輸出一組解，這裡退出整個程式
}
for 從狀态s根據産生規則産生的每個狀态t
if (t不在堆棧中) {
狀态t壓入堆棧；
DFS_TRY(t);
狀态t彈出堆棧；
}
}
主程式為：
初始狀态s0壓入堆棧；
DFS_TRY(s0);
然而，對于這個問題，如果單純地用上面的回溯法解決效率非常的低，幾乎無法忍受。是以要改進一下。我們注意到每個狀态是一個7元組，而且根據限制條件，所有的合法的狀态的個數是8*8*3*4*4*4*4 =49152個，完全可以将所有的狀态記錄下來，即使窮舉所有的狀态也是可以忍受的。是以在上面的DFS_TRY中，我們不是在堆棧中尋找已經搜尋過的狀态，而是在一個狀态表中找已經搜尋過的狀态，如果某個狀态在狀态表中的标志表明該狀态已經搜尋過了，就沒有必要再搜尋一遍。比如，單純的回溯法搜尋出來的搜尋樹如下所示：
a
/ \
/ \
b c
\ /
\ /
d
/ \
/ \
從a出發，搜尋 a - b - d - ... 然後回溯到a, 又搜尋到 a - c - d - ..., 因為d在搜尋的路徑上并沒有重複，是以在堆棧中是發現不了d節點被重複搜尋的，這樣就重複搜尋了d和它的子樹；如果用一個表格紀錄每個節點是否被搜尋過了，這樣搜尋 a - b - d - ...回溯到a, 又搜尋到 a - c - d ，這時候查表發現d已經搜尋過了，就可以不用再搜尋d和它的子樹了。
這種用一個表格來記錄狀态的搜尋政策叫做“備忘錄法”，是動态規劃的一種變形，關于動态規劃和備忘錄法，請參見:
http://algorithm.myrice.com/algorithm/technique/dynamic_programming/index.htm
備忘錄法的僞代碼：
bool Memoire_TRY( s )
{
if (狀态s是目标狀态) {
記錄狀态s；
return true; // 這裡假設隻要求輸出一組解
}
for 從狀态s根據産生規則産生的每個狀态t
if (狀态t沒有被搜尋過) { // 注意這裡的改變
标記狀态t被通路過；
if (DFS_TRY(t)) {
記錄狀态s；
return true;
}
}
return false;
}
主程式為：
初始化設定狀态表中的所有狀态未被通路過
初始狀态設為s0；
if (Memoire_TRY(s0))
列印記錄下來的解;
這樣就不需要自己設定堆棧了，但是需要維護一個狀态通路表。
下面是按照這種思路寫的程式，注意，求出來的不是最優解，但是很容易修改該程式求出最優解。
#include <iostream.h>
#include <string.h>
const int CUP_COUNT = 3; // 酒杯的數目
const int STATE_COUNT = 7; // 狀态變量的維數
typedef int State[STATE_COUNT]; // 記錄狀态的類型
const State CONSTR = {8, 8, 3, 4, 4, 4, 4}; // 限制條件
const State START = {8, 8, 0, 0, 0, 0, 0}; // 初始狀态
const State GOAL = {0, 0, 0, 4, 4, 4, 4}; // 目标狀态
const int MAX_STATE_COUNT = 10*10*10*10*10*10*10; //态空間的狀态數目
const MAX_STEP = 50; // 假設最多需要50步就可以找到目标
const State key = {3, 5, 3, 3, 2, 0, 0};
bool visited[MAX_STATE_COUNT]; // 用來标記通路過的狀态
State result[MAX_STEP]; // 記錄結果；
int step_count = 0; // 達到目标所用的步數
// 計算狀态s在狀态表中的位置
int pos(const State &s)
{
int p = 0;
for (int i=0; i<STATE_COUNT; i++) {
p = p*10 + s;
}
return p;
}
// 判斷狀态a,b是否相等
bool equal(const State &a, const State &b) {
for (int i=0; i<STATE_COUNT; i++)
if (a!=b) return false;
return true;
}
void printState(const State &s) {
for (int i=0; i<STATE_COUNT; i++)
cout << s << " ";
cout << endl;
}
// 備忘錄法搜尋
bool Memoire_TRY(const State &s, int step)
{
if (memcmp(s,GOAL,sizeof(s))==0) { // 如果是目标狀态
step_count = step;
memcpy(result[step-1],s, sizeof(s)); // 記錄狀态s
return true;
}
int i, j;
// 第一種規則，第i個人喝光杯子j中的酒
for (i=CUP_COUNT; i<STATE_COUNT; i++)
if (s < CONSTR) // 如果第i個人還可以喝
for (j=0; j<CUP_COUNT; j++)
if (s[j]>0 && s + s[j] <= CONSTR) { // 如果第i個人可以喝光第j杯中的酒
State t;
memcpy(t, s, sizeof(s));
t += t[j]; // 第i個人喝光第j杯的酒
t[j] = 0;
int tmp = pos(t);
if (!visited[pos(t)]) { // 如果狀态t沒有通路過
visited[pos(t)] =true; // 标記狀态t通路過了
if (Memoire_TRY(t, step+1)) { // 從狀态t出發搜尋
memcpy(result[step-1],s, sizeof(s)); // 記錄狀态s
return true;
} // end of if (Memoire_TRY(t, step+1))
} // end of if (!visited[pos(t)])
} // end of if (s + s[j] <= CONSTR)
// 第二種規則，将杯子i中的酒倒入到杯子j中去
for (i=0; i<CUP_COUNT; i++)
for (j=0; j<CUP_COUNT; j++)
if (i != j) {
int k = (CONSTR[j] - s[j] < s ? CONSTR[j] - s[j] : s ); // 計算出可以從i中倒入j中的酒的數量
if (k > 0) { // 如果可以倒
State t; // 生成新的狀态t
memcpy(t, s, sizeof(s));
t -= k;
t[j] += k;
int tmp = pos(t);
if (!visited[pos(t)]) { // 如果狀态t沒有通路過
visited[pos(t)] =true; // 标記狀态t通路過了
if (Memoire_TRY(t, step+1)) { // 從狀态t出發搜尋
memcpy(result[step-1],s, sizeof(s)); // 記錄狀态s
return true;
} // end of if (Memoire_TRY(t, step+1))
} // end of if (!visited[pos(t)])
} // end of if (k > 0)
} // end of if (i != j)
return false;
} // end of Memoire_TRY
void main()
{
memset(visited, false, sizeof(visited));
if (Memoire_TRY(START,1)) {
cout << "find a solution: " << endl;
for (int i=0; i<step_count; i++) {
for (int j=0; j<STATE_COUNT; j++)
cout << result[j] << " ";
cout << endl;
}
} else
cout << "no solution." << endl;
}
![初級銀行從業資格證有什麼用？[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)