网友答案整理I：微软等面试100题系列之网友精彩回复 [一]

微软等数据结构+算法面试100题系列之网友精彩回复[一]

------------------------------

作者:July飞雪

<!--EndFragment-->

一直不断有网友来信，想要微软等100题的答案，可由于整理这100题的答案，分量太大。

所以，后60题的答案，一直迟迟未得出炉。我也早已经在前面的博文中，有所阐述：

=====

由于答案的整理不像题目那般，除了自己所有的，还可以从网上搜集，
而这个答案，全都得由自己去想、去做，更是由于这些题现已经有近10万人看到或见识到。
如此，更兼诚惶诚恐，不敢大肆造次。
我也将，更加细致的整理本100题V0.1版最后60题第41题-100题的答案，
所以希望，各位更加耐心的等待。

=======================

但，网友热切盼望的心情，实不敢有丁点辜负。

正好，有一群不错的，极具热心的网友，

在我发表的帖子上，一直在孜孜不倦的思考，不畏100题分量之大，一点一点的做这100题。

正好可以整理，贴出来作为各位后来网友的思路参考，于是，本文，就产生了。

首先，向所有在我帖子上，回复了自己独立而完整的思路的，所有热心的网友，表示衷心的感谢与致敬。

为了表示对他们劳动成果的尊重，接下来，除了继续分类整理这100题的同时，

我将把一些网友的精彩回复，整理到我的博客里。

同时，希望各位能对以下任何网友给出的思路，毫不犹豫的给出批评、指正。

并特别的期待，你也能贡献你的思路、或者更好的想法、算法。

谢谢。

----------------------

完整100题，请参见，
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx

以下所有的思路、答案选自网友飞雪在我这帖子上的回复：

本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

//当然，继续欢迎，各位把自己针对此100题中任何一道，给出自己的思路，回复于上述帖子上。:D。

-----------------------------------------------------------------

为了表示对飞雪最大的尊重，我没有对他的回复做任何修改与改动。

欢迎，各位，毫不犹豫的，对他的思路、或解法提出质疑、批评、指正。谢谢。

飞雪：

第一题，改为循环链表做。
左边返回循环链表的最后一个元素，右边也返回，于是就可以返回加上根的循环链表了。
最后把循环部分断开，为所求。
第二题，似乎是今年很热的题，略。
第三题，最大子段和，略。

几个类似问题：
1.问这样的子串有多少个。
2.如果是首尾相连的，那么最大子串和是多少，有多少个。
3.如果是首尾相连的，取两个不相交子串，那么最大子串和是多少。

第四题，dfs。
第五题，一般可以用类似二分的，丢弃一半，这是渐近线性的算法。
还可以分为若干个桶，然后可以知道第k个在哪个桶里，这种算法比较稳定，如果输入比较均匀，表现可能较好。
另外，如果输入是有一定分布规律的话，可以取其中一部分进行采样，然后得到一个估计，然后再在这个估计的基础上优化。

第6题
直觉是有很多元素是0，所以可以先确定0的，然后再凭感觉做后面的。
第7题
似乎很古老了，略。
一个新问题：
结点里多了一个指针Node* x;指向链表中另一个元素，要求复制一个相同的链表。
第8题
...
第9题
预处题可以在nlogn内查询子段最大，最小值。
枚举根，查询左边和右边最小和最大值，于是可以知道根是不是合法的，如果合法，然后可以转换为子问题是不是合法。
另外似乎也可以不用做RMQ的预处理，因为枚举根是O(n)的，而求区间最大最小值也是O(n)的，RMQ会多一点东西出来。
复杂度大概是O(n^2)吧。
第10题
略

第9题补充，
总共O(n^2)个状态，O(n)的转移，所以复杂度上限是O(n^3)，但是实际上可能只有O(n^2)。

第11题
用dp[i]表示结点i上子问题的解，h[i]表示i子树的高度。
于是i的解可能是：i的高度，两个最高的子树的高度和加1（如果子树大于等于2），子问题上的解。
第12题
暂时没想法，本来想用位移计算n^2但是要判断某一位是不是1。
第13题
构造两个步长差为k的指针，然后同时移动。
主要是优化常数了。
第14题
for (int i = 0, j = n - 1; i < j;)
{
int t = data[i] + data[j];
if (t == value) ok;
if (t > value) --j;
else ++i;
}
第15题
递归的直接应用，如果要求循环，估计也是伪的，是直接把递归化为循环那种。
至于直接用循环的，还没想法。

第16题
利用队列做层次遍历，似乎也很老了。
第17题
貌似开个ascii上限的数组遍历就行了。
第18题
很老的题了。
给几个变种吧：
要求输出第一个的，而报数是在按a1, a2, a3, ..., ax的顺序报，也就是说第一次报a1的出局，第二次报到a2的出局，报到ax后又重新来。似乎是09年某个regional的题。
要求输出最后一个的，n大概是10亿，k是不超过1000，在hdoj上有。
还有就是2n个人，前面的是坏人，后面的是好人，要求好后在坏人后出去，求最小的k，也是old题了。
第19题
如果精度要求不高，直接解差分方程。
如果精度要求高，可以用大数加矩阵二分。
第20题
似乎没啥难度。

第21题
npc难问题。
这里只给出n不大，用位俺码来表示集合，枚举所有含m个元素的集合的算法：
int x = comb & -comb, y = comb + x;
comb = ((comb & ~y) / x >> 1) | y;
来源是topcoder.
第22题
逻辑推理吧，如果用程序的话，可能就是枚举所有情况，然后一步一步判断，注意前后关系。
第23题
在x-z平面上做。
第24题
似乎又是老的了。
第25题
用一个自动机扫描过去就OK了。
开始状态，字符状态，数字状态，结束状态。
26.左旋转字符串
两种做法：
1.分别就地翻转后再整体翻转，但是隐藏的常数偏大。
2.转换分解为循环，可能内存会大一点点，还有就是__gcd算法，但是最小复制的。
27.跳台阶问题
免子数，前面有提。
28.整数的二进制表示中1的个数
可以用x&(x-1)技巧，可以分段打表，也可以用内建函数__builtin_popcount，还可以位加法并对其优化。
29.栈的push、pop序列
问题可以加强为，push的元素是从小到大的，也可以知道这两个问题是等价的，但是转换过程是nlogn。
既然push是从小到大的，于是问题就灰常好解决了。
30.在从1到n的正数中1出现的次数
按位dp，计算每一位中出现的次数。
31.华为面试题：
无图无真相
32.
问题等价于给定n+m个元素，分为两部分，其中一部分为n个元素。
用dp[i][j]表示从这n+m个元素中先i个出来是不是能组成一个j。
于是i最大为min(n, m)，再遍历一次可以求解。
空间复杂度可以优化到O(全部的和)。
但是这样的话，要求所有的和不太大。
33.
似乎没有读懂，例子貌似只要统计1，2，3的次数就行了。
34.
似乎是OS上经典的问题了。
35.
枚举行O(N^2)
在列上做最大子段和O(M)。
36.引用自网友：longzuo
谷歌笔试
没仔细读。
37.
可能题目有小bug，最好假定串互不包含，否则会有些比较fuckable的情况。
然后就是预处理建拓扑图，求个最长路出来了。
38.
(3^n-1)/2
这个题目至少是2006年以前的了，做过。
39
39.1老题
39.2简单的dfs
40
似乎也很老了，不再回答了。

41.求固晶机的晶元查找程序
表示没读懂。
42.请修改append函数，利用这个函数实现：
似乎就是归并过程，取需要的部分。
43.递归和非递归俩种方法实现二叉树的前序遍历。
……加强为不准用辅助栈。
44.腾讯面试题：
……
45.雅虎：
45.1
每个点有个坐标(i,j)根据i+j的奇偶性，于是数字可以分为两组。
于是，这两组的和要相等。
45.2
似乎可以枚举m再做搜索。
46.搜狐：
catalan数
47.创新工场：
经典的dp了。
48.微软：
似乎还是直接二分。
如果序列从中间断为两部分，至多有一部分是一个递减序列循环移动而成的，并且是可判断的。
递归时，判断两部分的性质，对于递减的，可以知道是不是在里面，对于不满足递减性质的，可以递归地处理。
49.一道看上去很吓人的算法面试题：
神题，表示没想法。
50.网易有道笔试：
似乎重复了。
51.和为n连续正数序列
这个似乎不是网易的，而是05年百度之星的。
枚举划分的个数就行了，注意一下枚举的范围。
52.二元树的深度。
dfs
53.字符串的排列。
略
54.调整数组顺序使奇数位于偶数前面。
参考归并排序的inplace merge.
55.
题目：类CMyString的声明如下：
略

