程式員面試題精選(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; // right child 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 the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
// else return the greatest node in the sub-tree
///
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
if(!pNode)
return NULL;
BSTreeNode *pLeft = NULL;
BSTreeNode *pRight = NULL;
// Convert the left sub-tree
if(pNode->m_pLeft)
pLeft = ConvertNode(pNode->m_pLeft, false);
// Connect the greatest node in the left sub-tree to the current node
if(pLeft)
{
pLeft->m_pRight = pNode;
pNode->m_pLeft = pLeft;
}
// Convert the right sub-tree
if(pNode->m_pRight)
pRight = ConvertNode(pNode->m_pRight, true);
// Connect the least node in the right sub-tree to the current node
if(pRight)
{
pNode->m_pRight = pRight;
pRight->m_pLeft = pNode;
}
BSTreeNode *pTemp = pNode;
// If the current node is the right child of its parent,
// return the least node in the tree whose root is the current node
if(asRight)
{
while(pTemp->m_pLeft)
pTemp = pTemp->m_pLeft;
}
// If the current node is the left child of its parent,
// return the greatest node in the tree whose root is the current node
else
{
while(pTemp->m_pRight)
pTemp = pTemp->m_pRight;
}
return pTemp;
}
///
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
// As we want to return the head of the sorted double-linked list,
// we set the second parameter to be true
return ConvertNode(pHeadOfTree, true);
}
思路二對應的代碼：
///
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// pLastNodeInList - the tail of the double-linked list
///
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
if(pNode == NULL)
return;
BSTreeNode *pCurrent = pNode;
// Convert the left sub-tree
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
// Put the current node into the double-linked list
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
pLastNodeInList->m_pRight = pCurrent;
pLastNodeInList = pCurrent;
// Convert the right sub-tree
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
///
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);
// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
程式員面試題精選(02)－設計包含min函數的棧
題目：定義棧的資料結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間複雜度都是O(1)。
分析：這是去年google的一道面試題。
我看到這道題目時，第一反應就是每次push一個新元素時，将棧裡所有逆序元素排序。這樣棧頂元素将是最小元素。但由于不能保證最後push進棧的元素最先出棧，這種思路設計的資料結構已經不是一個棧了。
在棧裡添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，如果該元素比目前的最小元素還要小，則更新最小元素。
乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果目前最小元素被pop出去，如何才能得到下一個最小元素？
是以僅僅隻添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時将最小元素（或最小元素的位置。考慮到棧元素的類型可能是複雜的資料結構，用最小元素的位置将能減少空間消耗）push到輔助棧中；每次pop一個元素出棧的時候，同時pop輔助棧。
參考代碼：
#include <deque>
#include <assert.h>
template <typename T> class CStackWithMin
{
public:
CStackWithMin(void) {}
virtual ~CStackWithMin(void) {}
T& top(void);
const T& top(void) const;
void push(const T& value);
void pop(void);
const T& min(void) const;
private:
T> m_data; // the elements of stack
size_t> m_minIndex; // the indices of minimum elements
};
// get the last element of mutable stack
template <typename T> T& CStackWithMin<T>::top()
{
return m_data.back();
}
// get the last element of non-mutable stack
template <typename T> const T& CStackWithMin<T>::top() const
{
return m_data.back();
}
// insert an elment at the end of stack
template <typename T> void CStackWithMin<T>::push(const T& value)
{
// append the data into the end of m_data
m_data.push_back(value);
// set the index of minimum elment in m_data at the end of m_minIndex
if(m_minIndex.size() == 0)
m_minIndex.push_back(0);
else
{
if(value < m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.size() - 1);
else
m_minIndex.push_back(m_minIndex.back());
}
}
// erease the element at the end of stack
template <typename T> void CStackWithMin<T>::pop()
{
// pop m_data
m_data.pop_back();
// pop m_minIndex
m_minIndex.pop_back();
}
// get the minimum element of stack
template <typename T> const T& CStackWithMin<T>::min() const
{
assert(m_data.size() > 0);
assert(m_minIndex.size() > 0);
return m_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
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;
int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];
// if the current sum is negative, discard it
if(nCurSum < 0)
nCurSum = 0;
// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
nGreatestSum = nCurSum;
}
// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
nGreatestSum = pData[i];
}
}
return true;
}
讨論：上述代碼中有兩點值得和大家讨論一下：
· 函數的傳回值不是子數組和的最大值，而是一個判斷輸入是否有效的标志。如果函數傳回值的是子數組和的最大值，那麼當輸入一個空指針是應該傳回什麼呢？傳回0？那這個函數的使用者怎麼區分輸入無效和子數組和的最大值剛好是0這兩中情況呢？基于這個考慮，本人認為把子數組和的最大值以引用的方式放到參數清單中，同時讓函數傳回一個函數是否正常執行的标志。
· 輸入有一類特殊情況需要特殊處理。當輸入數組中所有整數都是負數時，子數組和的最大值就是數組中的最大元素。
程式員面試題精選(04)－在二進制樹中找出和為某一值的所有路徑
題目：輸入一個整數和一棵二進制樹。從樹的根結點開始往下通路一直到葉結點所經過的所有結點形成一條路徑。列印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二進制樹
10
/ /
5 12
/ /
4 7
則列印出兩條路徑：10, 12和10, 5, 7。
二進制樹結點的資料結構定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
分析：這是百度的一道筆試題，考查對樹這種基本資料結構以及遞歸函數的了解。
當通路到某一結點時，把該結點添加到路徑上，并累加目前結點的值。如果目前結點為葉結點并且目前路徑的和剛好等于輸入的整數，則目前的路徑符合要求，我們把它列印出來。如果目前結點不是葉結點，則繼續通路它的子結點。目前結點通路結束後，遞歸函數将自動回到父結點。是以我們在函數退出之前要在路徑上删除目前結點并減去目前結點的值，以確定傳回父結點時路徑剛好是根結點到父結點的路徑。我們不難看出儲存路徑的資料結構實際上是一個棧結構，因為路徑要與遞歸調用狀态一緻，而遞歸調用本質就是一個壓棧和出棧的過程。
參考代碼：
///
// 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 path from root to current node
int& currentSum // the sum of path
)
{
if(!pTreeNode)
return;
currentSum += pTreeNode->m_nValue;
path.push_back(pTreeNode->m_nValue);
// if the node is a leaf, and the sum is same as pre-defined,
// the path is what we want. print the path
bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum == expectedSum && isLeaf)
{
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
std::cout << *iter << '/t';
std::cout << std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue;
path.pop_back();
}
程式員面試題精選(05)－查找最小的k個元素
題目：輸入n個整數，輸出其中最小的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 namespace std;
typedef multiset<int, greater<int> > IntHeap;
///
// find k least numbers in a vector
///
void FindKLeastNumbers
(
const vector<int>& data, // a vector of data
IntHeap& leastNumbers, // k least numbers, output
unsigned int k
)
{
leastNumbers.clear();
if(k == 0 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
{
// if less 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::iterator iterFirst = leastNumbers.begin();
// if is less than the previous greatest number
if(*iter < *(leastNumbers.begin()))
{
// replace the previous greatest number
leastNumbers.erase(iterFirst);
leastNumbers.insert(*iter);
}
}
}
}
程式員面試題精選(06)－判斷整數序列是不是二進制查找樹的後序周遊結果
題目：輸入一個整數數組，判斷該數組是不是某二進制查找樹的後序周遊的結果。如果是傳回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[], int length)
{
if(squence == NULL || length <= 0)
return false;
// root of a BST is at the end of post order traversal squence
int root = squence[length - 1];
// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
// verify whether the left sub-tree is a BST
bool left = true;
if(i > 0)
left = verifySquenceOfBST(squence, i);
// verify whether the right sub-tree is a BST
bool right = true;
if(i < length - 1)
right = verifySquenceOfBST(squence + i, length - i - 1);
return (left && right);
}
程式員面試題精選(07)－翻轉句子中單詞的順序
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞内字元的順序不變。句子中單詞以空格符隔開。為簡單起見，标點符号和普通字母一樣處理。
例如輸入"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)
{
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin ++, pEnd --;
}
}
///
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
///
char* ReverseSentence(char *pData)
{
if(pData == NULL)
return NULL;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != '/0')
pEnd ++;
pEnd--;
// Reverse the whole sentence
Reverse(pBegin, pEnd);
// Reverse every word in the sentence
pBegin = pEnd = pData;
while(*pBegin != '/0')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
continue;
}
// A word is between with pBegin and pEnd, reverse it
else if(*pEnd == ' ' || *pEnd == '/0')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
return pData;
}
程式員面試題精選(08)－求1+2+...+n
題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（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; }
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = 0;
return Temp::GetSum();
}
我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我們不妨定義兩個函數。一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，我們需要做的就是在兩個函數裡二選一。從二選一我們很自然的想到布爾變量，比如ture（1）的時候調用第一個函數，false（0）的時候調用第二個函數。那現在的問題是如和把數值變量n轉換成布爾值。如果對n連續做兩次反運算，即!!n，那麼非零的n轉換為true，0轉換為false。有了上述分析，我們再來看下面的代碼：
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
return value;
}
這種方法是用虛函數來實作函數的選擇。當n不為零時，執行函數B::Sum；當n為0時，執行A::Sum。我們也可以直接用函數指針數組，這樣可能還更直接一些：
typedef int (*fun)(int);
int solution3_f1(int i)
{
return 0;
}
int solution3_f2(int i)
{
fun f[2]={solution3_f1, solution3_f2};
return i+f[!!i](i-1);
}
另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：
template <int n> struct solution4_Sum
{
enum Value { N = solution4_Sum<n - 1>::N + n};
};
template <> struct solution4_Sum<1>
{
enum Value { 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, unsigned int k)
{
if(pListHead == NULL)
return NULL;
// count the nodes number in the list
ListNode *pCur = pListHead;
unsigned int nNum = 0;
while(pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
nNum ++;
}
// if the number of nodes in the list is less than k
// do nothing
if(nNum < k)
return NULL;
// the kth node from the tail of a list
// is the (n - k)th node from the head
pCur = pListHead;
for(unsigned int i = 0; i < nNum - k; ++ i)
pCur = pCur->m_pNext;
return pCur;
}
思路二的參考代碼：
///
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
// k - the distance to the tail
// Output: the kth node from the tail of a list
///
ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k)
{
if(pListHead == NULL)
return NULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for(unsigned int i = 0; i < k; ++ i)
{
if(pAhead->m_pNext != NULL)
pAhead = pAhead->m_pNext;
else
{
// if the number of nodes in the list is less than k,
// do nothing
return NULL;
}
}
pBehind = pListHead;
// the distance 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;
}
return pBehind;
}
讨論：這道題的代碼有大量的指針操作。在軟體開發中，錯誤的指針操作是大部分問題的根源。是以每個公司都希望程式員在操作指針時有良好的習慣，比如使用指針之前判斷是不是空指針。這些都是程式設計的細節，但如果這些細節把握得不好，很有可能就會和心儀的公司失之交臂。
另外，這兩種思路對應的代碼都含有循環。含有循環的代碼經常出的問題是在循環結束條件的判斷。是該用小于還是小于等于？是該用k還是該用k-1？由于題目要求的是從0開始計數，而我們的習慣思維是從1開始計數，是以首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之後再用邊界值、邊界值減1、邊界值加1都運作一次（在紙上寫代碼就隻能在心裡運作了）。
擴充：和這道題類似的題目還有：輸入一個單向連結清單。如果該連結清單的結點數為奇數，輸出中間的結點；如果連結清單結點數為偶數，輸出中間兩個結點前面的一個。如果各位感興趣，請自己分析并編寫代碼。
程式員面試題精選(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
(
int data[], // a sorted array
unsigned int length, // the length of the sorted array
int sum, // the sum
int& num1, // the first number, output
int& num2 // the second number, output
)
{
bool found = false;
if(length < 1)
return found;
int ahead = length - 1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
// if the sum 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 the sum of two numbers is greater than the input
// decrease the greater number
else if(curSum > sum)
ahead --;
// if the sum of two numbers is less than the input
// increase the less number
else
behind ++;
}
return found;
}
擴充：如果輸入的數組是沒有排序的，但知道裡面數字的範圍，其他條件不變，如和在O(n)時間裡找到這兩個數字？
程式員面試題精選(11)－求二進制查找樹的鏡像
題目：輸入一顆二進制查找樹，将該樹轉換為它的鏡像，即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8
/ /
6 10
// //
5 7 9 11
輸出：
8
/ /
10 6
// //
11 9 7 5
定義二進制查找樹的結點為：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child 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 the right 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);
// mirror right 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();
// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);
// push right 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 namespace std;
struct BTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BTreeNode *m_pLeft; // left child of node
BTreeNode *m_pRight; // right child 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 a empty queue
deque<BTreeNode *> dequeTreeNode;
// insert the root at the tail of queue
dequeTreeNode.push_back(pTreeRoot);
while(dequeTreeNode.size())
{
// get a node from the head of queue
BTreeNode *pNode = dequeTreeNode.front();
dequeTreeNode.pop_front();
// print the node
cout << pNode->m_nValue << ' ';
// print its left child sub-tree if it has
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
// print its 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)
{
// invalid input
if(!pString)
return 0;
// get a hash table, and initialize it
const int tableSize = 256;
unsigned int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++ i)
hashTable[i] = 0;
// get the how many times each char appears in the string
char* pHashKey = pString;
while(*(pHashKey) != '/0')
hashTable[*(pHashKey++)] ++;
// find the first char which appears only once in a string
pHashKey = pString;
while(*pHashKey != '/0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
// if the string is empty
// or every char in the string appears at least twice
return 0;
}
程式員面試題精選(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 at every time
// Output: the last number remaining when the input is valid,
// otherwise -1
///
int LastRemaining_Solution1(unsigned int n, unsigned int m)
{
// invalid input
if(n < 1 || m < 1)
return -1;
unsigned int i = 0;
// initiate a list with n integers (0, 1, ... n - 1)
list<int> integers;
for(i = 0; i < n; ++ i)
integers.push_back(i);
list<int>::iterator curinteger = integers.begin();
while(integers.size() > 1)
{
// find the 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();
}
// remove the 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 at every time
// Output: the last number remaining when the input is valid,
// otherwise -1
///
int LastRemaining_Solution2(int n, unsigned int m)
{
// invalid input
if(n <= 0 || m < 0)
return -1;
// if there are only one integer in the circle initially,
// of course the last remaining one is 0
int lastinteger = 0;
// find the last remaining one in the circle with n integers
for (int i = 2; i <= n; i ++)
lastinteger = (lastinteger + m) % i;
return lastinteger;
}
如果對兩種思路的時間複雜度感興趣的讀者可以把n和m的值設的稍微大一點，比如十萬這個數量級的數字，運作的時候就能明顯感覺出這兩種思路寫出來的代碼時間效率大不一樣。
程式員面試題精選(15)－含有指針成員的類的拷貝
題目：下面是一個數組類的聲明與實作。請分析這個類有什麼問題，并針對存在的問題提出幾種解決方案。
template<typename T> class Array
{
public:
Array(unsigned arraySize):data(0), size(arraySize)
{
if(size > 0)
data = new T[size];
}
~Array()
{
if(data) delete[] data;
}
void setValue(unsigned index, const T& value)
{
if(index < size)
data[index] = value;
}
T getValue(unsigned index) const
{
if(index < size)
return data[index];
else
return T();
}
private:
T* data;
unsigned size;
};
分析：我們注意在類的内部封裝了用來存儲數組資料的指針。軟體存在的大部分問題通常都可以歸結指針的不正确處理。
這個類隻提供了一個構造函數，而沒有定義構造拷貝函數和重載拷貝運算符函數。當這個類的使用者按照下面的方式聲明并執行個體化該類的一個執行個體
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(const Array& copy);
const Array& operator = (const Array& copy);
最初的代碼存在問題是因為不同執行個體的data指向的同一位址，删除一個執行個體的data會把另外一個執行個體的data也同時删除。是以我們還可以讓構造拷貝函數或者拷貝運算符的重載函數拷貝的不隻是位址，而是資料。由于我們重新存儲了一份資料，這樣一個執行個體删除的時候，對另外一個執行個體沒有影響。這種思路我們稱之為深度拷貝。實作的代碼如下：
public:
Array(const Array& copy):data(0), size(copy.size)
{
if(size > 0)
{
data = new T[size];
for(int i = 0; i < size; ++ i)
setValue(i, copy.getValue(i));
}
}
const Array& operator = (const Array& copy)
{
if(this == ©)
return *this;
if(data != NULL)
{
delete []data;
data = NULL;
}
size = copy.size;
if(size > 0)
{
data = new T[size];
for(int i = 0; i < size; ++ i)
setValue(i, copy.getValue(i));
}
}
為了防止有多個指針指向的資料被多次删除，我們還可以儲存究竟有多少個指針指向該資料。隻有當沒有任何指針指向該資料的時候才可以被删除。這種思路通常被稱之為引用計數技術。在構造函數中，引用計數初始化為1；每當把這個執行個體指派給其他執行個體或者以參數傳給其他執行個體的構造拷貝函數的時候，引用計數加1，因為這意味着又多了一個執行個體指向它的data；每次需要調用析構函數或者需要把data指派為其他資料的時候，引用計數要減1，因為這意味着指向它的data的指針少了一個。當引用計數減少到0的時候，data已經沒有任何執行個體指向它了，這個時候就可以安全地删除。實作的代碼如下：
public:
Array(unsigned arraySize)
:data(0), size(arraySize), count(new unsigned int)
{
*count = 1;
if(size > 0)
data = new T[size];
}
Array(const Array& copy)
: size(copy.size), data(copy.data), count(copy.count)
{
++ (*count);
}
~Array()
{
Release();
}
const Array& operator = (const Array& copy)
{
if(data == copy.data)
return *this;
Release();
data = copy.data;
size = copy.size;
count = copy.count;
++(*count);
}
private:
void Release()
{
--(*count);
if(*count == 0)
{
if(data)
{
delete []data;
data = NULL;
}
delete count;
count = 0;
}
}
unsigned int *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 long Fibonacci_Solution1(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
return Fibonacci_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 long Fibonacci_Solution2(unsigned n)
{
int result[2] = {0, 1};
if(n < 2)
return result[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;
}
return fibN;
}
這還不是最快的方法。下面介紹一種時間複雜度是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
(
long long m00 = 0,
long long m01 = 0,
long long m10 = 0,
long long 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
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
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));
}
return matrix;
}
///
// Calculate the nth item of Fibonacci Series using devide and conquer
///
long long Fibonacci_Solution3(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
return PowerNMinus2.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(const char* str)
{
g_nStatus = kInvalid;
long long num = 0;
if(str != NULL)
{
const char* digit = str;
// the first char in the string maybe '+' or '-'
bool minus = false;
if(*digit == '+')
digit ++;
else if(*digit == '-')
{
digit ++;
minus = true;
}
// the remaining 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 ++;
}
// if the char is not a digit, invalid input
else
{
num = 0;
break;
}
}
if(*digit == '/0')
{
g_nStatus = kValid;
if(minus)
num = 0 - num;
}
}
return static_cast<int>(num);
}
讨論：在參考代碼中，我選用的是第一種聲明方式。不過在面試時，我們可以選用任意一種聲明方式進行實作。但當面試官問我們選擇的理由時，我們要對兩者的優缺點進行評價。第一種聲明方式對使用者而言非常直覺，但使用了全局變量，不夠優雅；而第二種思路是用傳回值來表明輸入是否合法，在很多API中都用這種方法，但該方法聲明的函數使用起來不夠直覺。
最後值得一提的是，在C語言提供的庫函數中，函數atoi能夠把字元串轉換整數。它的聲明是int atoi(const char *str)。該函數就是用一個全局變量來标志輸入是否合法的。
程式員面試題精選(18)－用兩個棧實作隊列
題目：某隊列的聲明如下：
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // 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 the new element into m_stack1
m_stack1.push(element);
}
///
// Delete the head from the queue
///
template<typename T> void CQueue<T>::deleteHead()
{
// if m_stack2 is empty,
// and there are some elements in m_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 the element 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)
{
// get the next node, and save it at pNext
ListNode* pNext = pNode->m_pNext;
// if the next 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;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
擴充：本題也可以遞歸實作。感興趣的讀者請自己編寫遞歸代碼。
程式員面試題精選(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 or j<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 first string
// pStr2 - the second string
// Output: the length of two strings' LCSs
/
int LCS(char* pStr1, char* pStr2)
{
if(!pStr1 || !pStr2)
return 0;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(!length1 || !length2)
return 0;
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;
}
// a char of LCS is found,
// it comes from the left up entry in the direction matrix
else if(pStr1[i] == pStr2[j])
{
LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
LCS_direction[i][j] = kLeftUp;
}
// it comes from the up entry in the direction matrix
else if(LCS_length[i - 1][j] > LCS_length[i][j - 1])
{
LCS_length[i][j] = LCS_length[i - 1][j];
LCS_direction[i][j] = kUp;
}
// it comes 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);
return LCS_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 matrix LCS_direction
// col - the column index in the matrix LCS_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;
// kLeftUp implies 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)
{
// move to 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)
{
// move to 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)
{
int nLength = 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);
}
}
return pStr;
}
///
// Reverse the string between pStart and pEnd
///
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *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(int i)
{
int count = 0;
while(i)
{
if(i & 1)
count ++;
i = i >> 1;
}
return count;
}
可能有讀者會問，整數右移一位在數學上是和除以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(int i)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(i & flag)
count ++;
flag = flag << 1;
}
return count;
}
另外一種思路是如果一個整數不為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(int i)
{
int count = 0;
while (i)
{
++ count;
i = (i - 1) & i;
}
return count;
}
擴充：如何用一個語句判斷一個整數是不是二的整數次幂？
程式員面試題精選(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題，這裡就不在贅述了。
1.
某種傳染病第一天隻有一個患者，前五天為潛伏期，不發作也不會傳染人
第6天開始發作，從發作到治愈需要5天時間，期間每天傳染3個人
求第N天共有多少患者
2.
将字元串中相鄰相同的子串合并為一個子串，如"12342343454565678789" -- "123456789"
3.
求一個串中出現的第一個最長重複子串。采用順序結構存儲串，實作求串s中出現的第一個最長重複子串的下标和長度
4.
求bit位中1的總個數為n的所有整數集合
比如，二進制位中有兩個1的整數為：
0x00000003
0x00000005
0x00000006
.
.
.
0xc0000000
5.
去掉整數的bit位為1的最高的兩個bit位，如0x1030f --> 0x10f
6.
unsigned int intvert(unsigned int x, int p, int n)
實作對x的進行轉換, p為起始轉化位(最左邊為第1位算起), n為需要轉換的長度, 對這些bit位取反
假設起始點在右邊.如x = 0b0001 0001, p=4, n=3 轉換後x = 0b0110 0001
7.
C和C++混合程式設計，C源檔案中會調用C++源檔案中定義的函數int func_cpp(int)，C++也會調用C源程式中定義的函數int func_c(int)，
請組織程式的結構c.c, cpp.cpp, pro.h
答案：
在18樓我說了我對這幾題的思路，剛才全部用代碼實作了下，
沒嚴格測試，可能會有些小BUG
C/C++ code
//第一題
思路：
建立一個有十個元素的數組來模拟病例記錄就可以了
使用資料結構unsigned int array[10] = {1};
#include<iostream>
using namespace std;
unsigned int func(unsigned int (&array)[10], int days)
{
unsigned int new_infected = 0;//記錄新增的被感染者的人數
unsigned int infect_able = 0; //記錄會傳染的人數
unsigned int total = 0; //當天的總或者人數
int i;
for (i = 5; i < 10; i++)
infect_able += array[i];
for (i = 0; i < days; i++)
{
new_infected = infect_able * 3;
infect_able = infect_able + array[4] - array[9];
memmove(array + 1, array, sizeof (int) * 9);
array[0] = new_infected;
}
total = infect_able;
for (i = 0; i < 5; i++)
total += array[i];
return total;
}
int main()
{
unsigned int array[10] = {1};//第一天一個病人
int days;
cout<<"輸入天數："<<endl;
cin>>days;
int total = func(array, days);
cout<<"第"<<days<<"天患者人數為："<<total<<endl;
system("pause");
return 0;
}
//第二題
思路：
當檢索到某個位置時，查找前面該字元最近出現的位置到目前位置的子串是否和目前位置之後的資料是否相同，不同就更新該字元最新出現的位置，相同就strcpy
使用資料結構int all[256];
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *func(char *src)
{
int all[256];
int cur_index;
if (NULL == src)
return NULL;
for (cur_index = 0; cur_index < 256; cur_index++)
{
all[cur_index] = -1;
}
cur_index = 0;
while (src[cur_index])
{
int front_index = all[src[cur_index]];
if (front_index == -1)
{
all[src[cur_index]] = cur_index;
++cur_index;
}
else
{
int rear_index = cur_index;
for (; front_index < cur_index; front_index++, rear_index++)
{
if (src[front_index] != src[rear_index])
break;
}
if (front_index != cur_index)
{
all[src[cur_index]] = cur_index;
++cur_index;
}
else
{
strcpy(src + cur_index, src + rear_index);
}
}
}
return src;
}
int main()
{
char src[1000];
puts("請輸入字元串");
gets(src);
printf("%s/n", func(src));
system("pause");
return 0;
}
//第三題
周遊一遍就可以了，目前index與前面所有出現src[index]處全部比較一遍
使用資料結構vector<int> all[256];
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
void func(const char *src, int *pindex, int *plength)
{
vector<int> all[256];
int cnt;
assert(NULL != src && NULL != pindex && NULL != plength);
*pindex = -1;
*plength = 0;
for (cnt = 0; src[cnt]; ++cnt)
{
int times;
for (times = 0; times < all[src[cnt]].size(); ++times)
{
int pre = all[src[cnt]][times];
int cur = cnt;
while (src[pre] == src[cur])
{
++pre;
++cur;
}
if (pre - all[src[cnt]][times] > *plength)
{
*pindex = all[src[cnt]][times];
*plength = pre - all[src[cnt]][times];
}
}
all[src[cnt]].push_back(cnt);
}
}
int main()
{
int index;
int length;
char src[1000];
puts("請輸入字元串：");
gets(src);
func(src, &index, &length);
puts("結果如下：");
cout<<"index = "<<index<<endl;
cout<<"length = "<<length<<endl;
for (int i = index; i < index + length; i++)
{
cout<<src[i];
}
cout<<endl;
system("pause");
return 0;
}
//第四題
直接調整0和1的位置就可以了
#include<stdio.h>
#include<stdlib.h>
int get_next(unsigned int *pval)
{
int cur;
int low, hig;
for (cur = 0; cur != (sizeof(*pval) << 3) - 1; ++cur)
{
if ((*pval & (1 << cur)) && !((*pval & (1 << (cur + 1)))))
break;
}
if ((sizeof(*pval) << 3) - 1 == cur)
{
return 0;
}
for (low = 0, hig = cur + 1; !(*pval & (1 << low)); ++low)
;
*pval ^= (1 << hig);
*pval ^= (1 << low);
for (hig = cur, low = 0; hig > low; --hig, ++low)
{
if (((*pval & (1 << hig)) && (!(*pval & (1 << low)))) || ((*pval & (1 << low)) && (!(*pval & (1 << hig)))))
{
*pval ^= (1 << hig);
*pval ^= (1 << low);
}
}
return 1;
}
int main()
{
unsigned int val;
int bit1_num;
printf("輸入二進制位中1的個數：/n");
scanf("%d", &bit1_num);
if ((sizeof(int) << 3) < bit1_num || bit1_num < 0)
{
printf("Error/n");
exit(1);
}
if ((sizeof(unsigned int) << 3) == bit1_num)
val = -1;
else
val = ((1 << bit1_num) - 1);
do
{
printf("%x/n", val);
}while (get_next(&val));
system("pause");
return 0;
}
//第五題
#include<stdio.h>
#include<stdlib.h>
unsigned int func(unsigned int val)
{
unsigned int ui = val;
unsigned int left = 0, right = 0;
while (ui)
{
right = left;
left = (ui & -ui);
ui &= (ui - 1);
}
return (val & ~(left | right));
}
int main(int argc,char* argv[])
{
printf("%x/n", func(0x1030f));
system("pause");
return 0;
}
//第六題
#include<iostream>
using namespace std;
inline unsigned int intvert(unsigned int x, int p, int n)
{
//這裡加上參數的有效性檢查!
return x ^ (((1 << n) - 1) << (p - 1));
}
int main()
{
unsigned int x = 0;
printf("%x/n", intvert(x, 4, 3));
system("pause");
return 0;
}
//第七題
//pro.h
#ifndef _PRO_H_
#define _PRO_H_
#ifdef __cplusplus
extern "C"
{
#endif //__cplusplus
int func_cpp(int);
int func_c(int);
#ifdef __cplusplus
}
#endif //__cplusplus
#endif //_PRO_H_
//c.c
#include"pro.h"
int func_c(int)
{
...
}
//cpp.cpp
#include"pro.h"
int main()
{
...
}
int func_cpp(int)
{
...
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)