面試-常考的數(shù)據(jù)結(jié)構(gòu)題(參考版)
2025-06-10 22:51本頁面
【正文】 有些是直接從網(wǎng)上找的，對第一作者敬禮，感謝你們的無私奉獻(xiàn)。 cout\n。i7。 BubbleSort(data,7)。 pData[j] = iTemp。j) { if(pData[j]pData[j1]) { iTemp = pData[j1]。i++) { for(int j=Count1。 for(int i=1。 return p1。amp。 p2=p2nextnext。 p1=p1next。 return head。 p1=p2=head。當(dāng)p2到達(dá)鏈表的末尾時(shí)，p1指向的時(shí)鏈表的中間。設(shè)置兩個(gè)指針p1，p2。這樣一趟掃描結(jié)果也就出來了。如果temp_sum降到0時(shí)，說明前面已經(jīng)掃描的那一段就可以拋棄了，這時(shí)將temp_sum置為0。如果往前掃描中遇到負(fù)數(shù)，那么當(dāng)前子序列的和將會減小。 return max。 } {i++) for(i=0。}那怎樣才能達(dá)到線性復(fù)雜度呢？這里運(yùn)用動(dòng)態(tài)規(guī)劃的思想。 if(vmax)//Sum(i, j+1) = Sum(i, j) + A[j+1]j++) for(j=i。 v=0。isize。 int i,j,v,max=a[0]。利用這一個(gè)遞推，我們就可以得到下面這個(gè)算法： int max_sub(int a[],int size){其實(shí)這個(gè)算法只是對對窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線性算法實(shí)現(xiàn)，算法的來源于Programming Pearls一書。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。}4,最大子序列 問題：給定一整數(shù)序列A1， A2，... An （可能有負(fù)數(shù)），求A1~An的一個(gè)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1