數(shù)據(jù)結(jié)構(gòu)常見筆試題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 一個數(shù)組中對第一個數(shù)組中的每個元素進行binary search。用C++實現(xiàn)代碼如下：bool FindCommon(int a[], int size1, int b[], int size2){int i。for (i = 0。 i size1。 i++){int start = 0, end = size21, mid。while (start = end){mid = (start + end)/2。if (a[i] == b[mid])return true。else if (a[i] b[mid])end = mid 1。elsestart = mid + 1。}}return false。}后來發(fā)現(xiàn)有一個O(n)算法。因為兩個數(shù)組都是排好序的。所以只要一次遍歷就行了。首先設(shè)兩個下標，分別初始化為兩個數(shù)組的起始地址，依次向前推進。推進的規(guī)則是比較兩個數(shù)組中的數(shù)字，小的那個數(shù)組的下標向前推進一步，直到任何一個數(shù)組的下標到達數(shù)組末尾時，如果這時還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。bool FindCommon2(int a[], int size1, int b[], int size2){int i = 0, j = 0。while (i size1 amp。amp。 j size2){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（可能有負數(shù)），求A1~An的一個子序列Ai~Aj，使得Ai到Aj的和最大。例如：整數(shù)序列2,11,4,13,5,2,5,3,12,9的最大子序列的和為21。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個。當然算法復(fù)雜度會達到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個算法復(fù)雜度為O(n)的線性算法實現(xiàn)，算法的來源于Programming Pearls一書。在給出線性算法之前，先來看一個對窮舉算法進行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。其實這個算法只是對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設(shè)Sum(i,j)是A[i]...A[j]的和，那么Sum(i,j+1) = Sum(i,j) + A[j+1]。利用這一個遞推，我們就可以得到下面這個算法：int MaxSub(int a[], int size){int i, j, v, max = a[0]。for (i = 0。 i size。 i++){v = 0。for (j = i。 j size。 j++){v = v + a[j]。// Sum(i,j+1) = Sum(i,j) + A[j+1]if (v max)max = v。}}return max。}那怎樣才能達到線性復(fù)雜度呢？這里運用動態(tài)規(guī)劃的思想。先看一下源代碼實現(xiàn)：int MaxSub2(int a[], int size){int i, max = 0, tempSum = 0。for (i = 0。 i size。 i++){tempSum += a[i]。if (tempSum max)max = tempSum。else if (tempSum 0)tempSum = 0。}return max。},并不是簡單的字符串反轉(zhuǎn)，而是按給定字符串里的單詞將字符串倒轉(zhuǎn)過來，就是說字符串里面的單詞還是保持原來的順序，這里的每個單詞用空格分開。例如：Here is
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1