【正文】 中應(yīng)該拋棄并重新清零，不然的話這個負(fù)數(shù)將會減少接下來的和。 參考代碼： ///////////////////////////////////////////////////////////////////////////// // Find the greatest sum of all subarrays // 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 8 int amp。 int nCurSum = nGreatestSum = 0。 i nLength。 // if the current sum is negative, discard it if(nCurSum 0) nCurSum = 0。 } // if all data are negative, find the greatest element in the array if(nGreatestSum == 0) { nGreatestSum = pData[0]。 i nLength。 } } return true。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個空指針是應(yīng)該返回什么呢？返回 0？那這個函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是 0 這兩中情況呢？基于這個考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時讓函數(shù)返回一個函數(shù)是否正常執(zhí)行的標(biāo)志。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時，子數(shù)組和的最大值就是數(shù)組中的最大 元素。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。 例如輸入整數(shù) 22 和如下二元樹 10 / \ 5 12 / \ 4 7 則打印出兩條路徑： 10, 12 和 10, 5, 7。 // value of node BinaryTreeNode *m_pLeft。 // right child of node }。 當(dāng)訪問到某一結(jié)點時，把該結(jié)點添加到路徑上，并累加當(dāng)前結(jié)點的值。如果當(dāng)前結(jié)點不是葉結(jié)點，則繼續(xù)訪問它的子結(jié)點。因此 我們在函數(shù)退出之前要在路徑上刪除當(dāng)前結(jié)點并減去當(dāng)前結(jié)點的值，以確保返回父結(jié)點時路徑剛好是根結(jié)點到父結(jié)點的路徑。 參考代碼： /////////////////////////////////////////////////////////////////////// // Find paths whose sum equal to expected sum /////////////////////////////////////////////////////////////////////// void FindPath ( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vectorintamp。 currentSum // the sum of path ) { if(!pTreeNode) return。 (pTreeNodem_nValue)。amp。 if(currentSum == expectedSum amp。 isLeaf) { std::vectorint::iterator iter =()。 iter != ()。\t39。 } // if the node is not a leaf, goto its children if(pTreeNodem_pLeft) FindPath(pTreeNodem_pLeft, 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 node39。 //!!I think here is no use ()。 例如輸入 1， 2， 3， 4， 5， 6， 7 和 8 這 8 個數(shù)字，則最小的 4 個數(shù)字為 1， 2， 3 和 4。只是這種思路的時間復(fù)雜度為 O(nlogn)。 我們可以開辟一個長度為 k 的數(shù)組。如果數(shù)組中已經(jīng)插入的元素少于 k 個，則將讀入的整數(shù)直接放到數(shù)組中。如果讀入的這個整數(shù)比數(shù)組中已有 k個整數(shù)的最大值要小，則用讀入的這個整數(shù)替換這 個最大值；如果讀入的整數(shù)比數(shù)組中已有 k 個整數(shù)的最大值還要大，則讀入的這個整數(shù)不可能是最小的 k 個整數(shù)之一，拋棄這個整數(shù)。 通常情況下 k 要遠(yuǎn)小于 n，所以這種辦法要優(yōu)于前面的思路。不過從給面試官留下更好印象的角度出發(fā)，我們可以 11 進(jìn)一步把代碼寫得更漂亮一些。在常用的數(shù)據(jù)結(jié)構(gòu)中，能夠在 O(1)時間里得到最大值的數(shù)據(jù)結(jié)構(gòu)為最大堆 。 另外，自己重頭開始寫一個最大堆需要一定量的代碼。同樣， STL中的 set 和 multiset 為我們做了很好的堆的實現(xiàn)，我們可以拿過來用。 typedef multisetint, greaterint IntHeap。 data, // a vector of data IntHeapamp。 if(k == 0 || () k) return。 for(。 ++ iter) { // if less than k numbers was inserted into leastNumbers if((()) k) (*iter)。s full now else { // first number in leastNumbers is the greatest one 12 IntHeap::iterator iterFirst = ()。 (*iter)。如果是返回true，否則返回 false。 如果輸入 5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回 false。 在后續(xù)遍歷得到的序列中，最后一個元素為樹的根結(jié)點。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。 /////////////////////////////////////////////////////////////////////// // 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, 13 // otherwise, return false /////////////////////////////////////////////////////////////////////// bool verifySquenceOfBST(int squence[], int length) { if(squence == NULL || length = 0) return false。 // the nodes in left subtree are less than the root int i = 0。 i length 1。 } // the nodes in the right subtree are greater than the root int j = i。 j length 1。 } // verify whether the left subtree is a BST bool left = true。 // verify whether the right subtree is a BST bool right = true。 return (left amp。 right)。句子中單詞以空格符隔開。 例如輸入“ I am a student.”，則輸出“ student. a am I”。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。這時，不但翻轉(zhuǎn)了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉(zhuǎn)了。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時的順序保持一致。翻轉(zhuǎn)“ I am a student.”中所有字符得到“ .tneduts a ma I”，再翻轉(zhuǎn)每個單詞中字符的順序得到“ students. a am I”，正是符合要求的輸出。 while(pBegin pEnd) { char temp = *pBegin。 *pEnd = temp。 } } /////////////////////////////////////////////////////////////////////// // Reverse the word order in a sentence, but maintain the character // order inside a word // Input: pData the sentence to be reversed ///////////////////////////////////////////////////////////////////// 15 // char* ReverseSentence(char *pData) { if(pData == NULL) return NULL。 char *pEnd = pData。\039。 pEnd。 // Reverse every word in the sentence pBegin = pEnd = pData。\039。 39。 pEnd ++。 } // A word is between with pBegin and pEnd, reverse it else if(*pEnd == 39。 || *pEnd == 39。) { Reverse(pBegin, pEnd)。 } else { pEnd ++。 } 16 (08)－求 1+2+...+n 題目：求 1+2+…+n ，要求不能使用乘除法、 for、 while、 if、 else、 switch、 case 等關(guān)鍵 字以及條件判斷語句（ A?B:C）。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關(guān)技術(shù)理解的深刻程度。由于已經(jīng)明確限制 for 和 while 的使用，循環(huán)已經(jīng)不能再用了。 我們?nèi)匀粐@循環(huán)做文章。比如定義一個類，我們 new一含有 n 個這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會被調(diào)用 n次。如下代碼正是基于這個思路： class Temp { public: Temp() { ++ N。 } static void Reset() { N = 0。 } static int GetSum() { return Sum。 static int Sum。 int Temp::N = 0。 int solution1_Sum(int n) { Temp::Reset()。 delete []a。 return