中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

做網(wǎng)站空間500m多少錢推廣下載app賺錢

做網(wǎng)站空間500m多少錢,推廣下載app賺錢,百度站長工具大全,微商城官網(wǎng)登錄截圖摘自湖南大學彭鵬老師的ppt。筆記也是根據(jù)他的ppt整理的。 動態(tài)規(guī)劃 核心 用數(shù)組記錄中間結(jié)果,避免重復(fù)計算 三角數(shù)塔問題 問題描述 給定一個三角形數(shù)塔,從頂部出發(fā),每次只能移動到下一行的相鄰元素。要求找到一條路徑,…

截圖摘自湖南大學彭鵬老師的ppt。筆記也是根據(jù)他的ppt整理的。

動態(tài)規(guī)劃

核心

用數(shù)組記錄中間結(jié)果,避免重復(fù)計算

三角數(shù)塔問題

問題描述

給定一個三角形數(shù)塔,從頂部出發(fā),每次只能移動到下一行的相鄰元素。要求找到一條路徑,使得路徑上的數(shù)字和最大。

假設(shè)有一個三角形數(shù)塔,如下所示:

    37 42 4 68 5 9 3

dp數(shù)組 dp[i][j]表示以matrix[i][j]為結(jié)尾的,最大路徑的和

    310 712 14 1320 19 23 16

最后結(jié)果是23

解題思路

dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];

偽代碼


int max_value(vector<vector<int>> &matrix ){vector<vector<int>> dp(matrix.size(),vector<int>(matrix.size()));dp[0][0] = matrix[0][0];for(int i=1;i<matrix.size();i++){dp[i][0] = dp[i-1][0] + matrix[i][0]; // 最左邊的for(int j=1;j<i;j++){// 中間的dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + matrix[i][j];}// 最右邊的dp[i][i] = dp[i-1][i-1] + matrix[i][i];}return max(dp.back().begin(),dp.back().end());    
};

復(fù)雜度分析

時間復(fù)雜度:O(n^2),其中 n 是三角形的行數(shù)。
空間復(fù)雜度:O(n^2),其中 n 是三角形的行數(shù)。

最大字段和

問題描述

給定由n個整數(shù)(可能有負整數(shù))組成的序列(a1, a2, …, an),最大子段和問題要求該序列形如 的最大值(1≤i≤j≤n),當序列中所有整數(shù)均為負整數(shù)時,其最大子段和為0。

示例

例如,序列(-20,11,-4,13, -5, -2)的最大子段和為 a2+a3+a4=20 。

dp[i]表示以a[i]開頭的,從a[i]–>a.back()的最大子段和

dp數(shù)組

dp[i] = max(dp[i+1]+a[i],a[i]);

123456
a-2011-413-5-2
dp020913-5-2

所以最后答案是20

// 注意是后序
int max_sub_array(vector<int> &a){int n = a.size();vector<int> dp(n);dp.back() = a.back();int max_sum = a[0];for(int i=n-2;i>=0;i--){dp[i] = max(dp[i+1]+a[i],a[i]);max_sum = max(max_sum,dp[i]);}return max_sum;
}

復(fù)雜度分析

時間復(fù)雜度:O(n),其中 n 是序列的長度。
空間復(fù)雜度:O(n),其中 n 是序列的長度。

最長公共子序列

問題描述

給定兩個字符串str1和str2,返回兩個字符串的最長公共子序列(LCS)。

子序列是指從原字符串中刪除若干個字符后,不改變剩余字符順序得到的字符串。最長公共子序列是兩個字符串所共同擁有的最長子序列。

例如,對于字符串"abcde"和"ace",最長公共子序列是"ace",因此長度為3。

示例

abcbdab
bdcaba

dp[i][j]表示str1[0:i]和str2[0:j]的最長公共子序列長度

startabcbdab
start00000000
b00111111
d00111222
c00122222
a01122233
b01223334
a01223344

所以最后答案是4 bdab

代碼

int longest_common_subsequence(string &str1,string &str2){int n = str1.size();int m = str2.size();vector<vector<int>> dp(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}return dp[n][m];
}

復(fù)雜度分析

時間復(fù)雜度:O(nm),其中 n 和 m 分別是字符串 str1 和 str2 的長度。
空間復(fù)雜度:O(n
m),其中 n 和 m 分別是字符串 str1 和 str2 的長度。

01背包問題

問題描述

給定 n 種物品和一個容量為 w 的背包,每種物品都只有一件可用。第 i 種物品的體積是 vi,價值是 wi。求解將哪些物品裝入背包,可使這些物品的總體積不超過背包容量,且總價值最大。輸出最大價值。

示例

number=4 capacity=8

i1234
s (weight)2345
v (value)3456

dp數(shù)組

dp[i][j]表示,在總?cè)萘繛閖的情況下,在0~i個物品中,能獲得的最大價值。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-s[i]]+v[i])

