|
精選微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題
--答案公布
-------
我很享受思考的過(guò)程，個(gè)人思考的全部結(jié)果，都放在了這篇帖子上，
[整理]精選微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題
現(xiàn)在，我要，好好整理下，這篇帖子我已做出來(lái)的題目答案 了。
展示自己的思考結(jié)果，我覺(jué)得很驕傲。:)。
----------------------------------------------------------
2010年 10月18日下午 July
-------------------------------- 1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目： 輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。 要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 轉(zhuǎn)換成雙向鏈表 4=6=8=10=12=14=16。 首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; //引用 245 樓 tree_star 的回復(fù)
#include <stdio.h> #include <iostream.h> struct BSTreeNode
{ int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; typedef BSTreeNode DoubleList;
DoubleList * pHead; DoubleList * pListIndex; void convertToDoubleList(BSTreeNode * pCurrent);
// 創(chuàng)建二元查找樹 void addBSTreeNode(BSTreeNode * & pCurrent, int value) { if (NULL == pCurrent) { BSTreeNode * pBSTree = new BSTreeNode(); pBSTree->m_pLeft = NULL; pBSTree->m_pRight = NULL; pBSTree->m_nValue = value; pCurrent = pBSTree; }
else { if ((pCurrent->m_nValue) > value) { addBSTreeNode(pCurrent->m_pLeft, value); } else if ((pCurrent->m_nValue) < value) { addBSTreeNode(pCurrent->m_pRight, value); } else { //cout<<"重復(fù)加入節(jié)點(diǎn)"<<endl; } } } // 遍歷二元查找樹 中序
void ergodicBSTree(BSTreeNode * pCurrent) { if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { ergodicBSTree(pCurrent->m_pLeft); } // 節(jié)點(diǎn)接到鏈表尾部
convertToDoubleList(pCurrent); // 右子樹為空 if (NULL != pCurrent->m_pRight) { ergodicBSTree(pCurrent->m_pRight); } } // 二叉樹轉(zhuǎn)換成list
void convertToDoubleList(BSTreeNode * pCurrent) { pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex) { pListIndex->m_pRight = pCurrent; } else { pHead = pCurrent; } pListIndex = pCurrent; cout<<pCurrent->m_nValue<<endl; } int main()
{ BSTreeNode * pRoot = NULL; pListIndex = NULL; pHead = NULL; addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 15); addBSTreeNode(pRoot, 16); ergodicBSTree(pRoot); return 0; } /////////////////////////////////////////////// 4 6 8 10 12 14 15 16 Press any key to continue ////////////////////////////////////////////// 2.設(shè)計(jì)包含min函數(shù)的棧。 定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。 要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。 結(jié)合鏈表一起做。
首先我做插入以下數(shù)字：10，7，3，3，8，5，2， 6
0: 10 -> NULL (MIN=10, POS=0) 1: 7 -> [0] (MIN=7, POS=1) 用數(shù)組表示堆棧，第0個(gè)元素表示棧底 2: 3 -> [1] (MIN=3, POS=2) 3: 3 -> [2] (MIN=3, POS=3) 4: 8 -> NULL (MIN=3, POS=3) 技巧在這里，因?yàn)?比當(dāng)前的MIN大，所以彈出8不會(huì)對(duì)當(dāng)前的MIN產(chǎn)生影響 5：5 -> NULL (MIN=3, POS=3) 6: 2 -> [2] (MIN=2, POS=6) 如果2出棧了，那么3就是MIN 7: 6 -> [6] 出棧的話采用類似方法修正。
所以，此題的第1小題，即是借助輔助棧，保存最小值，
且隨時(shí)更新輔助棧中的元素。 如先后，push 2 6 4 1 5 stack A stack B（輔助棧） 4: 5 1 //push 5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push進(jìn)A的元素1小于B中棧頂元素2 2: 4 2 //push 4,min=p->[0]=2 | 1: 6 2 //push 6,min=p->[0]=2 | 0: 2 2 //push 2,min=p->[0]=2 | push第一個(gè)元素進(jìn)A，也把它push進(jìn)B，
當(dāng)向Apush的元素比B中的元素小， 則也push進(jìn)B，即更新B。否則，不動(dòng)B，保存原值。 向棧A push元素時(shí)，順序由下至上。 輔助棧B中，始終保存著最小的元素。 然后，pop棧A中元素，5 1 4 6 2
A B ->更新 4: 5 1 1 //pop 5,min=p->[3]=1 | 3: 1 1 2 //pop 1,min=p->[0]=2 | 2: 4 2 2 //pop 4,min=p->[0]=2 | 1: 6 2 2 //pop 6,min=p->[0]=2 | 0: 2 2 NULL //pop 2,min=NULL v 當(dāng)pop A中的元素小于B中棧頂元素時(shí)，則也要pop B中棧頂元素。
3.求子數(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。 //July 2010/10/18
#include <iostream.h>
int maxSum(int* a, int n)
{ int sum=0; int b=0; for(int i=0; i<n; i++)
{ if(b<0) b=a[i]; else b+=a[i]; if(sum<b) sum=b; } return sum; } int main()
{ int a[10]={1,-8,6,3,-1,5,7,-2,0,1}; cout<<maxSum(a,10)<<endl; return 0; } 運(yùn)行結(jié)果，如下：
20 Press any key to continue ------------------------------------------------------------
int maxSum(int* a, int n)
{ int sum=0; int b=0; for(int i=0; i<n; i++)
{ if(b<=0) //此處修正下，把b<0改為 b<=0 b=a[i]; else b+=a[i]; if(sum<b) sum=b; } return sum; } //////////////////////////////////////////////
解釋下： 例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5， 那么最大的子數(shù)組為3, 10, -4, 7, 2， 因此輸出為該子數(shù)組的和18 所有的東西都在以下倆行，
即： b：0 1 -1 3 13 9 16 18 7 sum：0 1 1 3 13 13 16 18 18 其實(shí)算法很簡(jiǎn)單，當(dāng)前面的幾個(gè)數(shù)，加起來(lái)后，b<0后，
把b重新賦值，置為下一個(gè)元素，b=a[i]。 當(dāng)b>sum，則更新sum=b; 若b<sum，則sum保持原值，不更新。:)。July、10/31。 /////////////////////////////////////////////// //關(guān)于第4題，
當(dāng)訪問(wèn)到某一結(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)前的路徑符合要求，我們把它打印出來(lái)。 如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問(wèn)它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪問(wèn)結(jié)束后，遞歸函數(shù)將自動(dòng)回到父結(jié)點(diǎn)。
因此我們?cè)诤瘮?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è)壓棧和出棧的過(guò)程。 其中，部分題目源碼及思路，參考自：
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(); } 5.查找最小的k個(gè)元素 題目：輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。 例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字， 則最小的4個(gè)數(shù)字為1，2，3和4。 //July 2010/10/18 //引用自116 樓 wocaoqwer 的回復(fù)。 #include<iostream> using namespace std; class MinK{
public: MinK(int *arr,int si):array(arr),size(si){} bool kmin(int k,int*& ret){
if(k>size) { ret=NULL; return false; } else { ret=new int[k--]; int i; for(i=0;i<=k;++i) ret[i]=array[i]; for(int j=(k-1)/2;j>=0;--j) shiftDown(ret,j,k); for(;i<size;++i) if(array[i]<ret[0]) { ret[0]=array[i]; shiftDown(ret,0,k); } return true; } } void remove(int*& ret){ delete[] ret; ret=NULL; } private: void shiftDown(int *ret,int pos,int length){ int t=ret[pos]; for(int s=2*pos+1;s<=length;s=2*s+1){ if(s<length&&ret[s]<ret[s+1]) ++s; if(t<ret[s]) { ret[pos]=ret[s]; pos=s; } else break; } ret[pos]=t; } int *array; int size; }; int main() { int array[]={1,2,3,4,5,6,7,8}; MinK mink(array,sizeof(array)/sizeof(array[0])); int *ret; int k=4; if(mink.kmin(k,ret)) { for(int i=0;i<k;++i) cout<<ret[i]<<endl; mink.remove(ret); } return 0; } ///////////////////////////////////////// 運(yùn)行結(jié)果： 4 2 3 1 Press any key to continue ///////////////////////////////////////// 第6題
------------------------------------ 騰訊面試題： 給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù) 要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。 上排的十個(gè)數(shù)如下： 【0，1，2，3，4，5，6，7，8，9】 初看此題，貌似很難，10分鐘過(guò)去了，可能有的人，題目都還沒(méi)看懂。
舉一個(gè)例子，
數(shù)值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0 0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次， 2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次.... 以此類推.. // 引用自July 2010年10月18日。 //數(shù)值: 0,1,2,3,4,5,6,7,8,9
//分配: 6,2,1,0,0,0,1,0,0,0 #include <iostream.h> #define len 10 class NumberTB { private: int top[len]; int bottom[len]; bool success; public: NumberTB(); int* getBottom(); void setNextBottom(); int getFrequecy(int num); }; NumberTB::NumberTB()
{ success = false; //format top for(int i=0;i<len;i++) { top[i] = i; } } int* NumberTB::getBottom() { int i = 0; while(!success) { i++; setNextBottom(); } return bottom; } //set next bottom
void NumberTB::setNextBottom() { bool reB = true; for(int i=0;i<len;i++) { int frequecy = getFrequecy(i); if(bottom[i] != frequecy) { bottom[i] = frequecy; reB = false; } } success = reB; } //get frequency in bottom
int NumberTB::getFrequecy(int num) //此處的num即指上排的數(shù) i { int count = 0; for(int i=0;i<len;i++) { if(bottom[i] == num) count++; } return count; //cout即對(duì)應(yīng) frequecy } int main()
{ NumberTB nTB; int* result= nTB.getBottom(); for(int i=0;i<len;i++)
{ cout<<*result++<<endl; } return 0; } /////////////////////////////////////////// 運(yùn)行結(jié)果： 6 2 1 0 0 0 1 0 0 0 Press any key to continue ///////////////////////////////////////// 第7題
------------------------------------ 微軟亞院之編程判斷倆個(gè)鏈表是否相交 給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。 為了簡(jiǎn)化問(wèn)題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。 問(wèn)題擴(kuò)展：
1.如果鏈表可能有環(huán)列? 2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列? //這一題，自己也和不少人討論過(guò)了，
//更詳細(xì)的，請(qǐng)看這里： //My sina Blog： //http://blog.sina.com.cn/s/blog_5e3ab00c0100le4s.html 1.首先假定鏈表不帶環(huán)
那么，我們只要判斷倆個(gè)鏈表的尾指針是否相等。 相等，則鏈表相交；否則，鏈表不相交。 2.如果鏈表帶環(huán)， 那判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。 如果在，則相交，如果不在，則不相交。 所以，事實(shí)上，這個(gè)問(wèn)題就轉(zhuǎn)化成了：
1.先判斷帶不帶環(huán) 2.如果都不帶環(huán)，就判斷尾節(jié)點(diǎn)是否相等 3.如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。 如果在，則相交，如果不在，則不相交。 //用兩個(gè)指針，一個(gè)指針步長(zhǎng)為1，一個(gè)指針步長(zhǎng)為2，判斷鏈表是否有環(huán)
bool check(const node* head) { if(head==NULL) return false; node *low=head, *fast=head->next; while(fast!=NULL && fast->next!=NULL) { low=low->next; fast=fast->next->next; if(low==fast) return true; } return false; } //如果鏈表可能有環(huán)，則如何判斷兩個(gè)鏈表是否相交
//思路：鏈表1 步長(zhǎng)為1，鏈表2步長(zhǎng)為2 ，如果有環(huán)且相交則肯定相遇，否則不相交 list1 head: p1 list2 head: p2 while( p1 != p2 && p1 != NULL && p2 != NULL ) [b]//但當(dāng)鏈表有環(huán)但不相交時(shí)，此處是死循環(huán)。![/b] { p1 = p1->next; if ( p2->next ) p2 = p2->next->next; else p2 = p2->next; } if ( p1 == p2 && p1 && p2) //相交 else //不相交 [color=#FF0000][b]所以，判斷帶環(huán)的鏈表，相不相交，只能這樣[/b]：[/color] 如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。 如果在，則相交，如果不在，則不相交。(未寫代碼實(shí)現(xiàn)，見(jiàn)諒。:).. ------------------ 第9題
----------------------------------- 判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果 題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。 如果是返回true，否則返回false。 例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果： 8 / \ 6 10 / \ / \ 5 7 9 11 因此返回true。 如果輸入7、4、6、5，沒(méi)有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。 //貌似，少有人關(guān)注此題。:).2010/10/18 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);
} 第9題：
其實(shí)，就是一個(gè)后序遍歷二叉樹的算法。 關(guān)鍵點(diǎn)： 1. //確定根結(jié)點(diǎn) int root = squence[length - 1]; 2.
// 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; } 3.
遞歸遍歷，左右子樹。 ---------------------------------------
//第10題，單詞翻轉(zhuǎn)。
//單詞翻轉(zhuǎn)，引用自117 樓 wocaoqwer 的回復(fù)。 #include<iostream> #include<string> using namespace std; class ReverseWords{
public: ReverseWords(string* wo):words(wo){} void reverse_() { int length=words->size(); int begin=-1,end=-1; for(int i=0;i<length;++i){ if(begin==-1&&words->at(i)==' ') continue; if(begin==-1) { begin=i; continue; } if(words->at(i)==' ') end=i-1; else if(i==length-1) end=i; else continue; reverse__(begin,end); //1.字母翻轉(zhuǎn) begin=-1,end=-1; } reverse__(0,length-1); //2.單詞翻轉(zhuǎn) } private:
void reverse__(int begin,int end) // { while(begin<end) { char t=words->at(begin); words->at(begin)=words->at(end); words->at(end)=t; ++begin; --end; } } string* words; }; int main(){ string s="I am a student."; ReverseWords r(&s); r.reverse_(); cout<<s<<endl; return 0; } 運(yùn)行結(jié)果：
student. a am I Press any key to continue 第11題 ------------------------------------ 求二叉樹中節(jié)點(diǎn)的最大距離... 如果我們把二叉樹看成一個(gè)圖，
父子節(jié)點(diǎn)之間的連線看成是雙向的， 我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。 寫一個(gè)程序， 求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。 //July 2010/10/19 //此題思路，tree_star and i 在257、258樓，講的很明白了。 //定義一個(gè)結(jié)構(gòu)體
struct NODE { NODE* pLeft; NODE* pRight; int MaxLen; int MaxRgt; }; NODE* pRoot; //根節(jié)點(diǎn) int MaxLength; void traversal_MaxLen(NODE* pRoot)
{ if(pRoot == NULL) { return 0; }; if(pRoot->pLeft == NULL) { pRoot->MaxLeft = 0; } else //若左子樹不為空 { int TempLen = 0; if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight) //左子樹上的，某一節(jié)點(diǎn)，往左邊大，還是往右邊大 { TempLen+=pRoot->pLeft->MaxLeft; } else { TempLen+=pRoot->pLeft->MaxRight; } pRoot->nMaxLeft = TempLen + 1; traversal_MaxLen(NODE* pRoot->pLeft); //此處，加上遞歸 } if(pRoot->pRigth == NULL) { pRoot->MaxRight = 0; } else //若右子樹不為空 { int TempLen = 0; if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight) //右子樹上的，某一節(jié)點(diǎn)，往左邊大，還是往右邊大 { TempLen+=pRoot->pRight->MaxLeft; } else { TempLen+=pRoot->pRight->MaxRight; } pRoot->MaxRight = TempLen + 1; traversal_MaxLen(NODE* pRoot->pRight); //此處，加上遞歸 } if(pRoot->MaxLeft + pRoot->MaxRight > 0) { MaxLength=pRoot->nMaxLeft + pRoot->MaxRight; } } // 數(shù)據(jù)結(jié)構(gòu)定義
struct NODE { NODE* pLeft; // 左子樹 NODE* pRight; // 右子樹 int nMaxLeft; // 左子樹中的最長(zhǎng)距離 int nMaxRight; // 右子樹中的最長(zhǎng)距離 char chValue; // 該節(jié)點(diǎn)的值 }; int nMaxLen = 0; // 尋找樹中最長(zhǎng)的兩段距離 void FindMaxLen(NODE* pRoot) { // 遍歷到葉子節(jié)點(diǎn)，返回 if(pRoot == NULL) { return; } // 如果左子樹為空，那么該節(jié)點(diǎn)的左邊最長(zhǎng)距離為0 if(pRoot -> pLeft == NULL) { pRoot -> nMaxLeft = 0; } // 如果右子樹為空，那么該節(jié)點(diǎn)的右邊最長(zhǎng)距離為0 if(pRoot -> pRight == NULL) { pRoot -> nMaxRight = 0; } // 如果左子樹不為空，遞歸尋找左子樹最長(zhǎng)距離 if(pRoot -> pLeft != NULL) { FindMaxLen(pRoot -> pLeft); } // 如果右子樹不為空，遞歸尋找右子樹最長(zhǎng)距離 if(pRoot -> pRight != NULL) { FindMaxLen(pRoot -> pRight); } // 計(jì)算左子樹最長(zhǎng)節(jié)點(diǎn)距離 if(pRoot -> pLeft != NULL) { int nTempMax = 0; if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) { nTempMax = pRoot -> pLeft -> nMaxLeft; } else { nTempMax = pRoot -> pLeft -> nMaxRight; } pRoot -> nMaxLeft = nTempMax + 1; } // 計(jì)算右子樹最長(zhǎng)節(jié)點(diǎn)距離 if(pRoot -> pRight != NULL) { int nTempMax = 0; if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) { nTempMax = pRoot -> pRight -> nMaxLeft; } else { nTempMax = pRoot -> pRight -> nMaxRight; } pRoot -> nMaxRight = nTempMax + 1; } // 更新最長(zhǎng)距離 if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) { nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight; } } //很明顯，思路完全一樣，但書上給的這段代碼更規(guī)范！:)。 第12題
題目：求1+2+…+n， 要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字 以及條件判斷語(yǔ)句（A?B:C）。 //July、2010/10/19 ----------------- 循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達(dá)到這個(gè)效果。 比如定義一個(gè)類，我們new一含有n個(gè)這種類型元素的數(shù)組， 那么該類的構(gòu)造函數(shù)將確定會(huì)被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。 ------------------ #include <iostream.h>
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]; //就是這個(gè)意思，new出n個(gè)數(shù)組。
delete []a; a = 0; return Temp::GetSum();
} int main()
{ cout<<solution1_Sum(100)<<endl; return 0; } //運(yùn)行結(jié)果：
//5050 //Press any key to continue //July、2010/10/19 //第二種思路：
---------------- 既然不能判斷是不是應(yīng)該終止遞歸，我們不妨定義兩個(gè)函數(shù)。 一個(gè)函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個(gè)函數(shù)處理終止遞歸的情況， 我們需要做的就是在兩個(gè)函數(shù)里二選一。 從二選一我們很自然的想到布爾變量，
比如ture/(1)的時(shí)候調(diào)用第一個(gè)函數(shù)，false/(0)的時(shí)候調(diào)用第二個(gè)函數(shù)。 那現(xiàn)在的問(wèn)題是如和把數(shù)值變量n轉(zhuǎn)換成布爾值。 如果對(duì)n連續(xù)做兩次反運(yùn)算，即!!n，那么非零的n轉(zhuǎn)換為true，0轉(zhuǎn)換為false。 #include <iostream.h>
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); //利用虛函數(shù)的特性，當(dāng)Array[1]為0時(shí)，即Array[0] = &a; 執(zhí)行A::Sum， //當(dāng)Array[1]不為0時(shí)， 即Array[1] = &b; 執(zhí)行B::Sum。 return value;
} int main()
{ cout<<solution2_Sum(100)<<endl; return 0; } //5050
//Press any key to continue 第13題：
題目： 輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn), 鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。 //此題一出，相信，稍微有點(diǎn) 經(jīng)驗(yàn)的同志，都會(huì)說(shuō)到：
------------------------ 設(shè)置兩個(gè)指針p1,p2 首先p1和p2都指向head 然后p2向前走n步，這樣p1和p2之間就間隔k個(gè)節(jié)點(diǎn) 然后p1和p2同…… #include <iostream.h>
#include <stdio.h> #include <stdlib.h> struct ListNode
{ char data; ListNode* next; }; ListNode* head,*p,*q; ListNode *pone,*ptwo; ListNode* fun(ListNode *head,int k)
{ pone = ptwo = head; for(int i=0;i<=k-1;i++) ptwo=ptwo->next; while(ptwo!=NULL) { pone=pone->next; ptwo=ptwo->next; } return pone; } int main()
{ char c; head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; p = head; while(c !='0') { q = (ListNode*)malloc(sizeof(ListNode)); q->data = c; q->next = NULL; p->next = q; p = p->next; c = getchar(); } cout<<"---------------"<<endl; cout<<fun(head,2)->data<<endl; return 0;
} /////////////////////////////
1254863210 --------------- 2 Press any key to continue //////////////////////////// 第14題：
題目：輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字， 在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。 要求時(shí)間復(fù)雜度是O(n)。 如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。 例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。 //由于數(shù)組已經(jīng)過(guò)升序排列，所以，難度下降了不少。 //July、2010/10/19 #include <iostream.h> bool FindTwoNumbersWithSum
( int data[], // 已經(jīng)排序的 數(shù)組 unsigned int length, // 數(shù)組長(zhǎng)度 int sum, //用戶輸入的 sum int& num1, // 輸出符合和等于sum的第一個(gè)數(shù) int& num2 // 第二個(gè)數(shù) ) { bool found = false; if(length < 1) return found; int begin = 0; int end = length - 1; while(end > begin) { long curSum = data[begin] + data[end]; if(curSum == sum) { num1 = data[begin]; num2 = data[end]; found = true; break; } else if(curSum > sum) end--; else begin++; } return found; } int main() { int x,y; int a[6]={1,2,4,7,11,15}; if(FindTwoNumbersWithSum(a,6,15,x,y) ) { cout<<x<<endl<<y<<endl; } return 0; } 4 11 Press any key to continue //擴(kuò)展：如果輸入的數(shù)組是沒(méi)有排序的，但知道里面數(shù)字的范圍，其他條件不變，
//如何在O(n)時(shí)間里找到這兩個(gè)數(shù)字？ 關(guān)于第14題， 1.題目假定是，只要找出倆個(gè)數(shù)，的和等于給定的數(shù)， 其實(shí)是，當(dāng)給定一排數(shù)， 4,5,7,10,12 然后給定一個(gè)數(shù)，22。 就有倆種可能了。因?yàn)?2=10+12=10+5+7。 而恰恰與第4題，有關(guān)聯(lián)了。望大家繼續(xù)思考下。:)。 2.第14題，還有一種思路，如下倆個(gè)數(shù)組：
1、 2、 4、7、11、15 //用15減一下為 14、13、11、8、4、 0 //如果下面出現(xiàn)了和上面一樣的數(shù)，稍加判斷，就能找出這倆個(gè)數(shù)來(lái)了。 第一個(gè)數(shù)組向右掃描，第二個(gè)數(shù)組向左掃描。
第15題： 題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像， 即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。 用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。 例如輸入： 8 / \ 6 10 / \ / \ 5 7 9 11 輸出：
8 / \ 10 6 / \ / \ 11 9 7 5 定義二元查找樹的結(jié)點(diǎn)為：
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 }; //就是遞歸翻轉(zhuǎn)樹，有子樹則遞歸翻轉(zhuǎn)子樹。 //July、2010/10/19 void Revertsetree(list *root)
{ if(!root) return; list *p; p=root->leftch;
root->leftch=root->rightch; root->rightch=p; if(root->leftch)
Revertsetree(root->leftch); if(root->rightch) Revertsetree(root->rightch); } 由于遞歸的本質(zhì)是編譯器生成了一個(gè)函數(shù)調(diào)用的棧，
因此用循環(huán)來(lái)完成同樣任務(wù)時(shí)最簡(jiǎn)單的辦法就是用一個(gè)輔助棧來(lái)模擬遞歸。 首先我們把樹的頭結(jié)點(diǎn)放入棧中。
在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹。 如果它有左子樹，把它的左子樹壓入棧中；
如果它有右子樹，把它的右子樹壓入棧中。 這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹了。
//再用輔助棧模擬遞歸，改成循環(huán)的（有誤之處，望不吝指正）： void Revertsetree(list *phead)
{ if(!phead) return; stack<list*> stacklist;
stacklist.push(phead); //首先把樹的頭結(jié)點(diǎn)放入棧中。 while(stacklist.size())
//在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹 { list* pnode=stacklist.top(); stacklist.pop(); list *ptemp; ptemp=pnode->leftch; pnode->leftch=pnode->rightch; pnode->rightch=ptemp; if(pnode->leftch)
stacklist.push(pnode->leftch); //若有左子樹，把它的左子樹壓入棧中 if(pnode->rightch) stacklist.push(pnode->rightch); //若有右子樹，把它的右子樹壓入棧中 } } 第16題 題目：輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。 例如輸入 8
/ \ 6 10 /\ /\ 5 7 9 11 輸出8 6 10 5 7 9 11。
//題目不是我們所熟悉的，樹的前序，中序，后序。即是樹的層次遍歷。 /*308 樓 panda_lin 的回復(fù)，說(shuō)的已經(jīng)很好了。:)
利用隊(duì)列,每個(gè)單元對(duì)應(yīng)二叉樹的一個(gè)節(jié)點(diǎn). 1：輸出8， 隊(duì)列內(nèi)容: 6, 10 2：輸出6, 6的2個(gè)子節(jié)點(diǎn)5,7入隊(duì)列。隊(duì)列的內(nèi)容：10， 5， 7 3：輸出10，10的2個(gè)子節(jié)點(diǎn)9，11入隊(duì)列。隊(duì)列的內(nèi)容：5，7，9，11。 4：輸出5 ，5沒(méi)有子節(jié)點(diǎn)。隊(duì)列的內(nèi)容：7，9，11 5：。。。 由于STL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的deque（兩端都可以進(jìn)出的隊(duì)列），
我們只需要拿過(guò)來(lái)用就可以了。 我們知道樹是圖的一種特殊退化形式。 同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解， 將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。
因此這道題的本質(zhì)是在二元樹上實(shí)現(xiàn)廣度優(yōu)先遍歷。 //July、2010/10/19/晚。 #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 }; BTreeNode* pListIndex; BTreeNode* pHead; 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); } } // 創(chuàng)建二元查找樹
void addBTreeNode(BTreeNode * & pCurrent, int value) { if (NULL == pCurrent) { BTreeNode * pBTree = new BTreeNode(); pBTree->m_pLeft = NULL; pBTree->m_pRight = NULL; pBTree->m_nValue = value; pCurrent = pBTree; }
else { if ((pCurrent->m_nValue) > value) { addBTreeNode(pCurrent->m_pLeft, value); } else if ((pCurrent->m_nValue) < value) { addBTreeNode(pCurrent->m_pRight, value); } } } int main()
{ BTreeNode * pRoot = NULL; pListIndex = NULL; pHead = NULL; addBTreeNode(pRoot, 8); addBTreeNode(pRoot, 6); addBTreeNode(pRoot, 5); addBTreeNode(pRoot, 7); addBTreeNode(pRoot, 10); addBTreeNode(pRoot, 9); addBTreeNode(pRoot, 11); PrintFromTopToBottom(pRoot); return 0; } //輸出結(jié)果：
//8 6 10 5 7 9 11 Press any key to continue 是的，由這道題，突然想到了，樹的廣度優(yōu)先遍歷，BFS算法，
算法王帖：精選經(jīng)典的24個(gè)算法 [3.BFS和DFS優(yōu)先搜索] http://blog.sina.com.cn/s/blog_5e3ab00c0100lya2.html 第17題：
題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。 如輸入abaccdeff，則輸出b。 這道題是2006年google的一道筆試題。 思路剖析：由于題目與字符出現(xiàn)的次數(shù)相關(guān)，我們可以統(tǒng)計(jì)每個(gè)字符在該字符串中出現(xiàn)的次數(shù). 要達(dá)到這個(gè)目的，需要一個(gè)數(shù)據(jù)容器來(lái)存放每個(gè)字符的出現(xiàn)次數(shù)。 在這個(gè)數(shù)據(jù)容器中可以根據(jù)字符來(lái)查找它出現(xiàn)的次數(shù)，
也就是說(shuō)這個(gè)容器的作用是把一個(gè)字符映射成一個(gè)數(shù)字。 在常用的數(shù)據(jù)容器中，哈希表正是這個(gè)用途。
由于本題的特殊性，我們只需要一個(gè)非常簡(jiǎn)單的哈希表就能滿足要求。 由于字符（char)是一個(gè)長(zhǎng)度為8的數(shù)據(jù)類型，因此總共有可能256 種可能。
于是我們創(chuàng)建一個(gè)長(zhǎng)度為256的數(shù)組，每個(gè)字母根據(jù)其ASCII碼值作為數(shù)組的下標(biāo)對(duì)應(yīng)數(shù)組的對(duì)應(yīng)項(xiàng)， 而數(shù)組中存儲(chǔ)的是每個(gè)字符對(duì)應(yīng)的次數(shù)。 這樣我們就創(chuàng)建了一個(gè)大小為256，以字符ASCII碼為鍵值的哈希表。
我們第一遍掃描這個(gè)數(shù)組時(shí)，每碰到一個(gè)字符，在哈希表中找到對(duì)應(yīng)的項(xiàng)并把出現(xiàn)的次數(shù)增加一次。 這樣在進(jìn)行第二次掃描時(shí)，就能直接從哈希表中得到每個(gè)字符出現(xiàn)的次數(shù)了。 //July、2010/10/20 #include <iostream.h>
#include <string.h> char FirstNotRepeatingChar(char* pString) { if(!pString) return 0; const int tableSize = 256;
unsigned int hashTable[tableSize]; for(unsigned int i = 0; i < tableSize; ++ i) hashTable[i] = 0; char* pHashKey = pString;
while(*(pHashKey) != '\0') hashTable[*(pHashKey++)] ++; pHashKey = pString;
while(*pHashKey != '\0') { if(hashTable[*pHashKey] == 1) return *pHashKey; pHashKey++;
} return *pHashKey;
} int main()
{ cout<<"請(qǐng)輸入一串字符："<<endl; char s[100]; cin>>s; char* ps=s; cout<<FirstNotRepeatingChar(ps)<<endl; return 0; } ////////////////////////////////////////// 請(qǐng)輸入一串字符： abaccdeff b Press any key to continue /////////////////////////////////////////// 第18題：
題目：n個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0開始， 每次從這個(gè)圓圈中刪除第m個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)字）。 當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第m個(gè)數(shù)字。 求出在這個(gè)圓圈中剩下的最后一個(gè)數(shù)字。 July：我想，這個(gè)題目，不少人已經(jīng) 見(jiàn)識(shí)過(guò)了。 先看這個(gè)題目的簡(jiǎn)單變形。
n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)）， 凡報(bào)到3的人退出圈子，問(wèn)最后留下的是原來(lái)第幾號(hào)的那個(gè)人? --------------------------------------------------------- //July、2010/10/20 //我把這100題，當(dāng)每日必須完成的作業(yè)，來(lái)做了。:）。 #include <stdio.h> int main()
{ int i,k,m,n,num[50],*p; printf("input number of person:n="); scanf("%d",&n); printf("input number of the quit:m="); //留下->18題
scanf("%d",&m); //留下->18題 p=num;
for(i=0;i<n;i++) *(p+i)=i+1; //給每個(gè)人編號(hào) i=0; //報(bào)數(shù) k=0; //此處為3 // m=0; //m為退出人數(shù) //去掉->18題 while(m<n-1) { if(*(p+i)!=0) k++; if(k==3) { *(p+i)=0; //退出，對(duì)應(yīng)的數(shù)組元素置為0 k=0; m++; } i++; if(i==n) i=0; } while(*p==0) p++; printf("The last one is NO.%d\n",*p); } //////////////////////////////////////
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;
} //////////////////////////////////////////// 第19題：
題目：定義Fibonacci數(shù)列如下： / 0 n=0 f(n)= 1 n=1,2 \ f(n-1)+f(n-2) n>2 輸入n，用最快的方法求該數(shù)列的第n項(xiàng)。
分析：在很多C語(yǔ)言教科書中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fibonacci作為例子。 因此很多程序員對(duì)這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。 //0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597.......... //注意，當(dāng)求第100項(xiàng)，甚至更大的項(xiàng)時(shí)，請(qǐng)確保你用什么類型，長(zhǎng)整型?or long long int存儲(chǔ)。 //不然，計(jì)算機(jī)，將 得不到結(jié)果。 //若用遞歸方法，可寫 下如下代碼：
#include <iostream.h> int Fibona(int n)
{ int m; if(n==0) return 0; else if(n==1||n==2) return 1; else { m=Fibona(n-1)+Fibona(n-2); return m; } } int main()
{ cout<<"-----------------"<<endl; cout<<Fibona(17)<<endl; return 0; } ---------------------------
科書上反復(fù)用這個(gè)題目來(lái)講解遞歸函數(shù)，并不能說(shuō)明遞歸解法最適合這道題目。 我們以求解f(10)作為例子來(lái)分析遞歸求解的過(guò)程。 要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和f(7)…… 我們用樹形結(jié)構(gòu)來(lái)表示這種依賴關(guān)系 f(10) / \ f(9) f(8) / \ / \ f(8) f(7) f(6) f(5) / \ / \ f(7) f(6) f(6) f(5) 更簡(jiǎn)單的辦法是從下往上計(jì)算，首先根據(jù)f(0)和f(1)算出f(2)，再根據(jù)f(1)和f(2)算出f(3)……
依此類推就可以算出第n項(xiàng)了。很容易理解，這種思路的時(shí)間復(fù)雜度是O(n)。 其實(shí)，就是轉(zhuǎn)化為非遞歸程序，用遞推。!
------------------------------------------ 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;
} //很可惜，這還不是最快的方法。 //還有一種方法，可達(dá)到，時(shí)間復(fù)雜度為O(lgn). //............ 第20題：
題目：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。 例如輸入字符串"345"，則輸出整數(shù)345。 ----------------------------- 此題一點(diǎn)也不簡(jiǎn)單。不信，你就先不看一下的代碼， 你自己先寫一份，然后再對(duì)比一下，便知道了。 1.轉(zhuǎn)換的思路：每掃描到一個(gè)字符，我們把在之前得到的數(shù)字乘以10再加上當(dāng)前字符表示的數(shù)字。
這個(gè)思路用循環(huán)不難實(shí)現(xiàn)。 2.由于整數(shù)可能不僅僅之含有數(shù)字，還有可能以'+'或者'-'開頭，表示整數(shù)的正負(fù)。 如果第一個(gè)字符是'+'號(hào)，則不需要做任何操作；如果第一個(gè)字符是'-'號(hào)， 則表明這個(gè)整數(shù)是個(gè)負(fù)數(shù)，在最后的時(shí)候我們要把得到的數(shù)值變成負(fù)數(shù)。 3.接著我們?cè)囍幚矸欠ㄝ斎?。由于輸入的是指針，在使用指針之前?br>我們要做的第一件是判斷這個(gè)指針是不是為空。 如果試著去訪問(wèn)空指針，將不可避免地導(dǎo)致程序崩潰。 4.輸入的字符串中可能含有不是數(shù)字的字符。 每當(dāng)碰到這些非法的字符，我們就沒(méi)有必要再繼續(xù)轉(zhuǎn)換。 最后一個(gè)需要考慮的問(wèn)題是溢出問(wèn)題。由于輸入的數(shù)字是以字符串的形式輸入， 因此有可能輸入一個(gè)很大的數(shù)字轉(zhuǎn)換之后會(huì)超過(guò)能夠表示的最大的整數(shù)而溢出。 //July、2010、10/22。
enum Status {kValid = 0, kInvalid}; int g_nStatus = kValid; 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); } //在C語(yǔ)言提供的庫(kù)函數(shù)中，函數(shù)atoi能夠把字符串轉(zhuǎn)換整數(shù)。 //它的聲明是int atoi(const char *str)。該函數(shù)就是用一個(gè)全局變量來(lái)標(biāo)志輸入是否合法的。 其中，部分題目源碼及思路，參考自：
本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/v_JULY_v/archive/2010/11/05/5990750.aspx |
|
|
來(lái)自： qinjie2010 > 《我的圖書館》
