微软等数据结构+算法面试100题系列之网友精彩回复[二]
作者:Julymimo9527
完整100题，请参见，[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
以下所有的思路、答案选自网友mimo9527和我个人在这帖子上的回复：
========
为了表示对mimo9527的尊重，我尽量不对他的回复做修改与改动。
且尽量只贴思路，少或不贴代码。文末附上我个人对部分题、简单的思路回复。
欢迎，各位，毫不犹豫的，对以下的思路、或解法提出质疑、批评、指正。谢谢。
---------------------------------
mimo9527：
第8题此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题1.非常有名的老题2。7=1+2+4
3。★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗★不用乘法或加法增加8倍。现在用同样的方法增加7倍。
-----------------------------------重复的那个数字=数组之和-500500（1到1000之和）8倍：左移3位7倍：8倍-1倍
第10题翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“Iamastudent.”，则输出“student.aamI”。
-----------------------分析：可以利用堆栈后进先出的特性，把输入先push到堆栈中，然后再pop出来，即反序。
第12题题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（AB:C）
-----------------------------------分析：主要是能周期性的执行某一语句就可以了；如启动一个周期性定时器之类的，每次超时调用一次；只是还没找到合适的定时器函数；。。。。。。。。。
34.实现一个队列。队列的应用场景为：一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列。
生产者消费者问题答案代码，有几个问题，
1。是生产和消费线程没有做互斥，如队列就是一个共享资源，需要互斥使用。2。sleep没有必要。3。WaitForMultipleObjects(2,handles,TRUE,INFINITE);应该没有用吧？
这位哥们，指的是我之前上传的资源，答案V0.3版关于第34题的答案。
47.创新工场：求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
-------------分析：相当于寻找和“9876543210”的公共子串，可以使用《算法导论》中的“最长公共子序列算法”。-------------前面没考虑数字大于10的情况，数字大于10的时候，不能直接作为字符串处理，而应该作为一个数组序列，需要对程序做一点调整。
56.最长公共字串。题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。分析：求最长公共子串（LongestCommonSubsequence,LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。
-----------与上楼相同，两个字符串BDCABA和ABCBDAB都是《算法导论》例子里面的。。。。
voidLongestCommonSubsequence(){characStringX[]="abractyeyt";characStringY[]="dgdsaeactyey";characStringTemp[MAX_STRING_LEN];
intiStringXLen=strlen(acStringX);intiStringYLen=strlen(acStringY);intiStringTempLen;if(iStringXLen>=MAX_STRING_LEN-1||iStringXLen>=MAX_STRING_LEN-1){printf("stringistoolong!/n");return;}
memset(gaiComSubseqLen,0,MAX_STRING_LEN*MAX_STRING_LEN*sizeof(int));
LCS_Length(acStringX,acStringY);LSC_Print(acStringX,iStringXLen,iStringYLen);printf("/n");
return;}--------------------------
-----------------------分析：pToBeDeleted为尾节点或唯一节点时，比较简单；否则，因为是单向链表，找不到pToBeDeleted的上一个节点，故删除比较麻烦，所以可以将pToBeDeleted的下一个节点的内容复制到pToBeDeleted中，然后把pToBeDeleted的下一个节点删除。
64.寻找丑数。题目：我们把只包含因子2、3和5的数称作丑数（UglyNumber）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
-----------------------分析：丑数=2^i*3^j*5^k（^表示多少次方），通过变换i,j,k的取值来计算；但是我没有找到i,j,k如何取值的规律，只能不停的判断谁大谁小了。
65.输出1到最大的N位数题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，则输出1、2、3一直到最大的3位数即999。分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。
-----------------循环长度为10的n次方，在循环之前把这个长度计算出来，别在循环里计算；除此之外愣是没看出来有什么玄机，等待看别人的解答。
66.颠倒栈。题目：用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。颠倒之后的栈为{5,4,3,2,1}，5处在栈顶。
---------------------分析：这个简单，递归时把取出来的存在一个全局的数组里，然后根据要求再push回去；pop（）；存储；判断是否是最后一个：是：push（数组中最后一个，并在数组中删掉）；否：递归；push（数组中最后一个，并在数组中删掉）；
71.数值的整数次方。题目：实现函数doublePower(doublebase,intexponent)，求base的exponent次方。不需要考虑溢出。
-------------------------------分析：为了提高效率，考虑采用分治的思想：1.对exponent进行分解，如分解为2的i,j,k次方的和，然后对每一个递归计算；2.1中还有重复计算，可以增加一些处理，提高效率。
----------------------------------分析：1.出现次数大于数组长度N的一半的数字，一定在数组中的前一半中至少出现一次；2.先遍历数组的开始一半（注：如果N为奇数，则前一半多放一个），得到出现的每一个数及其出现次数的列表List；3.开始遍历数组的后一半FORJ=N/2;J<=N;J++：3.1如果是List中的数，则将List中该数出现的次数+1；3.2遍历List中的每一个数：3.2.1如果该数出现的次数+(N-J)<=N/2,则说明该数不可能是所求数字，从List中删除该数；3.2.1如果该数出现的次数>N/2,则说明该数就是所求数字；3.3如果List中只剩下一个数，则该数即为所求的数字；
75.二叉树两个结点的最低共同父结点题目：二叉树的结点定义如下：structTreeNode{intm_nvalue;TreeNode*m_pLeft;TreeNode*m_pRight;};输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
------------------------------分析：进行二叉树遍历（递归），并在遍历中加入如下内容：1.如果当前节点等于某一个输入节点，则返回1；如果不是则继续向左、右子节点遍历，如果一直到叶子节点仍未找到，则返回0；2.如果节点的左子节点遍历和右子节点遍历都返回1，则该节点就是所求的最低的共同父结点；
80.阿里巴巴一道笔试题引自baihacker问题描述:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种这个笔试题,很YD,因为把某个递归关系隐藏得很深.
----------------------------这个比较简单，思路如下：1.从12个人中任意选取2个人出来，组成一列，根据组合数学有C（12,2）中方法；2.再从剩余的10个人中任意选取2个人出来，组成下一列，根据组合数学有C（10,2）中方法；3.以此类推；4.根据组合数学的乘法原理，总的排列方式数=C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)=748440
5.根据上面的内容，很容易写出递归程序。
------------------------------------结果是132，可以抽象成将12个数填写到一个二维数组中，按从小到大的顺序填写（从大到小也一样），填写的条件就是左边不能为空，下边不能为空。
---------------------------------------
最后附上我个人关于一些题的思路、简单回复：
July：
今天，暂写一下，前20题的，我个人的思路：1.把二元树转化成排序的双向链表中序遍历二元树，然后，把二元树各结点连接，转化成List。2.设计包含min函数的栈。这题，见的实在太多了。我上传的答案V0.2版，已花了不少篇幅，阐述它（可参考，画个图，可能会更清晰点）。3.求子数组的最大和不考虑数组中全为负数的情况。即遍历一次，就找到那些变量，然后相加。可设俩个变量，b（数组元素为负，不加，把下一个元素赋给b，数组元素非负，相加），sum，并始终与b比较，sum 6.腾讯面试题此题，只要找出规律后，就能很快写出下排的数。当然，编程求解，有一定难度。请参考答案V0.3版。7.判断俩个链表是否相交问题转化为：1.先判断带不带换2.如果都不带环，判断尾结点是否相等3.如果都带环，判断一链表上俩指针相遇的那个结点，是否在另一条链表上。如果在，则相交，不在，则不相交。8.微软面试题。此题较繁琐，略。9.判断整数序列是不是二元查找树的后序遍历结果考察树的后序遍历。10.翻转句子中单词的顺序。这题，很多人，都想到了。略。 11.求二叉树中结点的最大距离若不清楚题意，网上搜下，看下图。且答案V0.2版，已花了不小的篇幅阐述了此题，请参考。12.求1+2+....n（诸多限制）循环本质，即让同样的代码执行n次而已。很多方法：1.利用构造函数的特殊性质2.模板...13.输出链表中倒数第k个结点此题的思路，用俩指针，一指head，一指k-1个元素，相隔k的距离很多人，都知道。14.给定一个数值，查找相加的和，等于此数值的俩个数此题与第21题差不多，但难度不及第21题。且还有序数列。15.把树翻转，转化为它的镜像利用递归，借助栈。 在此，奉献另外一种思路：abcdefghi，要abc移动至最后abcdefghi->defabcghi->defghiabc 一俩指针，p1指向ch[0]，p2指向[chm-1]，p2每次移动m的距离，p1也跟着相应移动， 每次移动过后，交换。如上第一步，交换abc和def，就变成了abcdef->defabc 第一步，abcdefghi->defabcghi第二步，继续交换，defabcghi->defghiabc 整个过程，看起来，就是abc一步一步向后移动abcdefghidefabcghidefghiabc//最后的复杂度是O（m+n） 再举一个例子，如果1234567890要变成4567890123：12345678901.45612378902.45678912303.45678912034.45678910235.4567890123//最后三步，相当于0前移，p1已经不动。欢迎，就此第26题，继续讨论。 40.百度研发笔试题40.1.设计min函数的栈。这个问题，我已经在答案V0.2，V0.3版里，讨论过很多次了。欢迎，各位大侠，批评指正。 此题的第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中，始终保存着最小的元素。 然后，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中栈顶元素。 40.2.一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。一网友给的思路：比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc 用两个变量front，rear指向一个的子串区间的头和尾用一个intcnt[255]={0}记录当前这个子串里字符集a,b,c各自的个数，一个变量sum记录字符集里有多少个了。 rear一直加，更新cnt[]和sum的值，直到sum等于字符集个数然后front++,直到cnt[]里某个字符个数为0，这样就找到一个符合条件的字串了 40.3.欢迎，其他人，继续共享自己的思路。 ============== 永远，向您的厚道致敬。谢谢。July、二零一零年十二月三十日凌晨三点。