微软四道经典算法面试题(附思路)

比较经典的四个算法题，目前只收集到相关的思路和个别题目的解法，不断更新中
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  非0最大-非0最小 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
我觉得这道题的前提非常重要
public boolean isContiguous(int[] array)
  {
  int min=-1;
  int max=-1;
  for(int i=0;iarray)
  {
  min=array;
  }
  if(max==-1||max<array)
  {
  max=array;
  }
  }
  }
  return max-min <=array.length-1;
  }
4.关键点在于创建一个Hash表，典型的以空间换时间:-)
    public static int getSumCount(int[] array,int N)
    {
    int count=0;
    //创建哈希表
        int[] hashTable=new int[N 1];
        for(int i=0;i <array.length;i )
        {
        hashTable[array]=array;
        }
        for(int i=0;i <array.length;i )
        {
        //如果是数对中较小的整数(防止重复计数)
        //并且配对的整数存在
                //并且不等于与之配对的整数,因数列不存在重复整数
                if(array <=(N 1)/2&&hashTable[N 1-array]!=0&&array*2!=N 1)
        {
            count ;
        }
        }
    return count;
    }