012345678
1003333333
2003447777
3003447899
40034478910

代碼

int max_value_in_knapsack(vector<int> &s,vector<int> &v,int capacity){int n = s.size();vector<vector<int>> dp(n+1,vector<int>(capacity+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=capacity;j++){if(j>=s[i-1]){dp[i][j] = max(dp[i-1][j],dp[i-1][j-s[i-1]]+v[i-1]);}else{dp[i][j] = dp[i-1][j];}}}return dp[n][capacity];
}

復(fù)雜度分析

時間復(fù)雜度:O(nm),其中 n 和 m 分別是物品的數(shù)量和背包容積。
空間復(fù)雜度:O(n
m),其中 n 和 m 分別是物品的數(shù)量和背包容積。

貪心算法

選取局部最優(yōu)解

優(yōu)缺點

  • 優(yōu)點:速度快,復(fù)雜度低
  • 缺點:需要證明是最優(yōu)解

活動選擇問題

問題描述

假設(shè)我們存在這樣一個活動集合S={a1,a2,a3,a4,…,an},其中每一個活動ai都有一個開始時間si和結(jié)束時間fi保證(0≤si<fi),活動ai進行時,那么它占用的時間為[si,fi),現(xiàn)在這些活動占用一個共同的資源(教室),就是這些活動會在某一時間段里面進行安排,如果兩個活動ai和aj的占用時間[si,fi),[sj,fj)不重疊,那么就說明這兩個活動是兼容的,也就是說當sj>=fi或者si>=fj那么活動ai,aj是兼容的。在活動選擇問題中,我們希望選出一個最大兼容活動集,即在同一間教室能安排數(shù)量最多的活動。

貪心策略

按照結(jié)束時間前的,放前面;結(jié)束時間一樣的,開始時間小的放前面,然后依次相加

貪心證明

貪心的結(jié)果集是S, 剩下的集合是T,對于T中的任意一個元素b,都存在一個a屬于S, 是a的結(jié)束時間大于b的開始時間。

在這里插入圖片描述

代碼

static bool cmp (const vector<int>&a, const vector<int>&b){return a[1]<b[1];}
int eraseOverlapIntervals(vector<vector<int>>& vct) {sort(vct.begin(),vct.end(),cmp);int endtime=vct.front()[1];int res=1;for(int i=1;i<vct.size();i++){if(endtime > vct[i][0]){}else{endtime=vct[i][1];res++;}}return res;}

建議

碰到這種問題,用動態(tài)規(guī)劃也能做,而且如果對應(yīng)的活動有權(quán)值,動態(tài)規(guī)劃還一定是正確的。

  1. 對任務(wù)按照結(jié)束時間排序
  2. dp[i][j] i表示從0~i個任務(wù),j表示空余時間,dp[i][j]表示最大解

哈夫曼編碼

問題描述

給定一個由n個不同字符組成的字符串,請設(shè)計一個哈夫曼編碼,使得使用該編碼的編碼長度最小。

哈夫曼樹

  • 定義:給定n個權(quán)值作為n個葉子結(jié)點的權(quán)值,構(gòu)造一棵二叉樹,若該樹的帶權(quán)路徑長度達到最小,稱這樣的二叉樹為最優(yōu)二叉樹,也稱為哈夫曼樹(Huffman Tree)。

