比較經(jīng)典的四個(gè)算法題，目前只收集到相關(guān)的思路和個(gè)別題目的解法，不斷更新中
1.一個(gè)整數(shù)數(shù)列，元素取值可能是0~65535中的任意一個(gè)數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。0是例外，可以反復(fù)出現(xiàn)。
請?jiān)O(shè)計(jì)一個(gè)算法，當(dāng)你從該數(shù)列中隨意選取5個(gè)數(shù)值，判斷這5個(gè)數(shù)值是否連續(xù)相鄰。
注意：
- 5個(gè)數(shù)值允許是亂序的。比如： 8 7 5 0 6
- 0可以通配任意數(shù)值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出現(xiàn)。
- 復(fù)雜度如果是O(n2)則不得分。
2.設(shè)計(jì)一個(gè)算法，找出二叉樹上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。
3.一棵排序二叉樹，令 f=(最大值+最小值)/2，設(shè)計(jì)一個(gè)算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。
4.一個(gè)整數(shù)數(shù)列，元素取值可能是1~N(N是一個(gè)較大的正整數(shù))中的任意一個(gè)數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。設(shè)計(jì)一個(gè)算法，找出數(shù)列中符合條件的數(shù)對的個(gè)數(shù)，滿足數(shù)對中兩數(shù)的和等于N+1。
復(fù)雜度最好是O(n)，如果是O(n2)則不得分。
思路分析
1.非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4
2.如果每個(gè)節(jié)點(diǎn)包含父親指針，把兩個(gè)節(jié)點(diǎn)到根的路徑都記錄下來，兩條路徑的最后面的元素肯定相同，
從兩條路徑的最后一個(gè)元素向前比較，直到第一次出現(xiàn)分叉為止，就可以找到最近節(jié)點(diǎn)。復(fù)雜度為O(n)，
路徑最長可能是n
如果不包含父親節(jié)點(diǎn)，那就先前序遍歷二叉樹，遍歷的時(shí)候可以像哈夫曼樹那樣左右01編號，
記錄給定兩節(jié)點(diǎn)的到達(dá)路徑，最后比較兩個(gè)0，1序列的前面位數(shù)，直到出現(xiàn)不相等為止，就找到最近父節(jié)點(diǎn)，
復(fù)雜度也是O(n)
3.找出最大值，最小值，復(fù)雜度都是O(h)，然后搜索f，可以找到f應(yīng)該插入的位置，復(fù)雜度也是O(h)，
再找f的后繼，復(fù)雜度也是O(h)，h最大可能是n，所以總體最壞情況復(fù)雜度就是O(n)
4.先排序，復(fù)雜度O(nlgn)，然后用兩個(gè)指示器(front和back)分別指向第一個(gè)和最后一個(gè)元素，如果
A[front]+A[back]>N+1，則back–；
如果A[front]+A[back]=N+1，則計(jì)數(shù)器加1，back–，同時(shí)front++；
如果A[front]+A[back] 重復(fù)上述步驟，O(n)時(shí)間找到所有數(shù)對，總體復(fù)雜度為O(nlgn)
題目分析
第1題：首先掃描一遍求出非0平均值，然后再掃描一遍即可判斷，復(fù)雜度：O(n)
第2題，是一個(gè)送分題，可以設(shè)計(jì)一個(gè)相當(dāng)巧妙的數(shù)據(jù)結(jié)構(gòu)，其復(fù)雜度為O(n)
第3題，也是送分題，掃描幾次即可
第4題，送分題。犧牲空間即可完成。
具體算法
1.思路是 非0最大值-非0最小值 <=數(shù)組長度-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.關(guān)鍵點(diǎn)在于創(chuàng)建一個(gè)Hash表，典型的以空間換時(shí)間:-)
1??? public static int getSumCount(int[] array,int N)
2???? {
3???? int count=0;
4???? //創(chuàng)建哈希表
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???????? //如果是數(shù)對中較小的整數(shù)(防止重復(fù)計(jì)數(shù))
13???????? //并且配對的整數(shù)存在
14???????????????? //并且不等于與之配對的整數(shù),因數(shù)列不存在重復(fù)整數(shù)
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

總結(jié)

以上是生活随笔為你收集整理的四道微软面试经典算法题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。