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