比較經(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ù)，滿足數(shù)對(duì)中兩數(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)到根的路徑都記錄下來(lái)，兩條路徑的最后面的元素肯定相同，
從兩條路徑的最后一個(gè)元素向前比較，直到第一次出現(xiàn)分叉為止，就可以找到最近節(jié)點(diǎn)。復(fù)雜度為O（n），
路徑最長(zhǎng)可能是n
如果不包含父親節(jié)點(diǎn)，那就先前序遍歷二叉樹(shù)，遍歷的時(shí)候可以像哈夫曼樹(shù)那樣左右01編號(hào)，
記錄給定兩節(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ù)對(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é)得這道題的前提非常重要
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)建一個(gè)Hash表，典型的以空間換時(shí)間:-)
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ù)對(duì)中較小的整數(shù)(防止重復(fù)計(jì)數(shù))
//并且配對(duì)的整數(shù)存在
//并且不等于與之配對(duì)的整數(shù),因數(shù)列不存在重復(fù)整數(shù)
if(array[i] <=(N+1)/2&&hashTable[N+1-array[i]]!=0&&array[i]*2!=N+1)
{
count++;
}
}
return count;
}
|
|