解法

  • 統(tǒng)計待編碼字符串中每個字符出現(xiàn)的次數(shù),并將這些次數(shù)作為權(quán)重存儲在數(shù)組中。
  • 根據(jù)權(quán)重構(gòu)建哈夫曼樹。在構(gòu)建過程中,每次從權(quán)重數(shù)組中取出兩個最小的權(quán)重,將它們合并為一個新節(jié)點,新節(jié)點的權(quán)重為這兩個節(jié)點權(quán)重之和。然后將新節(jié)點加入哈夫曼樹,同時從權(quán)重數(shù)組中刪除這兩個節(jié)點。重復(fù)這個過程,直到權(quán)重數(shù)組為空。
  • 根據(jù)哈夫曼樹生成哈夫曼編碼。對于哈夫曼樹的每個葉子節(jié)點,從根節(jié)點到葉子節(jié)點的路徑上的每個節(jié)點對應(yīng)一個0或1,將這些0和1按照從根節(jié)點到葉子節(jié)點的順序連接起來,就得到了該葉子節(jié)點的哈夫曼編碼。
  • 使用哈夫曼編碼對字符串進行編碼。將字符串中的每個字符替換為其哈夫曼編碼,然后將編碼后的字符串按照哈夫曼編碼的規(guī)則進行傳輸或存儲。

最小延遲調(diào)度問題

問題描述

任務(wù)集合S,?i∈S,di 為截止時間,ti為加工時間,di , ti為正整數(shù)。一個調(diào)度f : S→N,f(i)為任務(wù)i 的開始時間。求最大延遲達到最小的調(diào)度,就是所有任務(wù)超過截止時間的和最小。

在這里插入圖片描述

解決方案

按照結(jié)束時間di從小到大排序,安排時不留空余時間

貪心證明

最優(yōu)解中可以不存在相鄰的逆序任務(wù),使得(i,j): f(i) < f(j) di > dj。 (真確解中,交換兩個任意的任務(wù),都會使得總?cè)蝿?wù)拖延時間變長)。

找零問題

問題描述

考慮用最少的硬幣找n美分零錢的問題。假設(shè)每種硬幣的面額都是整數(shù)。設(shè)計貪心算法求解找零問題,假定有25美分、10美分、5美分和1美分4種面額的硬幣。證明你的算法能找到最優(yōu)解。

解決方案

按照先盡可能用25美分,然后盡可能用10美分,再盡可能用5美分,最后盡可能用1美分。

貪心證明

假設(shè)一個可能的解中,存在兩個10,一個5,則可以用25代替,獲取到一個更優(yōu)解。同樣遞歸,直到?jīng)]有硬幣組合能到25,對應(yīng)著先用25美分的。

圖基本算法

廣度優(yōu)先搜索

算法步驟

廣度優(yōu)先搜索(BFS,Breadth First Search),從初始點開始,逐層向前搜索,即第n層搜索未完成,不得進入下一層搜索。

深度優(yōu)先搜索

算法步驟

深度優(yōu)先搜索(DFS,Depth First Search),從初始點開始,對每一個可能的分支路徑深入到不能再深入為止,而且每個節(jié)點只能訪問一次

歐拉回路

判定條件

對于圖上的任意節(jié)點,入度等于出度。

DFS解法

  • 從任意一個起始點v開始DFS遍歷,直到再次到達點v,即尋找一個回路。
  • 將此回路定義為C,如果回路C中存在某個點x,其有出邊不在回路中,則繼續(xù)以此點x開始遍歷尋找回路C’,將環(huán)C、C’連接起來也是一個大回路,如此往復(fù),直到圖G中所有的邊均已經(jīng)添加到回路中
  • 顯然每條邊只會返回一次,所以復(fù)雜度為O(E)

用人話說就是:

  1. 對任意一個節(jié)點A做DFS, 直到終點到了A,對遍歷的邊進行標記,把所有遍歷的邊去除。
  2. 對任意一個還有邊的點B進行DFS,重復(fù)操作,直到所有邊都被標記。
  3. 標記的邊就是歐拉回路。

拓撲排序

算法步驟

  1. 找到所有入度為0的節(jié)點,并加入隊列
  2. 依次從隊列中取出節(jié)點,并將其指向的節(jié)點的入度減1,如果減1后,該節(jié)點的入度為0,則將其加入隊列

最小生成樹

