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

微软等数据结构++++算法面试100100100100题全部答案集锦作者：July、阿财。时间：二零一一年十月十三日。引言无私分享造就开源的辉煌。今是二零一一年十月十三日，明日14日即是本人刚好开博一周年。在一周年之际，特此分享出微软面试全部100题答案的完整版，以作为对本博客所有读者的回馈。一年之前的10月14日，一个名叫July的人在一个叫csdn的论坛上开帖分享微软等公司数据结构+算法面试100题，自此，与上千网友一起做，一起思考，一起解答这些面试题目，最终成就了一个名为：结构之法算法之道的编程面试与算法研究并重的博客，如今，此博客影响力逐步渗透到海外，及至到整个互联网。在此之前，由于本人笨拙，这微软面试100题的答案只整理到了前60题（第1-60题答案可到本人资源下载处下载：://v_july_v.download.csdn.net/://v_july_v.download.csdn.net/），故此，常有朋友留言或来信询问后面40题的答案。只是因个人认为：一、答案只是作为一个参考，不可太过依赖；二、常常因一些事情耽搁（如在整理最新的今年九月、十月份的面试题：九月腾讯，创新工场，淘宝等公司最新面试十三题、十月百度，阿里巴巴，迅雷搜狗最新面试十一题）；三、个人正在针对那100题一题一题的写文章，多种思路，不断优化，即成程序员编程艺术系列。自此，后面40题的答案迟迟未得整理。且个人已经整理的前60题的答案，在我看来，是有诸多问题与弊端的，甚至很多答案都是错误的。互联网总是能给人带来惊喜。前几日，一位现居美国加州的名叫阿财的朋友发来一封邮件，并把他自己做的全部100题的答案一并发予给我，自此，便似遇见了知己。十分感谢。任何东西只有分享出来才更显其价值。本只需贴出后面40题的答案，因为前60题的答案本人早已整理上传至网上，但多一种思路多一种参考亦未尝不可。特此，把阿财的答案再稍加整理番，然后把全部100题的答案现今都贴出来。若有任何问题，欢迎不吝指正。谢谢。上千上万的人都关注过此100题，且大都都各自贡献了自己的思路，或回复于微软100100100100题维护地址上，或回复于本博客内，人数众多，无法一一标明，特此向他们诸位表示敬意和感谢。谢谢大家，诸君的努力足以影响整个互联网，咱们已经迎来一个分享互利的新时代。微软面试100100100100题全部答案最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过。且因尊重阿财，未作过多修改。因此，有些答案是有问题的，重点还可关注本人的程序员编程艺术系列，亦可参考个人之前整理的前60题的答案：第1题-20题答案：，第21-40题答案：，第41-60题答案：）：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