1.引言——什么是算法
- 算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。
一大段話可能看起來很空洞或者可以說是乏味和枯燥。簡(jiǎn)單來說算法其實(shí)就是一個(gè)提出問題和解決問題的過程。如下圖所示，這是洛谷的一道題目，可以說是最最基礎(chǔ)的一道題，由此我們可以看到一道完整的算法題應(yīng)當(dāng)會(huì)以什么樣的方式呈現(xiàn)。A+B是小學(xué)一年級(jí)學(xué)習(xí)的加法內(nèi)容，但如何將我們熟悉的東西用程序設(shè)計(jì)語言的方式展現(xiàn)，
其實(shí)就是學(xué)習(xí)算法一直需要面對(duì)的一個(gè)問題，對(duì)于較大的數(shù)據(jù)，又該如何處理，也是我們一直需要去解決的問題之一。
下面給大家介紹三個(gè)常用的在線判題系統(tǒng)OJ（Online Judge）：
- 洛谷：https://www.luogu.com.cn/
- ?？停?a target="_blank">https://ac.nowcoder.com/acm/home
- AcWing：https://www.acwing.com/about/
下方為洛谷測(cè)評(píng)狀態(tài)示意圖：
后續(xù)我們可能會(huì)參加ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ICPC）、中國大學(xué)生程序設(shè)計(jì)競(jìng)賽（CCPC）、藍(lán)橋杯程序設(shè)計(jì)大賽、中國高校計(jì)算機(jī)大賽——團(tuán)體程序設(shè)計(jì)天梯賽等等。
2.基礎(chǔ)算法
一棟大樓并非平地而起，地基的搭建往往是建造一棟樓最艱難的時(shí)刻?；A(chǔ)算法可以稱的上是整個(gè)算法學(xué)習(xí)的地基。在學(xué)習(xí)基礎(chǔ)算法時(shí)，除了對(duì)知識(shí)的理解，還有很重要的一點(diǎn)是探索個(gè)人學(xué)習(xí)算法的方式。我認(rèn)為自己現(xiàn)在還沒有找到一個(gè)適合我的學(xué)習(xí)方法，目前也仍在探索中。
下面來大致分享一些基本算法。
2.1 暴力
我接觸到的第一個(gè)算法就是暴力。暴力如同他的字面意思，就是暴力求解，可以理解成小學(xué)奧數(shù)學(xué)過的枚舉法。指的是從所有可能的解的集合中一一枚舉各元素，用題目中給定的檢驗(yàn)條件判定哪些是無用的，哪些是有用的。能使命題成立的就是答案。
該算法可以求的一些情況較少的問題的解，若問題規(guī)模太大，該算法便不適用。正如枚舉法并不是時(shí)時(shí)適用一樣，暴力也被數(shù)據(jù)和時(shí)間局限，往往數(shù)據(jù)量過大，暴力便不適用了。因此他的優(yōu)缺點(diǎn)都很明顯，簡(jiǎn)單易想，在部分題目中或某題目中的局部使用有較好的效果。但運(yùn)算量過大。對(duì)于數(shù)據(jù)量較大的題目，效率較低，當(dāng)問題規(guī)模變大時(shí)，循環(huán)的階數(shù)越大，執(zhí)行速度越慢，容易超時(shí)。
2.2 位運(yùn)算
單看每一個(gè)都很簡(jiǎn)單無非就是與（&），或（|），非（~），異或（xor)，還有一些移位計(jì)算，并沒有什么難點(diǎn)。但當(dāng)深入學(xué)習(xí)之后，了解了二進(jìn)制狀態(tài)壓縮成對(duì)變換等等，就會(huì)逐漸體會(huì)到位運(yùn)算多么重要。在后續(xù)很多算法中，我們都需要用位運(yùn)算去實(shí)現(xiàn)一個(gè)算法，例如并查集需要用到lowbit等，位運(yùn)算更像是水，一時(shí)半會(huì)兒不喝沒有什么關(guān)系，但一旦干渴的時(shí)間長了，那是性命之憂，起初可能意識(shí)不到位運(yùn)算的作用，但當(dāng)你需要用到的時(shí)候，想不起來如何使用，也就只能干瞪眼了。
2.3遞推與遞歸
一個(gè)實(shí)際問題的各種可能情況構(gòu)成的集合通常被稱為“狀態(tài)空間”，而程序的運(yùn)行則是對(duì)于狀態(tài)空間的遍歷，算法和數(shù)據(jù)結(jié)構(gòu)則通過劃分、歸納、提取、抽象來幫助提高程序遍歷狀態(tài)空間的效率。遞推和遞歸就是程序遍歷狀態(tài)空間的兩種基本方式。
對(duì)于一個(gè)待求解的問題，當(dāng)它局限在某處邊界、某個(gè)小范圍或者某種特殊情形下時(shí)，其答案往往時(shí)已知的。如果能夠?qū)⒃摻獯鸬膽?yīng)用場(chǎng)景擴(kuò)大到原問題的狀態(tài)空間，并且擴(kuò)展過程的每個(gè)步驟都具有相似性，就可以考慮遞推或遞歸求解。以已知的“問題邊界”為起點(diǎn)向“原問題”正向推導(dǎo)的擴(kuò)展方式就是遞推。
2.4前綴和和差分
前綴和是一種重要的預(yù)處理，能大大降低查詢的時(shí)間復(fù)雜度。
根據(jù)下面兩張圖，相信大家一定能對(duì)一維和二維前綴和有一個(gè)初步理解。
前綴和和差分其實(shí)是一對(duì)互逆運(yùn)算，差分序列B的前綴和序列就是原序列A。前綴和序列S的差分序列也是原序列A。
2.5 二分
二分法是一種隨處可見卻非常精妙的算法，經(jīng)常能為我們打開問題的突破口。二分的基礎(chǔ)用法是在單調(diào)序列或單調(diào)函數(shù)中進(jìn)行查找。因此當(dāng)問題答案具有單調(diào)性時(shí)，就可以通過二分把求解轉(zhuǎn)換為判定（根據(jù)復(fù)雜度理論，判定難度小于求解），這使得二分法的運(yùn)用范圍非常廣泛。二分的實(shí)現(xiàn)方式多種多樣，但是其細(xì)節(jié)之處確實(shí)需要仔細(xì)考慮。
2.6 排序
我們經(jīng)常會(huì)用到排序算法，這里把它分成三類：
- 選擇排序、插入排序、冒泡排序
- 堆排序、歸并排序、快速排序
- 計(jì)數(shù)排序、基數(shù)排序、桶排序
前兩類是基于比較的排序算法，第三類換了一種思路，不直接比較大小，而是對(duì)被排序的數(shù)值采取按位劃分、分類映射等處理方式。
2.7 貪心
貪心是一種在每次決策時(shí)采取當(dāng)前已一下最優(yōu)策略的算法，因此使用貪心法要求所有問題的整體最優(yōu)解可以由局部最優(yōu)性導(dǎo)出。
3.數(shù)據(jù)結(jié)構(gòu)
3.1 棧
棧是一種“后進(jìn)先出”的線性數(shù)據(jù)結(jié)構(gòu)。棧只有一端能夠進(jìn)出元素，一般被稱為一端為棧頂，另一端為棧底。添加或刪除元素時(shí)，我們只能將其插入到棧頂（進(jìn)棧），或者把棧頂元素從棧中取出他（出棧）。
3.2 隊(duì)列
隊(duì)列是一種“先進(jìn)先出”的線性數(shù)據(jù)結(jié)構(gòu)，一般來講，元素從右端進(jìn)入隊(duì)列（入隊(duì)），從左端離開隊(duì)列（出隊(duì)）。于是我們稱隊(duì)列的左端為隊(duì)頭，右端為隊(duì)尾?？梢栽贑++中用一個(gè)數(shù)組和兩個(gè)變量（記錄隊(duì)頭和隊(duì)尾位置）來實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)的。
3.3 鏈表與鄰接表
數(shù)組是一種隨機(jī)訪問，但不支持在任意位置插入或刪除元素的數(shù)據(jù)結(jié)構(gòu)。與之對(duì)應(yīng)，鏈表支持在任意位置插入或刪除，但只能按順序依次訪問其中的元素。我們可以用一個(gè)struct表示鏈表的節(jié)點(diǎn)，其中可以存儲(chǔ)任意數(shù)據(jù)。另外用prev和next兩個(gè)指針指向前后相鄰的兩個(gè)節(jié)點(diǎn)，構(gòu)成一個(gè)常見的雙向鏈表結(jié)構(gòu)。為避免左右兩端或者空鏈表中訪問過界，我們通常建立額外兩個(gè)節(jié)點(diǎn)head與tail代表鏈表頭尾，把實(shí)際數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)在head和tail之間，來減少鏈表邊界處的判斷，降低編程復(fù)雜度。
3.4 Hash表
又稱為散列表，一般由Hash函數(shù)（散列函數(shù)）與鏈表結(jié)構(gòu)共同實(shí)現(xiàn)。Hash表一般包括兩個(gè)操作：
- 計(jì)算Hash函數(shù)的值
- 定位到對(duì)應(yīng)鏈表中依次遍歷比較
3.5 字符串
STL-string本質(zhì)是string是C++風(fēng)格的字符串，而string本質(zhì)上是一個(gè)類。有這樣的特點(diǎn)：string 類內(nèi)部封裝了很多成員方法。
例如：查找find、拷貝copy、刪除delete、替換replace、插入insert
string管理char*所分配的內(nèi)存，不用擔(dān)心復(fù)制越界和取值越界等，由類內(nèi)部進(jìn)行負(fù)責(zé)。
還有KMP模式匹配和最小表示法等，在此不詳細(xì)敘述了。
3.6 并查集
并查集（Disjoint-Set)是一種可以動(dòng)態(tài)維護(hù)若干個(gè)不重疊的集合，并支持合并和查詢的數(shù)據(jù)結(jié)構(gòu)。
因此，可以想到并查集包括兩個(gè)基本操作：
- Get：查詢一個(gè)元素屬于哪個(gè)集合
- Merge：把兩個(gè)集合合并成一個(gè)集合
具有非常明顯的傳遞關(guān)系的題目,或者說并查集擅長動(dòng)態(tài)維護(hù)許多具有傳遞性的關(guān)系,能在無向圖中維護(hù)節(jié)點(diǎn)之間的連通性會(huì)用到并查集。（下圖為一道并查集經(jīng)典例題配圖，判斷是否有環(huán)狀結(jié)構(gòu)）
3.7 樹狀數(shù)組
什么是樹狀數(shù)組？顧名思義，就是用數(shù)組來模擬樹形結(jié)構(gòu)。
什么問題需要用到樹狀數(shù)組？大部分基于區(qū)間上的更新以及求和問題。
4.搜索
4.1 深度優(yōu)先搜索（DFS）
深搜是一種與遞歸和棧緊密結(jié)合的算法。顧名思義就是按照深度優(yōu)先搜索的順序?qū)Α皢栴}狀態(tài)空間”進(jìn)行搜索的算法。使用遞歸實(shí)現(xiàn)的指數(shù)型、排列型和組合型枚舉。
4.2 廣度優(yōu)先搜索（BFS）
廣搜又稱為寬度優(yōu)先搜索，是一種與隊(duì)列緊密結(jié)合的算法。
5.動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃對(duì)狀態(tài)空間的遍歷構(gòu)成一張有向無環(huán)圖，遍歷順序就是該有向無環(huán)圖的一個(gè)拓?fù)湫颉Ｓ邢驘o環(huán)圖中的節(jié)點(diǎn)對(duì)應(yīng)問題中的“狀態(tài)”，圖中的邊則對(duì)應(yīng)狀態(tài)轉(zhuǎn)移的“轉(zhuǎn)移”，轉(zhuǎn)移的選取就是動(dòng)態(tài)規(guī)劃中的“決策”。在很多情況下，動(dòng)態(tài)規(guī)劃用于解決最優(yōu)化問題。
“狀態(tài)”“階段”和“決策”是構(gòu)成動(dòng)態(tài)規(guī)劃算法的三要素，而“子問題重疊性”“無后效性”和“最優(yōu)子結(jié)構(gòu)”是問題能用動(dòng)態(tài)規(guī)劃求解的三個(gè)基本條件。
6.圖論
圖論涉及的內(nèi)容廣泛，形象，實(shí)際，知識(shí)體系綜合性較強(qiáng)，還融合了之前學(xué)習(xí)的各類算法與數(shù)據(jù)結(jié)構(gòu)。個(gè)人認(rèn)為并非三言兩語就可以解釋清楚一些基本定義與概念的，故而不再詳細(xì)展開談。圖論的應(yīng)用價(jià)值非常高，一直是程序設(shè)計(jì)競(jìng)賽的重要關(guān)注點(diǎn)。
7.學(xué)習(xí)總結(jié)
上述也僅僅列出了一些常用算法，只能算是冰山一角，個(gè)人認(rèn)為算法并無難易，剛開始學(xué)并查集和樹狀數(shù)組的時(shí)候，我學(xué)了五天并查集，同一節(jié)課的視頻仔仔細(xì)細(xì)看了三遍，但還是覺得有的點(diǎn)很難理解（因?yàn)楫?dāng)時(shí)正是算法集訓(xùn)時(shí)期，我負(fù)責(zé)并查集與樹狀數(shù)組方面的授課），有一種自己依葫蘆畫瓢能寫出來，但給他人講解的話還是很含糊不清，但是當(dāng)我思考了足夠多次，很多問題就迎刃而解了。現(xiàn)在再回看備課是做過的例題以及看過的視頻，就會(huì)覺得很好理解。因此，我覺得算法和很多東西一樣，入門難，只要堅(jiān)持不懈，總有完全理解的一天。雖然本蒟蒻至今都不算完全入門，和校內(nèi)很多大佬還有很大差距，但相信堅(jiān)持一定會(huì)有收獲。
算法這項(xiàng)學(xué)習(xí)一定需要大量刷題和思考，必要時(shí)候需要借助他人力量，有很多自己一直不理解的點(diǎn)，可以嘗試去問問大佬們，他們總是會(huì)給出一些讓我們覺得非常精妙的方法。
希望大家能夠愿意嘗試接觸算法，了解算法，學(xué)習(xí)算法，即使能夠堅(jiān)持學(xué)習(xí)算法的人少之又少，但堅(jiān)持的過程本身就是一種磨練。希望大家都能夠收獲絞勁腦汁AC時(shí)的自豪，看懂大佬題解時(shí)對(duì)其絕妙算法的贊嘆！
