四道微软面试经典算法题

比较经典的四个算法题，目前只收集到相关的思路和个别题目的解法，不断更新中 
1.一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。 
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。 
注意： 
- 5个数值允许是乱序的。比如： 8 7 5 0 6 
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4 
- 0可以多次出现。 
- 复杂度如果是O(n2)则不得分。 
2.设计一个算法，找出二叉树上任意两个结点的最近共同父结点。 
复杂度如果是O(n2)则不得分。 
3.一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。 
复杂度如果是O(n2)则不得分。 
4.一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。 
复杂度最好是O(n)，如果是O(n2)则不得分。 
思路分析 
1.非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4 
2.如果每个节点包含父亲指针，把两个节点到根的路径都记录下来，两条路径的最后面的元素肯定相同， 
从两条路径的最后一个元素向前比较，直到第一次出现分叉为止，就可以找到最近节点。复杂度为O（n）， 
路径最长可能是n 
如果不包含父亲节点，那就先前序遍历二叉树，遍历的时候可以像哈夫曼树那样左右01编号， 
记录给定两节点的到达路径，最后比较两个0，1序列的前面位数，直到出现不相等为止，就找到最近父节点， 
复杂度也是O（n） 
3.找出最大值，最小值，复杂度都是O（h），然后搜索f，可以找到f应该插入的位置，复杂度也是O（h）， 
再找f的后继，复杂度也是O（h），h最大可能是n，所以总体最坏情况复杂度就是O（n） 
4.先排序，复杂度O（nlgn），然后用两个指示器（front和back）分别指向第一个和最后一个元素，如果 
A[front]+A[back]>N+1，则back–； 
如果A[front]+A[back]=N+1，则计数器加1，back–，同时front++； 
如果A[front]+A[back] 重复上述步骤，O（n）时间找到所有数对，总体复杂度为O（nlgn） 
题目分析 
第1题：首先扫描一遍求出非0平均值，然后再扫描一遍即可判断，复杂度：O(n) 
第2题，是一个送分题，可以设计一个相当巧妙的数据结构，其复杂度为O(n) 
第3题，也是送分题，扫描几次即可 
第4题，送分题。牺牲空间即可完成。 
具体算法 
1.思路是 非0最大值-非0最小值 <=数组长度-1 
我觉得这道题的前提非常重要 

1public boolean isContiguous(int[] array) 
2   { 
3   int min=-1; 
4   int max=-1; 
5   for(int i=0;i <array.length;i++) 
6   { 
7   if(array[i]!=0) 
8   { 
9   if(min==-1||min>array[i]) 
10   { 
11   min=array[i]; 
12   } 
13   if(max==-1||max <array[i]) 
14   { 
15   max=array[i]; 
16 } 
17   } 
18   } 
19   return max-min <=array.length-1; 
20   } 

4.关键点在于创建一个Hash表，典型的以空间换时间:-) 

1    public static int getSumCount(int[] array,int N) 
2     { 
3     int count=0; 
4     //创建哈希表 
5         int[] hashTable=new int[N+1]; 
6         for(int i=0;i <array.length;i++) 
7         { 
8         hashTable[array[i]]=array[i]; 
9         } 
10         for(int i=0;i <array.length;i++) 
11         { 
12         //如果是数对中较小的整数(防止重复计数) 
13         //并且配对的整数存在 
14                 //并且不等于与之配对的整数,因数列不存在重复整数 
15                 if(array[i] <=(N+1)/2&&hashTable[N+1-array[i]]!=0&&array[i]*2!=N+1) 
16         { 
17             count++; 
18         } 
19         } 
20     return count; 
21     }

来自:  http://hi.baidu.com/fengfage/blog/item/c9da90ca137fd24af21fe78f.html

本文转自左正博客园博客，原文链接：http://www.cnblogs.com/soundcode/archive/2011/11/21/2257605.html，如需转载请自行联系原作者