經(jīng)典數(shù)據(jù)結(jié)構(gòu)面試題含答案(編輯修改稿)
2025-07-16 07:56 本頁面
【文章內(nèi)容簡(jiǎn)介】 else if (a[i]b[mid]) end=mid1。 else start=mid+1。 } } return false。}后來發(fā)現(xiàn)有一個(gè) O(n)算法。因?yàn)閮蓚€(gè)數(shù)組都是排好序的。所以只要一次遍歷就行了。首先設(shè)兩個(gè)下標(biāo)，分別初始化為兩個(gè)數(shù)組的起始地址，依次向前推進(jìn)。推進(jìn)的規(guī)則是比較兩個(gè)數(shù)組中的數(shù)字，小的那個(gè)數(shù)組的下標(biāo)向前推進(jìn)一步，直到任何一個(gè)數(shù)組的下標(biāo)到達(dá)數(shù)組末尾時(shí)，如果這時(shí)還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。 bool findmon2(int a[], int size1, int b[], int size2){ int i=0,j=0。 while(isize1 amp。amp。 jsize2) { if(a[i]==b[j]) return true。 if(a[i]b[j]) j++。 if(a[i]b[j]) i++。 } return false。}4,最大子序列 問題：給定一整數(shù)序列A1， A2，... An （可能有負(fù)數(shù)），求A1~An的一個(gè)子序列Ai~Aj，使得Ai到Aj的和最大例如：整數(shù)序列2, 11, 4, 13, 5, 2, 5, 3, 12, 9的最大子序列的和為21。對(duì)于這個(gè)問題，最簡(jiǎn)單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線性算法實(shí)現(xiàn)，算法的來源于Programming Pearls一書。 在給出線性算法之前，先來看一個(gè)對(duì)窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。其實(shí)這個(gè)算法只是對(duì)對(duì)窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。假設(shè)Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用這一個(gè)遞推，我們就可以得到下面這個(gè)算法： int max_sub(int a[],int size){ int i,j,v,max=a[0]。 for(i=0。isize。i++) { v=0。 for(j=i。jsize。j++) { v=v+a[j]。//Sum(i, j+1) = Sum(i, j) + A[j+1] if(vmax) max=v。 } } return max。}那怎樣才能達(dá)到線性復(fù)雜度呢？這里運(yùn)用動(dòng)態(tài)規(guī)劃的思想。先看一下源代碼實(shí)現(xiàn)： int max_sub2(int a[], int size){ int i,max=0,temp_sum=0。 for(i=0。isize。i++) { temp_sum+=a[i]。 if(temp_summax) max=temp_sum。 else if(temp_sum0) temp_sum=0。 } return max。}6,按單詞反轉(zhuǎn)字符串 并不是簡(jiǎn)單的字符串反轉(zhuǎn)，而是按給定字符串里的單詞將字符串倒轉(zhuǎn)過來，就是說字符串里面的單詞還是保持原來的順序，這里的每個(gè)單詞用空格分開。例如：Here is 經(jīng)過反轉(zhuǎn)后變?yōu)椋?is Here如果只是簡(jiǎn)單的將所有字符串翻轉(zhuǎn)的話，可以遍歷字符串，將第一個(gè)字符和最后一個(gè)交換，第二個(gè)和倒數(shù)第二個(gè)交換，依次循環(huán)。其實(shí)按照單詞反轉(zhuǎn)的話可以在第一遍遍歷的基礎(chǔ)上，再遍歷一遍字符串，對(duì)每一個(gè)單詞再反轉(zhuǎn)一次。這樣每個(gè)單詞又恢復(fù)了原來的順序。char* reverse_word(const char* str){ int len = strlen(str)。 char* restr = new char[len+1]。 strcpy(restr,str)。 int i,j。 for(i=0,j=len1。ij。i++,j) { char temp=restr[i]。 restr[i]=restr[j]。 restr[j]=temp。 } int k=0。 while(klen) { i=j=k。 while(restr[j]!=39。 39。 amp。amp。 restr[j]!=39。39。 ) j++。16
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1