答案V0.2版]精选微软数据结构+算法面试100题[前20题]

1精选微软等数据结构精选微软等数据结构精选微软等数据结构精选微软等数据结构++++算法面试算法面试算法面试算法面试100100100100题题题题--------答案修正答案修正答案修正答案修正V0.2V0.2V0.2V0.2版本版本版本版本此份答案是针对，前期已公布的最初的那份答案的，初步校正与修正。（V0.1版）相比第一份V0.1版答案，此份答案V0.2版更加准确，亦修正了不少题目的答案。此份20题的答案，思路更加清晰易懂，简介明了。帖子更新地址：若对已公布的面试题有任何问题，请把意见发表在上述帖子上，探讨交流。所有源码及答案，只做了初步校正，欢迎批评指正。MyBlog：：：[e-mail]//东华理工、July整理编辑。2010/11/06。谢谢。-------我很享受思考的过程，个人思考的全部结果，都放在了这篇帖子上，现在，我要，好好整理下，上篇帖子上，已公布出来的题目答案了。展示自己的思考结果，我觉得很骄傲。:)。----------------------------------------------------------22010年10月18日下午July--------------------------------1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};//引用245楼tree_star的回复#includestdio.h#includeiostream.hstructBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};typedefBSTreeNodeDoubleList;DoubleList*pHead;DoubleList*pListIndex;voidconvertToDoubleList(BSTreeNode*pCurrent);//创建二元查找树voidaddBSTreeNode(BSTreeNode*&pCurrent,intvalue){if(NULL==pCurrent){BSTreeNode*pBSTree=newBSTreeNode();3pBSTree-m_pLeft=NULL;pBSTree-m_pRight=NULL;pBSTree-m_nValue=value;pCurrent=pBSTree;}else{if((pCurrent-m_nValue)value){addBSTreeNode(pCurrent-m_pLeft,value);}elseif((pCurrent-m_nValue)value){addBSTreeNode(pCurrent-m_pRight,value);}else{//cout重复加入节点endl;}}}//遍历二元查找树中序voidergodicBSTree(BSTreeNode*pCurrent){if(NULL==pCurrent){return;}if(NULL!=pCurrent-m_pLeft){ergodicBSTree(pCurrent-m_pLeft);}//节点接到链表尾部convertToDoubleList(pCurrent);//右子树为空if(NULL!=pCurrent-m_pRight){ergodicBSTree(pCurrent-m_pRight);}}4//二叉树转换成listvoidconvertToDoubleList(BSTreeNode*pCurrent){pCurrent-m_pLeft=pListIndex;if(NULL!=pListIndex){pListIndex-m_pRight=pCurrent;}else{pHead=pCurrent;}pListIndex=pCurrent;coutpCurrent-m_nValueendl;}intmain(){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);return0;}///////////////////////////////////////////////4681012141516Pressanykeytocontinue//////////////////////////////////////////////52.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。结合链表一起做。首先我做插入以下数字：10，7，3，3，8，5，2，60:10-NULL(MIN=10,POS=0)1:7-[0](MIN=7,POS=1)用数组表示堆栈，第0个元素表示栈底2:3-[1](MIN=3,POS=2)3:3-[2](MIN=3,POS=3)4:8-NULL(MIN=3,POS=3)技巧在这里，因为8比当前的MIN大，所以弹出8不会对当前的MIN产生影响5：5-NULL(MIN=3,POS=3)6:2-[2](MIN=2,POS=6)如果2出栈了，那么3就是MIN7:6-[6]出栈的话采用类似方法修正。所以，此题的第1小题，即是借助辅助栈，保存最小值，且随时更新辅助栈中的元素。如先后，push26415stackAstackB（辅助栈）4:51//push5,min=p-[3]=1^3:11//push1,min=p-[3]=1|//此刻push进A的元素1小于B中栈顶元素22:42//push4,min=p-[0]=2|1:62//push6,min=p-[0]=2|0:22//push2,min=p-[0]=2|push第一个元素进A，也把它push进B，当向Apush的元素比B中的元素小，则也push进B，即更新B。否则，不动B，保存原值。向栈Apush元素时，顺序由下至上。辅助栈B中，始终保存着最小的元素。6然后，pop栈A中元素，51462AB-更新4:511//pop5,min=p-[3]=1|3:112//pop1,min=p-[0]=2|2:422//pop4,min=p-[0]=2|1:622//pop6,min=p-[0]=2|0:22NULL//pop2,min=NULLv当popA中的元素小于B中栈顶元素时，则也要popB中栈顶元素。3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。//July2010/10/18#includeiostream.hintmaxSum(int*a,intn){intsum=0;intb=0;for(inti=0;in;i++){if(b0)b=a[i];elseb+=a[i];if(sumb)sum=b;}7returnsum;}intmain(){inta[10]={1,-8,6,3,-1,5,7,-2,0,1};coutmaxSum(a,10)endl;return0;}运行结果，如下：20Pressanykeytocontinue------------------------------------------------------------intmaxSum(int*a,intn){intsum=0;intb=0;for(inti=0;in;i++){if(b=0)//此处修正下，把b0改为b=0b=a[i];elseb+=a[i];if(sumb)sum=b;}returnsum;}//////////////////////////////////////////////解释下：例如输入的数组为1,-2,3,10,-4,7,2,-5，那么最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18所有的东西都在以下俩行，即：8b：01-1313916187sum：01131313161818其实算法很简单，当前面的几个数，加起来后，b0后，把b重新赋值，置为下一个元素，b=a[i]。当bsum，则更新sum=b;若bsum，则sum保持原值，不更新。:)。July、10/31。///////////////////////////////////////////////关于此第3题，有网友提出，说以上的解答，没有给出如果数组中全部为负数的情况，的解决方案。的确，我一直把，题目限定了是既有负数也有正数的，不考虑全部为负数的情况。当然，若考虑如果数组，全部为负数，解决方案如下（网友给出的答案，未作测试）：intmaxSum(int*a,intn){intsum=0;intb=0;//针对数组全部为负数的判断。intnTemp=a[0];for(intj=1;jn;j++){if(nTempa[j])nTemp=a[j];}if(nTemp0)returnnTemp;for(inti=0;in;i++){if(b0)b=a[i];elseb+=a[i];if(sumb)sum=b;9}returnsum;}voidmain(){//inta[]={1,2,3,10,4,7,2,5};//inta[]={1,-2,3,10,-4,7,2,-5};//inta[]={-1,-2,-3,-10,-4,-7,-2,-5};printf(\n%d\n,maxSum(a,8));getchar();}//关于第4题，当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父