【正文】 template typename T const Tamp。 CStackWithMinT::top() const { return ()。 6 } // insert an elment at the end of stack template typename T void CStackWithMinT::push(const Tamp。 value) { // append the data into the end of m_data (value)。 // set the index of minimum elment in m_data at the end of m_minIndex if(() == 0) (0)。 else { if(value m_data[()]) (() 1)。 else (())。 } } // erease the element at the end of stack template typename T void CStackWithMinT::pop() { // pop m_data ()。 // pop m_minIndex ()。 } // get the minimum element of stack template typename T const Tamp。 CStackWithMinT::min() const { assert(() 0)。 assert(() 0)。 return m_data[()]。 } 舉個(gè)例子演示上述代碼的運(yùn)行過程： 步驟 數(shù)據(jù)棧 輔助棧 最小值 3 3 0 3 4 3,4 0,0 3 2 3,4,2 0,0,2 2 7 1 3,4,2,1 0,0,2,3 1 3,4,2 0,0,2 2 3,4 0,0 3 0 3,4,0 0,0,2 0 討論：如果思路正確，編寫上述代碼不是一件很難的事情。但如果能注意一些細(xì)節(jié)無疑能在面試中加分。比如我在上面的代碼中做了如下的工作： ? 用模板類實(shí)現(xiàn)。如果別人的元素類型只是 int 類型，模板將能給面試官帶來好印象； ? 兩個(gè)版本的 top 函數(shù)。在很多類中，都需要提供 const 和非 const版本的成員訪問函數(shù)； ? min 函數(shù)中 assert。把代碼寫的盡量安全是每個(gè)軟件公司對程序員的要求； ? 添加一些注釋。注釋既能提高代碼的可讀性，又能增加代碼量，何樂而不為？ 總之，在面試時(shí)如果時(shí)間允許，盡量把代碼寫的漂亮一些。說不定代碼中的幾個(gè)小亮點(diǎn)就能讓自己輕松拿到心儀的 Offer。 (03)－求子數(shù)組的最大和 題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為 O(n)。 例如輸入的數(shù)組為 1, 2, 3, 10, 4, 7, 2, 5，和最大的子數(shù)組為 3, 10, 4, 7, 2，因此輸出為該子數(shù)組的和 18。 分析：本題最初為 2020 年浙江大學(xué)計(jì)算機(jī)系的考研題的最后一道程序設(shè)計(jì)題，在 2020 年里包括 google 在內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為 2020 年程序員面試題中經(jīng)典中的經(jīng)典。 如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長度為 n 的數(shù)組有 O(n2)個(gè)子數(shù)組；而且求一個(gè)長度為 n 的數(shù)組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是 O(n3)。 很容易理解，當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(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。nGreatestSum // the greatest sum of all subarrays ) { // 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。 } 討論：上述代碼中有兩點(diǎn)值得和大家討論一下： ? 函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回 0？那這個(gè)函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是 0 這兩中情況呢？基于這個(gè)考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)函數(shù)是否正常執(zhí)行的標(biāo)志。 ? 輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時(shí)，子數(shù)組和的最大值就是數(shù)組中的最大 元素。 9 (04)－在二元樹中找出和為某一值的所有路徑 題目：輸入一個(gè)整數(shù)和一棵二元樹。從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。 例如輸入整數(shù) 22 和如下二元樹 10 / \ 5 12 / \ 4 7 則打印出兩條路徑： 10, 12 和 10, 5, 7。 二元樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為： struct BinaryTreeNode // a node in the binary tree { int m_nValue。 // value of node BinaryTreeNode *m_pLeft。 // left child of node BinaryTreeNode *m_pRight。 // right child of node }。 分析：這是百度的一道筆試題，考查對樹這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。 當(dāng)訪問到某一結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動回到父結(jié)點(diǎn)。因此 我們在函數(shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個(gè)棧結(jié)構(gòu)，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過程。 參考代碼： /////////////////////////////////////////////////////////////////////// // Find paths whose sum equal to expected sum /////////////////////////////////////////////////////////////////////// void FindPath ( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vectorintamp。path, // a pathfrom root to current node intamp。 currentSum // the sum of path ) { if(!pTreeNode) return。 10 currentSum += pTreeNodem_nValue。 (pTreeNodem_nValue)。 // if the node is a leaf, and the sum is same as predefined, // the path is what we want. print the path bool isLeaf = (!pTreeNodem_pLeft amp。amp。 !pTreeNodem_pRight)。 if(currentSum == expectedSum amp。amp。 isLeaf) { std::vectorint::iterator iter =()。 for(。 iter != ()。 ++ iter) std::cout*iter39。\t39。 std::coutstd::endl。 } // if the node is not a leaf, goto its children if(pTreeNodem_pLeft) FindPath(pTreeNodem_pLeft, expectedSum, path, currentSum)。 if(pTreeNodem_pRight) FindPath(pTreeNodem_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 node39。s value from the current sum currentSum = pTreeNodem_nValue。 //!!I think here is no use ()。 } (05)查找最小的 k個(gè)元素 題目：輸入 n 個(gè)整數(shù)，輸出其中最小的 k 個(gè)。 例如