題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
分析：由于編寫字符串相關代碼能夠反映程序員的編程能力和編程習慣，與字符串相關的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。
由于本題需要翻轉句子，我們先顛倒句子中的所有字符。這時，不但翻轉了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nè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;
}
判斷整數(shù)序列是不是二元查找樹的后序遍歷結果[折疊]
題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結果。如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。
分析：這是一道trilogy的筆試題，主要考查對二元查找樹的理解。
在后續(xù)遍歷得到的序列中，最后一個元素為樹的根結點。從頭開始掃描這個序列，比根結點小的元素都應該位于序列的左半部分;從第一個大于跟結點開始到跟結點前面的一個元素為止，所有元素都應該大于跟結點，因為這部分元素對應的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認序列的左、右兩部分是不是都是二元查找樹。
參考代碼：
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);
}
