數(shù)據(jù)結(jié)構(gòu)常見筆試題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 一個(gè)數(shù)組中對第一個(gè)數(shù)組中的每個(gè)元素進(jìn)行binary search。用C++實(shí)現(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)有一個(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 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（可能有負(fù)數(shù)），求A1~An的一個(gè)子序列Ai~Aj，使得Ai到Aj的和最大。例如：整數(shù)序列2,11,4,13,5,2,5,3,12,9的最大子序列的和為21。對于這個(gè)問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線性算法實(shí)現(xiàn)，算法的來源于Programming Pearls一書。在給出線性算法之前，先來看一個(gè)對窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。其實(shí)這個(gè)算法只是對窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。假設(shè)Sum(i,j)是A[i]...A[j]的和，那么Sum(i,j+1) = Sum(i,j) + A[j+1]。利用這一個(gè)遞推，我們就可以得到下面這個(gè)算法：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。}那怎樣才能達(dá)到線性復(fù)雜度呢？這里運(yùn)用動(dòng)態(tài)規(guī)劃的思想。先看一下源代碼實(shí)現(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)過來，就是說字符串里面的單詞還是保持原來的順序，這里的每個(gè)單詞用空格分開。例如：Here is
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1