【正文】 pEnd != 39。 // Reverse the whole sentence Reverse(pBegin, pEnd)。) { if(*pBegin == 39。 continue。\039。 } } return pData。 通常求 1+2+…+n 除了用公式 n(n+1)/2 之外，無外乎循環(huán)和遞歸兩種思路。循環(huán)只是讓相同的代碼執(zhí)行 n 遍而已， 我們完全可以不用 for 和while 達(dá)到這個效果。 Sum += N。 } private: static int N。 int Temp::Sum = 0。 a = 0。一個函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個函數(shù)處理終止遞歸的情況 ，我們需要做的就是在兩個函數(shù)里二選一。有了上述分析，我們再來看下面的代碼： class A。 class B: public A { public: virtual int Sum (int n) { return Array[!!n]Sum(n1)+n。 Array[0] = amp。 int value = Array[1]Sum(n)。我們也可以直 接用函數(shù)指針數(shù)組，這樣可能還更直接一些： typedef int (*fun)(int)。 } 18 另外我們還可以讓編譯器幫我們來完成類似于遞歸的運(yùn)算，比如如下代碼： template int n struct solution4_Sum { enum Value { N = solution4_Sumn 1::N + n}。 solution4_Sum100::N就是 1+2+...+100 的結(jié)果。由于這個過程是在編譯過程中完成的，因此要求輸入 n必須是在編譯期間就能確定，不能動態(tài)輸入。鏈表的倒數(shù)第 0 個結(jié)點(diǎn)為鏈表的尾指針。 分析：為了得到倒數(shù)第 k 個結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再從尾端回溯 k 步。假設(shè)整個鏈表有 n個結(jié)點(diǎn)，那么倒數(shù)第 k個結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第 nk1 個結(jié)點(diǎn)（從 0開始計(jì)數(shù)）。第一次得到鏈表中結(jié)點(diǎn)個數(shù) n，第二次得到從頭結(jié)點(diǎn)開始的第 nk1 個結(jié)點(diǎn)即倒數(shù)第 k 個結(jié)點(diǎn)。我們能不能把鏈表遍 歷的次數(shù)減少到 1？如果可以，將能有效地提高代碼執(zhí)行的時間效率。對于很長的鏈表，只需要把每個結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。 unsigned int nNum = 0。 // the kth node from the tail of a list // is the (n k)th node from the head pCur = pListHead。 return pCur。 for(unsigned int i = 0。 } } pBehind = pListHead。 } 討論：這道題的代碼有大量的指針操作。 另外，這兩種思路對應(yīng)的代碼都含有循環(huán)。如果該鏈表的結(jié)點(diǎn)數(shù)為奇數(shù)，輸出中間的結(jié)點(diǎn)；如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，輸出中間兩個結(jié)點(diǎn)前面的一個。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可?？上н@種思路需要的時間復(fù)雜度是 O(n2)。 我們把前面的思路整理一下：最初我們找到數(shù)組的第一個數(shù)字和最后一個數(shù)字。感興趣的讀者可以自行證明一下。 if(length 1) return found。 // if the sum of two numbers is equal to the input // we have found them if(curSum == sum) { num1 = data[behind]。 } // if the sum of two numbers is greater than the input // decrease the greater number else if(curSum sum) ahead 。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。 // right child of node }。 上面的分析印證了我們的直覺：在遍歷二元查找樹時每訪問到一個結(jié)點(diǎn)，交換它的左右子樹。 pNodem_pLeft = pNodem_pRight。 } 由于遞歸的本質(zhì)是編譯器生成了一個函數(shù)調(diào)用的棧，因此用循環(huán)來完成同樣任務(wù)時最簡單的辦法就是用一個輔助棧來模擬遞歸。這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹了。 while(()) { BSTreeNode *pNode = ()。 pNodem_pRight = pTemp。 例如輸入 8 / \ 6 10 /\ /\ 5 7 9 11 輸出 8 6 10 5 7 9 11。自然先應(yīng)該打印根結(jié)點(diǎn) 8，同時為了下次能夠打印 8的兩個子結(jié)點(diǎn)，我們應(yīng)該在遍歷到 8 時把子結(jié)點(diǎn) 6 和 10 保存到一個數(shù)據(jù)容器中。接下來我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn) 10 訪問了。實(shí)際上我們無需自己動手實(shí)現(xiàn)一個，因?yàn)?STL已經(jīng)為我們實(shí)現(xiàn)了一個很好的 deque（兩端都可以進(jìn)出的隊(duì)列），我們只需要拿過來用就可以了。 參考代碼： include deque 26 include iostream using namespace std。 // right child of node }。 while(()) { // get a node from the head of queue BTreeNode *pNode = ()。 // print its left child subtree if it has if(pNodem_pLeft) (pNodem_pLeft)。 // print the node cout pNodem_nValue 39。 // get a empty queue dequeBTreeNode * dequeTreeNode。 // value of node BTreeNode *m_pLeft。同時如果對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。因此不難看出這個數(shù)據(jù)容器的類型應(yīng)該是個隊(duì)列。按照從左往右的要求，我們先取出 6 訪問。這道題實(shí)質(zhì)上是要求遍歷一棵二元樹，只不過不是我們熟悉的前序、中序或者后序遍歷。 // push right child subtree into stack if not null if(pNodem_pRight) (pNodem_pRight)。 25 // swap the right and left child subtree BSTreeNode *pTemp = pNodem_pLeft。 std::stackBSTreeNode*stackTreeNode。在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹。 // mirror left child subtree if not null if(pNodem_pLeft) MirrorRecursively(pNodem_pLeft)。參考代碼如下： /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) recursively // the head of BST in initial call ///////////////////////////////////////////////////////////////////// 24 // void MirrorRecursively(BSTreeNode *pNode) { if(!pNode) return。我們試著在遍歷例子中的二元查找樹的同時來交換每個結(jié)點(diǎn)的左右子樹。 // value of node BSTreeNode *m_pLeft。 } return found。 found = true。 int behind = 0。 num1, // the first number, output intamp。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個數(shù)字；如果小于輸入的數(shù)字呢？我們希望兩個數(shù)字的和再大一點(diǎn)。由于 4+11=15，因此輸出 4 和 11。 (10)－在排序數(shù)組中查找和為給定值的兩個數(shù)字 題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。是該用小于還是小于等于？是該用 k 還是該用 k1？由于題目要求的是從 0 開始計(jì)數(shù)，而我們的習(xí)慣思維是從 1 開始計(jì)數(shù)，因此首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之后再用邊界值、邊界值減 邊界值加 1都運(yùn)行一次（在紙上寫代碼就只能在心里運(yùn)行了） 。因此每個公司都希望程序員在操作指針時有良好的習(xí)慣，比如使用指針之前判斷是不是空指針。 pBehind = pBehindm_pNext。 ++ i) { if(pAheadm_pNext != NULL) pAhead = pAheadm_pNext。 ListNode *pAhead = pListHead。 i nNum k。 nNum ++。 思路一的參考代碼： /////////////////////////////////////////////////////////////////////// // 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。由于兩個指針的距離保持在 k1，當(dāng)?shù)谝粋€（走在前面的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時，第二個指針（走在后面的）指針正好是倒數(shù)第 k 個結(jié)點(diǎn)。但如果輸入的鏈表的結(jié)點(diǎn)個數(shù)很多，有可能不能一次性把整個鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個結(jié)點(diǎn)需要兩次從硬盤讀入到物理內(nèi)存。如何得到結(jié)點(diǎn)數(shù) n？這個不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。因此我們需要打開我們的思路。 ListNode* m_pNext。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求 n不能太大。但以 100為參數(shù)的類型需要得到以 99 為 參 數(shù) 的 類 型 ， 因 為solution4_Sum100::N=solution4_Sum99::N+100。 template struct solution4_Sum1 { enum Value { N = 1}。 } int solution3_f2(int i) { fun f[2]={solution3_f1, solution3_f2}。 } 這種方法是用虛函數(shù)來實(shí)現(xiàn)函數(shù)的選擇。 Array[1] = amp。 int solution2_Sum(int n) { A a。 class A { public: virtual int Sum (int n) { return 0。那現(xiàn)在的問題是如和把數(shù)值變量 n 轉(zhuǎn)換成布爾值。 } 我們同樣也可以圍繞遞歸做文章。 Temp *a = new Temp[n]。 }。 Sum = 0。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。同樣，遞歸函數(shù)也需要用 if 語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語句了。 分析：這道題沒有多少實(shí)際意義，因?yàn)樵谲浖_發(fā)中不會有這么變態(tài)的限制。 pBegin = ++pEnd。 39。) { pBegin ++。 while(*pBegin != 39。) pEnd ++。 char *pBegin = pData。 *pBegin = *pEnd。 還是以上面的輸入為例子。 由于本題需要翻轉(zhuǎn)句子，我們先