微软等数据结构+算法面试100题全部答案

本文转载自CSDN大牛的一篇博客：作者：July、阿财时间：二零一一年十月十三日。我能够看到此文，还要多谢陈同学！让我得以及时分享给大家引言无私分享造就开源的辉煌。今是二零一一年十月十三日，明日14日即是本人刚好开博一周年。在一周年之际，特此分享出微软面试全部100题答案的完整版，以作为对读者的回馈。一年之前的10月14日，一个名叫July的人在一个叫csdn的论坛上开帖分享微软等公司数据结构+算法面试100题，自此，与上千网友一起思考，解答这些面试题目，最终成就了一个名为：结构之法算法之道的面试编程与算法研究并重的博客，如今，此博客影响力逐步渗透到海外，及至到整个互联网。在此之前，由于本人笨拙，这微软面试100题的答案只整理到了前60题，故此，常有朋友留言或来信询问后面40题的答案。只是因个人认为：一、答案只是作为一个参考，不可太过依赖；二、常常因一些事情耽搁。自此，后面40题的答案迟迟未得整理。且个人已经整理的前60题的答案，在我看来，是有诸多问题与弊端的，甚至很多答案都是错误的。互联网总是能带来惊喜。前几日，一位现局美国加州的名叫阿财的朋友发来一封邮件，并把他自己做的全部100题的答案一并发予给我，自此，便似遇见了知己。十分感谢。话不絮烦。本只需贴出后面40题的答案，因为前60题的答案本人早已整理上传至网上，但多一种思路多一种参考亦未尝不可。把阿财的答案再稍加整理番，特此，全部100题的答案现今都贴出来。有任何问题，欢迎不吝指正。谢谢。上千上万的人都关注过此100题，且大都都各自贡献了自己的思路，或回复于微软100题的维护帖子上，或回复于本博客内，人数众多，无法一一标明，特此向他们诸位表示敬意和感谢。谢谢大家，诸君的努力足以影响整个互联网，咱们已经迎来一个分享互利的新时代。微软面试100题全部答案个人整理的前60题的答案可参见以下三篇文章：1.微软100题第1题-20题答案[博文I]2.微软100题第21-40题答案[博文II]3.微软100题第41-60题答案[博文III]最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）：1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};ANSWER:Thisisatraditionalproblemthatcanbesolvedusingrecursion.Foreachnode,connectthedoublelinkedlistscreatedfromleftandrightchildnodetoformafulllist./***@paramrootTherootnodeofthetree*@returnTheheadnodeoftheconvertedlist.*/BSTreeNode*treeToLinkedList(BSTreeNode*root){BSTreeNode*head,*tail;helper(head,tail,root);returnhead;}voidhelper(BSTreeNode*&head,BSTreeNode*&tail,BSTreeNode*root){BSTreeNode*lt,*rh;if(root==NULL){head=NULL,tail=NULL;return;}helper(head,lt,root-m_pLeft);helper(rh,tail,root-m_pRight);if(lt!=NULL){lt-m_pRight=root;root-m_pLeft=lt;}else{head=root;}if(rh!=NULL){root-m_pRight=rh;rh-m_pLeft=root;}else{tail=root;}}2.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。ANSWER:StackisaLIFOdatastructure.Whensomeelementispoppedfromthestack,thestatuswillrecovertotheoriginalstatusasbeforethatelementwaspushed.Sowecanrecovertheminimumelement,too.structMinStackElement{intdata;intmin;};structMinStack{MinStackElement*data;intsize;inttop;}MinStackMinStackInit(intmaxSize){MinStackstack;stack.size=maxSize;stack.data=(MinStackElement*)malloc(sizeof(MinStackElement)*maxSize);stack.top=0;returnstack;}voidMinStackFree(MinStackstack){free(stack.data);}voidMinStackPush(MinStackstack,intd){if(stack.top==stack.size)error(“outofstackspace.”);MinStackElement*p=stack.data[stack.top];p-data=d;p-min=(stack.top==0?d:stack.data[top-1]);if(p-mind)p-min=d;top++;}intMinStackPop(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[--stack.top].data;}intMinStackMin(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[stack.top-1].min;}3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。ANSWER:Atraditionalgreedyapproach.Keepcurrentsum,slidefromlefttoright,whensum0,resetsumto0.intmaxSubarray(inta[],intsize){if(size=0)error(“errorarraysize”);intsum=0;intmax=-(131);intcur=0;while(cursize){sum+=a[cur++];if(summax){max=sum;}elseif(sum0){sum=0;}}returnmax;}4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/\512/\47则打印出两条路径：10,12和10,5,7。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};ANSWER:Usebacktrackingandrecurison.Weneedastacktohelpbacktrackingthepath.structTreeNode{intdata;TreeNode*left;TreeNode*right;};voidprintPaths(TreeNode*root,intsum){intpath[MAX_HEIGHT];helper(root,sum,path,0);}voidhelper(TreeNode*root,intsum,intpath[],inttop){path[top++]=root.data;sum-=root.data;if(root-left==NULL&&root-right==NULL){if(sum==0)printPath(path,top);}else{if(root-left!=NULL)helper(root-left,sum,path,top);if(root-right!=NULL)helper(root-right,sum,path,top);}top--;sum-=root.data;}5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。ANSWER:Thisisaverytraditionalquestion...O(nlogn):catI_FILE|sort-n|head-nKO(kn):doinsertionsortuntilkelementsareretrieved.O(n+klogn):TakeO(n)timetobottom-upbuildamin-heap.Thensift-downk-1times.SotraditionalthatIdon‟twanttowritethecodes...Onlygivesthesiftupandsiftdownfunction./***@paramitheindexoftheelementinheapa[0...n-1]tobesiftedupvoidsiftup(inta[],inti,intn){while(i0){intj=(i&1==0?i-1:i+1);intp=(i-1)1;if(jn&&a[j]a[i])i=j;if(a[i]a[p])swap(a,i,p);i=p;}}voidsiftdown(inta[],inti,intn){while(2*i+1n){intl=2*i+1;if(l+1n&&a[l+1]a[l])l++;if(a[l]a[i])swap(a,i,l);i=l;}}第6题腾讯面试题：给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0，1，2，3，4，5，6，7，8，9】举一个例子，数值:0,1,2,3,4,5,6,7,8,9分配:6,2,