還有幾天就打藍橋杯了, 這里就記錄一下個人備賽訓練中學到的算法小寄巧~?這里只是基于個人的總結, 看完之后不一定能拿獎。。。當然結果啥的并不重要, 重要的是學到的算法思路和優(yōu)化的技巧, 幫助你在日后寫出更優(yōu)美高效的代碼。

目錄:

* 圖論

* 二分搜索

* 前綴和與差分

* 并查集

圖論

圖論里面最經(jīng)典的問題就是最短路徑了, 求最短路徑的兩種算法思想, 一種是基于貪心算法的dijkstra, 另外一種是基于動態(tài)規(guī)劃的 Floyd 和 Bellman-ford。

dijkstra 的算法過程:

dijkstra一般用來解決單源最短路徑問題(邊權一定要為正數(shù)), 首先我們定義一個數(shù)組 dist, 然后我們再定義一個集合 S, 我們首先把源點的距離(dist數(shù)組)設置為 0 然后放入集合 S 中.

之后我們在 集合 S 中 找到一個沒有訪問過且 dist最小的一個節(jié)點, 對這個節(jié)點進行松弛操作并更新 dist 數(shù)組, 最后標記為已訪問過。

重復以上過程 n - 1 次。

經(jīng)典模板題:

https://www.lanqiao.cn/problems/1460/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B7%AF%E5%BE%84

Bell-ford實際上是動態(tài)規(guī)劃, 我們定義 dp 方程:

dp[i][j]： 在第 i 步內(nèi)到達 節(jié)點 j 的最短路徑.

其中 j 是 v 的某一條鄰邊, 定義?cost(v, j) 為v 到 j 的路徑:

dp[i][j] = min(dp[i][j], dp[i - 1][v] + cost(v, j))

我們可以對其進行狀態(tài)壓縮:

dp[j] = min(dp[j], dp[v] + cost(v, j)

于是我們發(fā)現(xiàn)這不就是松弛操作嗎?

那么就相當于對每條邊進行松弛操作, 所以說 Bellman-ford 更像是暴力法, 時間復雜度會比 Djikstra高:

二分搜索

對于二分查找如果我們要找某個元素是否在一個數(shù)組中, 這很容易實現(xiàn)。但一般問題需要在數(shù)組查找滿足條件的某個區(qū)間的左端點或者右端點, 這時候就要注意好循環(huán)時更新區(qū)間的細節(jié)，不然很容易出現(xiàn)死循環(huán)。

當我們要獲取滿足條件的左端點時:?

列如：在升序數(shù)組中找到第一個不小于target的索引：

nums = [5,7,7,8,8,10], target = 8; ans = 3;

對于這個問題我們不要死記硬背, 我們來直觀地理解一下:

當 arr[mid] < val 時, 我們才會更新 left， 我們已上面為例子, 那么會出現(xiàn)兩種情況:

1. 當 mid 取到索引 2 時, 此時元素是 7, 那么l = mid + 1 = 3， 之后我們只會更新 r, 當出現(xiàn) l = r - 1時, 我們更新 mid = (l + r) >> 1 (向下取整), 那么最后的 l 是 3。 (證明了此時答案為左端點)

索引: 0? 1? 2? 3? 4???5

元素: 5? 7? 7? 8? 8? 10

2.?當?mid 沒有取到索引 2 時, 此時我們的 l 最終一定會落在索引 2, r 會落在索引3, 此時我們更新 mid = (l + r) >> 1 (向下取整), 此時 mid = 2, l = mid + 1 = 3, 那么最后的 l 是 3。 (證明了此時答案也為左端點)

索引:?0??1? 2? 3??4???5

元素:?5??7??7??8??8??10

當我們要獲取滿足條件的右端點時:

列如：在升序數(shù)組中找到最后一個不大于target的索引。

nums = [5,7,7,8,8,10], target = 8; ans = 4;

證明和上面的一樣。。。此時 mid = (l + r + 1) >> 1 為向上取整了, 所以取得了右端點.

當然，也可以這樣理解：?

當我們要取左端點時(對應上面的第一種), 我們滿足條件了那么 r = mid 說明我們不再往>r的方向找了, 沒滿足條件我們就使得 l = mid + 1繼續(xù)搜索。

當我們要取右端點時(對應上面的第二種), 我們滿足條件那么 l = mid 繼續(xù)搜索直到獲取到滿足條件的最大下標, 沒滿足條件我們就使得 r = mid - 1 繼續(xù)搜索.

例題:

1.分巧克力：

前綴和與差分

一維前綴和

預處理出s[]，s[i]存儲前i個數(shù)的和:

計算[l,r]區(qū)間和:

二維前綴和

左上角坐標為(1,1)，右下角坐標為(i,j)的前綴和（區(qū)域內(nèi)所有數(shù)的和）

求左上角坐標為(x1,y1)，右下角坐標為(x2,y2)的前綴和

例題: 統(tǒng)計子矩陣

給定一個?N×M?的矩陣?A, 請你統(tǒng)計有多少個子矩陣 (最小?1×1, 最大N×M)?滿足子矩陣中所有數(shù)的和不超過給定的整數(shù)?K??

一維差分

二維差分

并查集

并查集是一種優(yōu)美的數(shù)據(jù)結構, 在之前的 leetcode 題解中介紹過:

leetcode賽后補題: 322周賽題解 - 嗶哩嗶哩 (bilibili.com)

例題: 七段碼:

https://www.lanqiao.cn/problems/595/learning/

我們首先建圖, 然后只需要dfs枚舉出所有的亮燈情況, 判斷亮燈的部分是否是一個連通塊即可: