微軟四道經(jīng)典算法面試題(附思路)

比較經(jīng)典的四個算法題，目前只收集到相關(guān)的思路和個別題目的解法，不斷更新中
1.一個整數(shù)數(shù)列，元素取值可能是0~65535中的任意一個數(shù)，相同數(shù)值不會重復出現(xiàn)。0是例外，可以反復出現(xiàn)。
請設(shè)計一個算法，當你從該數(shù)列中隨意選取5個數(shù)值，判斷這5個數(shù)值是否連續(xù)相鄰。
注意：
-?5個數(shù)值允許是亂序的。比如：?8?7?5?0?6
-?0可以通配任意數(shù)值。比如：8?7?5?0?6?中的0可以通配成9或者4
-?0可以多次出現(xiàn)。
-?復雜度如果是O(n2)則不得分。
2.設(shè)計一個算法，找出二叉樹上任意兩個結(jié)點的最近共同父結(jié)點。
復雜度如果是O(n2)則不得分。
3.一棵排序二叉樹，令?f=(最大值?最小值)/2，設(shè)計一個算法，找出距離f值最近、大于f值的結(jié)點。
復雜度如果是O(n2)則不得分。
4.一個整數(shù)數(shù)列，元素取值可能是1~N（N是一個較大的正整數(shù)）中的任意一個數(shù)，相同數(shù)值不會重復出現(xiàn)。設(shè)計一個算法，找出數(shù)列中符合條件的數(shù)對的個數(shù)，滿足數(shù)對中兩數(shù)的和等于N?1。
復雜度最好是O(n)，如果是O(n2)則不得分。
思路分析
1.非0最大-非0最小?1??非0最大-非0最小?N?1，則back–；
如果A[front]?A[back]=N?1，則計數(shù)器加1，back–，同時front?；
如果A[front]?A[back]?重復上述步驟，O（n）時間找到所有數(shù)對，總體復雜度為O（nlgn）
題目分析
第1題：首先掃描一遍求出非0平均值，然后再掃描一遍即可判斷，復雜度：O(n)
第2題，是一個送分題，可以設(shè)計一個相當巧妙的數(shù)據(jù)結(jié)構(gòu)，其復雜度為O(n)
第3題，也是送分題，掃描幾次即可
第4題，送分題。犧牲空間即可完成。
具體算法
1.思路是?非0最大值-非0最小值?<=數(shù)組長度-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.關(guān)鍵點在于創(chuàng)建一個Hash表，典型的以空間換時間:-)
????public?static?int?getSumCount(int[]?array,int?N)
????{
????int?count=0;
????//創(chuàng)建哈希表
????????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?)
????????{
????????//如果是數(shù)對中較小的整數(shù)(防止重復計數(shù))
????????//并且配對的整數(shù)存在
????????????????//并且不等于與之配對的整數(shù),因數(shù)列不存在重復整數(shù)
????????????????if(array?<=(N?1)/2&&hashTable[N?1-array]!=0&&array*2!=N?1)
????????{
????????????count?;
????????}
????????}
????return?count;
????}