补充一下51：
如果划分为奇数个，那么n能被中间那个数整除，且n/划分个数就是中间那个数。
如果划分为偶数个，中间两个数的和和整除n的，刚好是n/(划分个数的一半)。
补充一下54：
好像直接inplace merge是不对的
可以用两个指针分别指向操作后的两个开始位置，然后扫描。
都扫描到不合法的为止，然后交换。然后继续扫描。。。

修改33楼，“NPC难问题”没这个说法，多打了一个C字，应该是“NP-难问题”，这和NP完全问题是不同的。

修正一下上文中22题给的解法。
似乎推理还推不出来。
编程计算我提的也是不对的。
应该是首先构造所有合法的可能性。
然后对于A猜不出。那么对于可能可能的B，C的组合应该是大于1种A。于是可以去掉一种的。
同样的对去掉后的，根据B猜不出，可以去掉一些。
再根据C继续去掉。
最后A猜出了，说明对应的B，C组合有只有一种情况。
我但是算出来是有四种情况。

于是尝试修改，对于B，C的组合，不考虑其顺序的话，还剩两种情况。

得再想想。
不考虑顺序，还剩0种。

56.最长公共字串。
经典lcs dp
57.用俩个栈实现队列。
似乎也没啥说的
58.从尾到头输出链表。
似乎可以考虑递归。
也可以考虑临时性翻转。
还可以考虑把值存到一个序列中去。
59.不能被继承的类。
final类的经典实现：利用一个private虚继承一个有非平凡构造函数的类。
60.在O（1）时间内删除链表结点。
写的时候要小心。
61.找出数组中两个只出现一次的数字
可以先全部异或起来，得到这两个数字的异或值。
可以知道这两个数字在某一位上不同，根据这个不同，把所有的数字分为两组。
分组异或出来为所求。
类似问题，1到n的数，丢失了一个数，如何求出来。丢失了两个呢？
62.找出链表的第一个公共结点。
似乎没啥说的。
一个以前我给的答案，遍历三次（遍历的时候返转），得到
A + X, B + X, A + B的值，（A为每一个链表独立部分，B为第二个链接独立部分，X为公共部分）
但是这似乎要假定X > 0.
63.在字符串中删除特定的字符。
没啥说的。
64. 寻找丑数。
在一个更大的集合内BFS。
65.输出1到最大的N位数
似乎没说的。
如果要溢出的话，说明输出相当大，再去注意一些细节意义不大了。
66.颠倒栈。
直接递归地做了。
不清楚的是，输入是啥？能改变输入栈么？
67.俩个闲玩娱乐。
67.1似乎直接排序就完了。
67.2假定n不太大，用dp[i][j]表示前i个骰子组合成j的方案数。
于是加一个骰子可以更新dp[i+1][j+x] x = 1 ... 6。
如果n太大，可以试着把生成函数求出来。
68.把数组排成最小的数。
对于两个串a,b。a在b的前面的时候a+b<b+a.
69.旋转数组中的最小元素。
似乎可以2分的。在前面的题目中有类似的。
70.给出一个函数来输出一个字符串的所有排列。
http://hi.baidu.com/feixue/blog/item/9442d11337eef9085aaf5355.html

