數(shù)據(jù)結(jié)構(gòu)常見筆試題-文庫吧資料
2025-03-31 03:01本頁面
【正文】 對每一個單詞再反轉(zhuǎn)一次。},并不是簡單的字符串反轉(zhuǎn)，而是按給定字符串里的單詞將字符串倒轉(zhuǎn)過來，就是說字符串里面的單詞還是保持原來的順序，這里的每個單詞用空格分開。else if (tempSum 0)tempSum = 0。 i++){tempSum += a[i]。for (i = 0。}那怎樣才能達(dá)到線性復(fù)雜度呢？這里運用動態(tài)規(guī)劃的思想。// Sum(i,j+1) = Sum(i,j) + A[j+1]if (v max)max = v。 j size。 i++){v = 0。for (i = 0。假設(shè)Sum(i,j)是A[i]...A[j]的和，那么Sum(i,j+1) = Sum(i,j) + A[j+1]。在給出線性算法之前，先來看一個對窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。當(dāng)然算法復(fù)雜度會達(dá)到O(n^3)。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。}4.“最大子序列”問題：給定一整數(shù)序列A1，A2，...,An（可能有負(fù)數(shù)），求A1~An的一個子序列Ai~Aj，使得Ai到Aj的和最大。if (a[i] b[j])i++。 j size2){if (a[i] == b[j])return true。while (i size1 amp。推進(jìn)的規(guī)則是比較兩個數(shù)組中的數(shù)字，小的那個數(shù)組的下標(biāo)向前推進(jìn)一步，直到任何一個數(shù)組的下標(biāo)到達(dá)數(shù)組末尾時，如果這時還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。所以只要一次遍歷就行了。}后來發(fā)現(xiàn)有一個O(n)算法。elsestart = mid + 1。if (a[i] == b[mid])return true。 i++){int start = 0, end = size21, mid。for (i = 0。就是任意挑選一個數(shù)組，遍歷這個數(shù)組的所有元素，遍歷過程中，在另一個數(shù)組中對第一個數(shù)組中的每個元素進(jìn)行binary search。elsereturn false。 p1 != p2)。 p2next amp。} while (p2 amp。}do{p1 = p1next。bool IsLoop(Node *head){Node *p1 = head,*p2 = head。Node *next。若兩指針當(dāng)前指向的node相同，則為入口，否則各自向前走1再判斷是否相等。求環(huán)長：按照上面兩個指針不同步長步進(jìn)的方法，第一次相遇時記錄當(dāng)前指針，步長為1的指針繼續(xù)走，計數(shù)，直到再次來到記錄的指針，經(jīng)過的步數(shù)即為環(huán)長。直到p2碰到NULL指針或者兩個指針相等結(jié)束循環(huán)。設(shè)置兩個指針p1，p2。return p。tmpnext = p。return p。算法的源代碼如下：法二：LNode* Reverse(LNode *p, LinkList amp。不過，這個方法有一個缺點，就是在反轉(zhuǎn)后的最后一個結(jié)點會形成一個環(huán)，所以必須將函數(shù)返回的節(jié)點的next域置為NULL。比較}還有一種利用遞歸的方法。}headnext = NULL。pre = cur。while (cur != NULL){nex = curnext。pre = head。head = q。p = p next。head = NULL。LNode *p, *q。void Reverse(LinkList amp。LNode *next。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素，然后將當(dāng)前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。第四部分鏈表反轉(zhuǎn)（無表頭結(jié)點）單向鏈表的反轉(zhuǎn)是
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1