本文純粹是出自學(xué)習(xí)目的，根據(jù)個人理解屏歹，將文章進(jìn)行了部分編排與修改隐砸。如侵權(quán)，請聯(lián)系刪除蝙眶。
------@2017/04/19------
程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法
先有數(shù)據(jù)季希，再有算法。所以在設(shè)計時幽纷，都是以數(shù)據(jù)結(jié)構(gòu)為出發(fā)點(diǎn)進(jìn)行設(shè)計的式塌。
另一方面，如果有了具體的算法友浸，也可根據(jù)具體情況對數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn)峰尝。
Set: 將一對散亂的東西存放在一個容器里
(原文此處有圖，省略...)
然而數(shù)據(jù)本身是沒有順序的收恢，如何保持順序關(guān)系武学？
方法 1：array，將數(shù)據(jù)連續(xù)有序的排成一排
(原文此處有圖伦意，省略...)
方法 2：linkedlist火窒，將各個數(shù)據(jù)之間用指針連接
數(shù)據(jù)存好以后，就來到了問題的核心部分：如何處理這些數(shù)據(jù)驮肉？算法
怎么計算這些數(shù)據(jù)就是算法部分所關(guān)注的內(nèi)容熏矿。同一對數(shù)據(jù)(相同的 input)，根據(jù)不同需求，要求得到不同的處理結(jié)果(output)曲掰，那么我們就會使用不同的算法疾捍。
個人理解，算法就是處理計算數(shù)據(jù)的具體方法栏妖。課本中學(xué)到的各種排序算法乱豆，貪心，動態(tài)規(guī)劃算法吊趾，都是別人的研究結(jié)果宛裕，可供直接使用。
最簡單的離自己论泛，要排序一堆數(shù)據(jù)揩尸，常用的就是 merge sort, quick sort 等。具體情況具體分析屁奏，各種算法各有優(yōu)劣岩榆。其他的大致都在這個框架里，就像現(xiàn)在的流行語：** 這坟瓢，都是套路 **勇边。
但是，如果能把每個算法深入學(xué)習(xí)理解折联，還是可以從中學(xué)到很多思考以及解決問題的方法粒褒。
舉個具體算法的例子：如何判斷某些數(shù)據(jù)是否存在？
好比你要在一堆人里面诚镰，找出某一個人奕坟，那么我們一般會使用排查的方法，一個一個的挨著找清笨。
對數(shù)據(jù)也是一樣的道理月杉，就是挨個排查搜索，遍歷函筋。
問題是沙合，我們?nèi)绾渭铀俨檎夷兀?/p>
生活中的例子
繼續(xù)用上面找人的例子奠伪，如果你知道要找的目標(biāo)的身高跌帐，那么讓所有人按照：從左到右，從矮到高順序依次排列绊率。
你可以先尋問谨敛，站在最中間的人的身高。如果他比你要找的人高滤否，那么你的目標(biāo)一定在此人的左邊脸狸，此人右邊的所有人都可排除掉了。
反之亦然，每次的搜索規(guī)模就能減小一般炊甲，大大的節(jié)約了搜索時間泥彤。
計算機(jī)中的數(shù)據(jù)例子
對于數(shù)據(jù)，是同樣的道理卿啡。如果數(shù)據(jù)已排序吟吝，那么每次可以從有效區(qū)間的中間點(diǎn)，開始查找颈娜。如果正好等于要找的元素剑逃，直接返回。若小于要查找的元素官辽，則有效區(qū)間可以縮小為該中間點(diǎn)的左邊蛹磺，反之中間點(diǎn)的右邊。
這種方法是一種確定性貪心同仆。
(原文此處有圖萤捆，省略...)
這種算法，可以由兩種不同的底層數(shù)據(jù)結(jié)構(gòu)來支持：array 和 binary search tree.
如何快速判斷 5 是否在其中俗批？
二叉搜索樹
(原文此處有圖鳖轰，省略...)
另外一個有趣的算法問題就是，如何遍歷整個 Tree?
方法 1：DFS
方法 2：BFS
知識整合
算法題：input - 一個有向圖; output - 從頭部到葉子的最小路徑;
(原文此處有圖扶镀，省略...)
每個點(diǎn)蕴侣，記錄一個值 distance 代表，從根節(jié)點(diǎn)到達(dá)該點(diǎn)的最短距離臭觉，從可達(dá)到它的所有路徑中昆雀，選擇最短的路徑長度。
以圖中 2 點(diǎn)為例蝠筑，分別可以從 3 和 5 達(dá)到它狞膘，distance(2) = min(distance(3)), distance(5)) + 2.
這就是我們常說的動態(tài)規(guī)劃 (DP)：由上一層的答案推導(dǎo)出下一層的答案，即 k + 1層答案是由 k 層答案得到的什乙。
動態(tài)規(guī)劃一共做了三件事：
- 解(將挽封？)空間轉(zhuǎn)換
以上題為例，每個點(diǎn)臣镣，除了它原本的數(shù)據(jù)值辅愿，還多存了一個額外的值 distance。此時忆某，每個點(diǎn)的語義就和原來的語義有所不同点待。
BFS
貪心：確定性貪心
