比較經(jīng)典的四個(gè)算法題，目前只收集到相關(guān)的思路和個(gè)別題目的解法，不斷更新中
1.一個(gè)整數(shù)數(shù)列，元素取值可能是0~65535中的任意一個(gè)數(shù)，相同數(shù)值不會(huì)重復(fù)出現(xiàn)。0是例外，可以反復(fù)出現(xiàn)。
請(qǐng)?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è)算法，找出二叉樹(shù)上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。
3.一棵排序二叉樹(shù)，令?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ù)值不會(huì)重復(fù)出現(xiàn)。設(shè)計(jì)一個(gè)算法，找出數(shù)列中符合條件的數(shù)對(duì)的個(gè)數(shù)，滿(mǎn)足數(shù)對(duì)中兩數(shù)的和等于N?1。
復(fù)雜度最好是O(n)，如果是O(n2)則不得分。
思路分析
1.非0最大-非0最小?1??非0最大-非0最小?N?1，則back–；
如果A[front]?A[back]=N?1，則計(jì)數(shù)器加1，back–，同時(shí)front?；
如果A[front]?A[back]?重復(fù)上述步驟，O（n）時(shí)間找到所有數(shù)對(duì)，總體復(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ù)組長(zhǎng)度-1
我覺(jué)得這道題的前提非常重要
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)鍵點(diǎn)在于創(chuàng)建一個(gè)Hash表，典型的以空間換時(shí)間:-)
????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ù)對(duì)中較小的整數(shù)(防止重復(fù)計(jì)數(shù))
????????//并且配對(duì)的整數(shù)存在
????????????????//并且不等于與之配對(duì)的整數(shù),因數(shù)列不存在重復(fù)整數(shù)
????????????????if(array?<=(N?1)/2&&hashTable[N?1-array]!=0&&array*2!=N?1)
????????{
????????????count?;
????????}
????????}
????return?count;
????}