把所有點都連接起來,使得生成樹各邊權(quán)值之和最小。

prim算法

算法步驟

  1. 選擇一個節(jié)點作為起始點,并將其加入生成樹中。
  2. 選擇與生成樹相連的,最小的邊,將其加入生成樹中。
  3. 重復(fù)步驟2,直到所有節(jié)點都被加入生成樹中。
    在這里插入圖片描述

復(fù)雜度

  • 使用鄰接矩陣表示圖: O(V^2) V是頂點數(shù)量,每次都要找最小的頂點
  • 使用鄰接表表示圖: O(ElogV) E是邊的數(shù)量,每次都要找最小的頂點
    (加入新節(jié)點的時候,把新節(jié)點所有相鄰的,不在生成樹中的邊添加進去)

Kruskal算法

算法步驟

  1. 按照邊的權(quán)值從小到大排序
  2. 依次選擇邊,如果選擇后不會形成環(huán),則加入生成樹中(使用并查集判斷新加入的邊是否會形成環(huán))

瓶頸生成樹

定義

一個無向圖G上的瓶頸生成樹是G上一種特殊的生成樹。一個瓶頸生成樹T上權(quán)重最大邊的權(quán)重是G中所有生成樹中最小的。T上最大權(quán)重的邊的權(quán)重稱為T的值。 就是生成樹T,的最大權(quán)值,是G中所有生成樹中,最大權(quán)值的最小值。

單源最短路徑

松弛算法

在這里插入圖片描述

說人話就是,對于點u --> v , 如果找到另外一個點x,使得u --> x --> v的路徑更短,則更新u --> v的路徑。后面的Dijkstra算法Bellman-Ford算法是基于這個算法的。

Dijkstra算法

算法步驟

  1. 創(chuàng)建一個距離列表,其中包含每個節(jié)點到起始節(jié)點的距離。起始節(jié)點的距離設(shè)置為0,其他節(jié)點的距離設(shè)置為無窮大。

  2. 創(chuàng)建一個已訪問列表和一個待訪問列表。起始節(jié)點被標記為已訪問,其他所有節(jié)點都被標記為待訪問。

  3. 對于每一個待訪問的節(jié)點,計算它到起始節(jié)點的距離。如果這個距離比當前記錄的距離還要短,那么就更新這個節(jié)點的距離。

  4. 從待訪問列表中找到距離最小的節(jié)點,將其標記為已訪問,并將其從待訪問列表中移除。

  5. 重復(fù)步驟3和4,直到所有的節(jié)點都被訪問過。

  6. 距離列表中記錄的就是每個節(jié)點到起始節(jié)點的最短距離。

缺點

無法解決邊值為負值

Bellman-Ford算法

算法步驟

  1. 為每個頂點 ’ v '初始化距離數(shù)組 dist[]為dist[v] = INFINITY。假設(shè)任何頂點(假設(shè)為“0”)作為源并分配dist = 0。
  2. 根據(jù)以下條件放松所有edges(u,v,weight)N-1次:
    • dist[v] = 最小值(dist[v],dist[u] + weight)
  3. 現(xiàn)在,再次放松所有邊,即第N次,并基于以下兩種情況,我們可以檢測負循環(huán):
    • 情況 1(存在負循環(huán)):對于任何邊(u,v,權(quán)重),如果 dist[u] + weight < dist[v]
    • 情況 2(無負循環(huán)):情況 1 對于所有邊均失敗。

證明

N-1次可以求出最小路徑

Bellman-ford算法思想是,進行一次遍歷,遍歷所有邊,一次一定能找到一個距離start節(jié)點最近的點,N-1次之后,target節(jié)點最多和start節(jié)點之間有N-2個節(jié)點

N次距離減少,出現(xiàn)負循環(huán)回路

負權(quán)重的邊又被遍歷了一次

主定理

將規(guī)模為n的問題轉(zhuǎn)化為a個規(guī)模為n/b的問題,花費的時間是O( n d n^d nd)
T(n)= a ? T ( n b ) + n d a*T(\frac{n})+n^d a?T(bn?)+nd, 其中a>1 , b>1 , d>0

  • 當 a < b d b^d bd , T(n)=O( n d n^d nd)
  • 當 a = b d b^d bd , T(n)=O( n l o g b a ? l g n n^{log_ a}*lgn nlogb?a?lgn)
  • 當 a > b^d , T(n)=O( n l o g b a n^{log_ a} nlogb?a)