71.数值的整数次方。
二分
72.
singleton的实现方法太多，但是各种实现又有各种问题。
73.对策字符串的最大长度。
最长回文子串：
经典方法：反转后连接到原字符串上，求出后缀数组，再求出高度数组，再各种处理。
另外还有一个，基于分治，类似暴力，近似线性的做法。
74.数组中超过出现次数超过一半的数字
主元素的查找，一种做法是每两个一组，不同的消去，相同的保留一个，最后还是线性的。
另一种做法是扫描+计数。
扩展：允许刚好出现一半。
75.二叉树两个结点的最低共同父结点
经典的LCA问题。
在欧拉序列上做RMQ。
或者用tarjan离线地做。
或者直接暴力。
76.复杂链表的复制
A B A B A B
77.关于链表问题的面试题目如下：
77.1似乎old了
在chinaunix有一个04年9月的贴子，里面有分析，似乎比较详细。
77.2又old了。
77.3还是没变。
77.4略
77.5略
78.链表和数组的区别在哪里？
各有长短。
有一种互补的数据结构叫 块状链表。
79.
80.阿里巴巴一道笔试题
似乎是我发的贴子里的。

81
81.1
用一个数组表示所有后缀的最小值，然后从左往右扫描，记录扫描到的最大值。
81.2
反向做hash？
81.3
一般是rbt。
82
82.1
不熟悉这方面的
82.2
同上
83
83.1
统计奇数的数组，然后两个位置开始扫描，都有不合法的时候交换。
83.2
old题。
84
84.1
一般还是开个数组扫描并统计
84.2
如果n是偶数可以知道一半的概率大于等于n/2于是可以用随机的0，1表示，再加上一个0到n/2-1的随机
数就行了。
如果是奇数似乎我没有好的想法，可以考虑生成一个0到2^t-1的随机数然后对n取模，可以知道取模后可能
的值都是1/n，当t越大，效果越好。这样可以以1/n的概率返回n/2，对于其它数很好处理。
85
85.1翻转A后的最长公共前缀。
85.2单串匹配算法灰常多的。
86
这个递归地用用就行了，平衡的话，要溢出时整数的个数就已经溢出了。
非递归的话开个指针数组，一次长度为2，处理的地址是0,2,4第二次长度为4地址是0,4,8。
87
似乎都没什么可以说的。
88
暂时我只能做到O(n)空间O(n)时间或者O(1)空间O(n^2)时间。
89
89.5
表示只会用后缀数组求最大公共子串。
90
90.1
似乎是在考察无中间变量的交换。
90.2
while (str[i] = str[j++]) if (str[i] != key) ++i;
90.3
略
91
91.1
10：第桶酒给对应的二进制位那些老鼠吃。
91.2
不清楚输入输出
92
经典的逆序数了
93
和前文重复了。
94
如果数据范围不大，可以先排序，然后从大的往小的扫描：
dp[i][j]表示以i结尾，公差为j的最长序列，时空复杂度和元素范围有关。
范围太大的话，可以考虑搜索。
95
略
96
略
97
略
98
略
99
99.1
从两头开始点可以计算出半个小时，组合多个可以计算出15分钟。
99.2
略
99.3
如果我问指向的一条路是不是正确的方向，对方会回答什么。
100
略
ps1，倒推。
ps2，还在想。

完。

=============

欢迎，各位，毫不犹豫的，对他的思路、或解法提出质疑、批评、指正。谢谢。

友情链接下：

飞雪主页：
http://hi.csdn.net/baihacker

飞雪博客：
http://blog.csdn.net/baihacker

--------------------------------------------------

接下来，我会陆续贴出其它网友在我帖子上，所回复的精彩答案与思路。

再次，向飞雪等网友表示致敬。

谢谢，大家。

帖子回复光荣榜第一期(按回复先后顺序排列)：

感谢：
飞雪
shmiluwabi666
My_hello
mimo9527
hawksoft
涂文强
litaoye
fengqiao1999
linyt
Force200413
supernove
kof87427

特别感谢：
飞雪
mimo9527
litaoye
hawksoft

==========================================

1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100题，请参见，
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多详情，请参见，本人博客：
My Blog：
http://blog.csdn.net/v_JULY_v
4.所有的资源（题目+答案）下载地址：
http://v_july_v.download.csdn.net/
5.本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

作者声明:

本人July对本博客所有任何内容和资料享有版权，转载请注明作者本人July及出处。

永远，向您的厚道致敬。谢谢。July、二零一零年十二月十六日。

<!--EndFragment-->