比較經(jīng)典的四個算法題，目前只收集到相關(guān)的思路和個別題目的解法，不斷更新中

1.一個整數(shù)數(shù)列，元素取值可能是0~65535中的任意一個數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。0是例外，可以反復(fù)出現(xiàn)。
請設(shè)計一個算法，當(dāng)你從該數(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)。
- 復(fù)雜度如果是O(n2)則不得分。

2.設(shè)計一個算法，找出二叉樹上任意兩個結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。

3.一棵排序二叉樹，令 f=(最大值+最小值)/2，設(shè)計一個算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。

4.一個整數(shù)數(shù)列，元素取值可能是1~N（N是一個較大的正整數(shù)）中的任意一個數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。設(shè)計一個算法，找出數(shù)列中符合條件的數(shù)對的個數(shù)，滿足數(shù)對中兩數(shù)的和等于N+1。
復(fù)雜度最好是O(n)，如果是O(n2)則不得分。

思路分析
1.非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4

2.如果每個節(jié)點(diǎn)包含父親指針，把兩個節(jié)點(diǎn)到根的路徑都記錄下來，兩條路徑的最后面的元素肯定相同，
從兩條路徑的最后一個元素向前比較，直到第一次出現(xiàn)分叉為止，就可以找到最近節(jié)點(diǎn)。復(fù)雜度為O（n），
路徑最長可能是n
如果不包含父親節(jié)點(diǎn)，那就先前序遍歷二叉樹，遍歷的時候可以像哈夫曼樹那樣左右01編號，
記錄給定兩節(jié)點(diǎn)的到達(dá)路徑，最后比較兩個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），然后用兩個指示器（front和back）分別指向第一個和最后一個元素，如果
A[front]+A[back]>N+1，則back–；
如果A[front]+A[back]=N+1，則計數(shù)器加1，back–，同時front++；
如果A[front]+A[back] 重復(fù)上述步驟，O（n）時間找到所有數(shù)對，總體復(fù)雜度為O（nlgn）

題目分析
第1題：首先掃描一遍求出非0平均值，然后再掃描一遍即可判斷，復(fù)雜度：O(n)
第2題，是一個送分題，可以設(shè)計一個相當(dāng)巧妙的數(shù)據(jù)結(jié)構(gòu)，其復(fù)雜度為O(n)
第3題，也是送分題，掃描幾次即可
第4題，送分題。犧牲空間即可完成。

具體算法
1.思路是 非0最大值-非0最小值 <=數(shù)組長度-1
我覺得這道題的前提非常重要

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            

public boolean isContiguous(int[] array)
            {
            int min=-1;
            int max=-1;
            for(int i=0;i <array.length;i++)
            {
            if(array[i]!=0)
            {
            if(min==-1||min>array[i])
            {
            min=array[i];
            }
            if(max==-1||max <array[i])
            {
            max=array[i];
            }
            }
            }
            return max-min <=array.length-1;
            }

4.關(guān)鍵點(diǎn)在于創(chuàng)建一個Hash表，典型的以空間換時間:-)

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            

    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[i]]=array[i];
            }
            for(int i=0;i <array.length;i++)
            {
            //如果是數(shù)對中較小的整數(shù)(防止重復(fù)計數(shù))
            //并且配對的整數(shù)存在
            //并且不等于與之配對的整數(shù),因數(shù)列不存在重復(fù)整數(shù)
            if(array[i] <=(N+1)/2&&hashTable[N+1-array[i]]!=0&&array[i]*2!=N+1)
            {
            count++;
            }
            }
            return count;
            }