不想推導(dǎo),直接記住吧

例子

二分查找

  • T(n)= 2 T ( n 2 ) + 1 2T(\frac{n}{2})+1 2T(2n?)+1
  • a=2 b=2 d=0 --> O(n)

歸并排序合并

  • T(n)= 2 T ( n 2 ) + n 2T(\frac{n}{2})+n 2T(2n?)+n
  • a=2 b=2 d=1 --> O(n*lgn)

遞歸式子

  • T(n)= 3 T ( n 4 ) + n l g n 3T(\frac{n}{4})+nlg{n} 3T(4n?)+nlgn
  • a=3 b=4 d約為1.5 --> O(n*lgn)

紅黑樹

定義

  1. 每個節(jié)點要么是黑色,要么是紅色;
  2. 根和葉子都是黑色的,所有的葉子都是NIL;
  3. 紅色節(jié)點的父節(jié)點是黑色的;
  4. 從節(jié)點x到其所有后代葉子節(jié)點的所有路徑中包含相同數(shù)量
    的黑節(jié)點。
http://www.risenshineclean.com/news/54769.html

相關(guān)文章:

  • 網(wǎng)站開發(fā)報價明細營銷推廣的公司
  • 杭州十大室內(nèi)設(shè)計公司網(wǎng)站關(guān)鍵詞優(yōu)化方法
  • 公司網(wǎng)站怎么做站外鏈接濟南seo外包公司
  • 做網(wǎng)站推廣客服好做么百度地址
  • 去菲律賓做網(wǎng)站百度seo標題優(yōu)化軟件
  • 大連城建設(shè)計研究院網(wǎng)站南昌seo顧問
  • 天津校園文化設(shè)計公司湖南網(wǎng)站建設(shè)推廣優(yōu)化
  • 中國做美國酒店的網(wǎng)站制作網(wǎng)站公司
  • 廣州黃埔區(qū)網(wǎng)站建設(shè)北京seo網(wǎng)站優(yōu)化公司
  • 做網(wǎng)站郴州百度信息流效果怎么樣
  • 涪城移動網(wǎng)站建設(shè)免費推廣網(wǎng)站注冊入口
  • 做自己的購物網(wǎng)站網(wǎng)站推廣要點
  • 日照手機網(wǎng)站設(shè)計小學生抄寫新聞20字
  • 河南做網(wǎng)站公司排名sem代運營托管公司
  • 微信高端網(wǎng)站建設(shè)百度愛采購平臺官網(wǎng)
  • 徐州企業(yè)網(wǎng)站排名優(yōu)化官網(wǎng)百度
  • 深圳品牌模板網(wǎng)站建設(shè)百度推廣助手怎么用
  • 扁平化 手機網(wǎng)站首頁5118大數(shù)據(jù)平臺官網(wǎng)
  • wordpress固定鏈自定義結(jié)構(gòu)企業(yè)關(guān)鍵詞優(yōu)化最新報價
  • 公司個人怎么做網(wǎng)絡(luò)推廣seo建站工具
  • 青島做網(wǎng)站方案網(wǎng)上營銷培訓課程
  • 蕪湖做網(wǎng)站哪家好網(wǎng)站流量分析工具
  • 怎么在國外網(wǎng)站做推廣百度推廣的幾種方式
  • 重慶江北區(qū)網(wǎng)站建設(shè)公司seo網(wǎng)絡(luò)推廣是什么意思
  • 個人網(wǎng)站做公司網(wǎng)站企業(yè)網(wǎng)絡(luò)營銷案例
  • 秦皇島海三建設(shè)沒錢了奉化seo頁面優(yōu)化外包
  • wordpress做物流網(wǎng)站百度搜索引擎的特點
  • 給人做網(wǎng)站多少錢張掖seo
  • 濰坊地區(qū)網(wǎng)站制作免費輿情監(jiān)測平臺
  • wordpress 文章推薦一篇福建優(yōu)化seo