递歸算法#
算法策略#
遞歸算法是一種直接或者間接調用自身函數或者方法的算法。
遞歸算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。遞歸算法對解決一大類問題很有效，它可以使算法簡潔和易於理解。
優缺點：
- 優點：實現簡單易上手
- 缺點：遞歸算法對常用的算法如普通循環等，運行效率較低；並且在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲，遞歸太深，容易發生棧溢出。
適用場景#
遞歸算法一般用於解決三類問題：
- 數據的定義是按遞歸定義的。（斐波那契數列）
- 問題解法按遞歸算法實現。（回溯）
- 數據的結構形式是按遞歸定義的。（樹的遍歷，圖的搜索）
遞歸的解題策略：
- 第一步：明確你這個函數的輸入輸出，先不管函數裡面的代碼什麼，而是要先明白，你這個函數的輸入是什麼，輸出為何什麼，功能是什麼，要完成什麼樣的一件事。
- 第二步：尋找遞歸結束條件，我們需要找出什麼時候遞歸結束，之後直接把結果返回
- 第三步：明確遞歸關係式，怎麼通過各種遞歸調用來組合解決當前問題
使用遞歸算法求解的一些經典問題#
- 斐波那契數列
- 漢諾塔問題
- 樹的遍歷及相關操作
DOM 樹為例#
下面以 DOM 樹為例，實現一個 document.getElementById 功能
由於 DOM 是一棵樹，而樹的定義本身就是用的遞歸定義，所以用遞歸的方法處理樹，會非常地簡單自然。
第一步：明確你這個函數的輸入輸出
從 DOM 樹根節點一層層往下遞歸，判斷當前節點的 id 是否是我們要尋找的 id='d-cal'
輸入：DOM 樹根節點 document，我們要尋找的 id='d-cal'
輸出：返回滿足 id='sisteran' 的子結點
function getElementById(node, id){}
第二步：尋找遞歸結束條件
從 document 開始往下找，對所有子結點遞歸查找他們的子結點，一層一層地往下查找：
- 如果當前結點的 id 符合查找條件，則返回當前結點
- 如果已經到了葉子結點了還沒有找到，則返回 null
function getElementById(node, id){
// 當前結點不存在，已經到了葉子結點了還沒有找到，返回 null
if(!node) return null
// 當前結點的 id 符合查找條件，返回當前結點
if(node.id === id) return node
}
第三步：明確遞歸關係式
當前結點的 id 不符合查找條件，遞歸查找它的每一個子結點
function getElementById(node, id){
// 當前結點不存在，已經到了葉子結點了還沒有找到，返回 null
if(!node) return null
// 當前結點的 id 符合查找條件，返回當前結點
if(node.id === id) return node
// 前結點的 id 不符合查找條件，繼續查找它的每一個子結點
for(var i = 0; i < node.childNodes.length; i++){
// 遞歸查找它的每一個子結點
var found = getElementById(node.childNodes[i], id);
if(found) return found;
}
return null;
}
就這樣，我們的一個 document.getElementById 功能已經實現了：
function getElementById(node, id){
if(!node) return null;
if(node.id === id) return node;
for(var i = 0; i < node.childNodes.length; i++){
var found = getElementById(node.childNodes[i], id);
if(found) return found;
}
return null;
}
getElementById(document, "d-cal");
使用遞歸的優點是代碼簡單易懂，缺點是效率比不上非遞歸的實現。Chrome 瀏覽器的查 DOM 是使用非遞歸實現。非遞歸要怎麼實現呢？如下代碼：
function getByElementId(node, id){
//遍歷所有的Node
while(node){
if(node.id === id) return node;
node = nextElement(node);
}
return null;
}
還是依次遍歷所有的 DOM 結點，只是這一次改成一個 while 循環，函數 nextElement 負責找到下一個結點。所以關鍵在於這個 nextElement 如何實現非遞歸查找結點功能：
// 深度遍歷
function nextElement(node){
// 先判斷是否有子結點
if(node.children.length) {
// 有則返回第一個子結點
return node.children[0];
}
// 再判斷是否有相鄰結點
if(node.nextElementSibling){
// 有則返回它的下一个相鄰結點
return node.nextElementSibling;
}
// 否則，往上返回它的父結點的下一个相鄰元素，相當於上面遞歸實現裡面的for循環的i加1
while(node.parentNode){
if(node.parentNode.nextElementSibling) {
return node.parentNode.nextElementSibling;
}
node = node.parentNode;
}
return null;
}
在控制台裡面運行這段代碼，同樣也可以正確地輸出結果。不管是非遞歸還是遞歸，它們都是深度優先遍歷。 實際上 getElementById 瀏覽器是用的一個哈希 map 存儲的，根據 id 直接映射到 DOM 結點，而 getElementsByClassName 就是用的這樣的非遞歸查找。
分治算法#
算法策略#
在計算機科學中，分治算法是一個很重要的算法，快速排序、歸併排序等都是基於分治策略進行實現的，所以，建議理解掌握它。
分治，顧名思義，就是 分而治之 ，將一個複雜的問題，分成兩個或多個相似的子問題，在把子問題分成更小的子問題，直到更小的子問題可以簡單求解，求解子問題，則原問題的解則為子問題解的合併。
適用場景#
當出現滿足以下條件的問題，可以嘗試只用分治策略進行求解：
- 原始問題可以分成多個相似的子問題
- 子問題可以很簡單的求解
- 原始問題的解是子問題解的合併
- 各個子問題是相互獨立的，不包含相同的子問題
分治的解題策略：
- 第一步：分解，將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題
- 第二步：解決，解決各個子問題
- 第三步：合併，將各個子問題的解合併為原問題的解
使用分治法求解的一些經典問題#
- 二分查找
- 歸併排序
- 快速排序
- 漢諾塔問題
- React 時間分片
二分查找#
也稱折半查找算法，它是一種簡單易懂的快速查找算法。例如我隨機寫 0-100 之間的一個數字，讓你猜我寫的是什麼？你每猜一次，我就會告訴你猜的大了還是小了，直到猜中為止。
第一步：分解
每次猜拳都把上一次的結果分出大的一組和小的一組，兩組相互獨立
- 選擇數組中的中間數
function binarySearch(items, item) {
// low、mid、high將數組分成兩組
var low = 0,
high = items.length - 1,
mid = Math.floor((low+high)/2),
elem = items[mid]
// ...
}
第二步：解決子問題
查找數與中間數對比
- 比中間數低，則去中間數左邊的子數組中尋找；
- 比中間數高，則去中間數右邊的子數組中尋找；
- 相等則返回查找成功
while(low <= high) {
if(elem < item) { // 比中間數高
low = mid + 1
} else if(elem > item) { // 比中間數低
high = mid - 1
} else { // 相等
return mid
}
}
第三步：合併
function binarySearch(items, item) {
var low = 0,
high = items.length - 1,
mid, elem
while(low <= high) {
mid = Math.floor((low+high)/2)
elem = items[mid]
if(elem < item) {
low = mid + 1
} else if(elem > item) {
high = mid - 1
} else {
return mid
}
}
return -1
}
最後，二分法只能應用於數組有序的情況，如果數組無序，二分查找就不能起作用了
function binarySearch(items, item) {
// 快排
quickSort(items)
var low = 0,
high = items.length - 1,
mid, elem
while(low <= high) {
mid = Math.floor((low+high)/2)
elem = items[mid]
if(elem < item) {
low = mid + 1
} else if(elem > item) {
high = mid - 1
} else {
return mid
}
}
return -1
}
// 測試
var arr = [2,3,1,4]
binarySearch(arr, 3)
// 2
binarySearch(arr, 5)
// -1
貪心算法#
算法策略#
貪心算法，故名思義，總是做出當前的最優選擇，即期望通過局部的最優選擇獲得整體的最優選擇。
某種意義上說，貪心算法是很貪婪、很目光短淺的，它不從整體考慮，僅僅只關注當前的最大利益，所以說它做出的選擇僅僅是某種意義上的局部最優，但是貪心算法在很多問題上還是能夠拿到最優解或較優解，所以它的存在還是有意義的。
適用場景#
在日常生活中，我們使用到貪心算法的時候還是挺多的，例如：
從 100 張面值不等的鈔票中，抽出 10 張，怎樣才能獲得最多的價值？
我們只需要每次都選擇剩下的鈔票中最大的面值，最後一定拿到的就是最優解，這就是使用的貪心算法，並且最後得到了整體最優解。
但是，我們任然需要明確的是，期望通過局部的最優選擇獲得整體的最優選擇，僅僅是期望而已，也可能最終得到的結果並不一定不能是整體最優解。
那麼一般在什麼時候可以嘗試選擇使用貪心算法呢？
當滿足以下條件時，可以使用：
- 原問題複雜度過高
- 求全局最優解的數學模型難以建立或計算量過大
- 沒有太大必要一定要求出全局最優解，“比較優” 就可以
如果使用貪心算法求最優解，可以按照以下 步驟求解 ：
- 首先，我們需要明確什麼是最優解（期望）
- 然後，把問題分成多個步驟，每一步都需要滿足：
- 可行性：每一步都滿足問題的約束
- 局部最優：每一步都做出一個局部最優的選擇
- 不可取消：選擇一旦做出，在後面遇到任何情況都不可取消
- 最後，疊加所有步驟的最優解，就是全局最優解
經典案例：活動選擇問題#
使用貪心算法求解的經典問題有：
- 最小生成樹算法
- 單源最短路徑的 Dijkstra 算法
- Huffman 壓縮編碼
- 背包問題
- 活動選擇問題等
回溯算法#
算法策略#
回溯算法是一種搜索法，試探法，它會在每一步做出選擇，一旦發現這個選擇無法得到期望結果，就回溯回去，重新做出選擇。深度優先搜索利用的就是回溯算法思想。
適用場景#
回溯算法很簡單，它就是不斷的嘗試，直到拿到解。它的這種算法思想，使它通常用於解決廣度的搜索問題，即從一組可能的解中，選擇一個滿足要求的解。
使用回溯算法的經典案例#
- 深度優先搜索
- 0-1 背包問題
- 正則表達式匹配
- 八皇后
- 數獨
- 全排列
這裡以正則表達式匹配為例，介紹一下
正則表達式匹配#
var string = "abbc"
var regex = /ab{1,3}c/
console.log( string.match(regex) )
// \\["abbc", index: 0, input: "abbc", groups: undefined\\]
它的匹配過程：
在第 5 步匹配失敗，此時 b{1,3} 已經匹配到了兩個 b 正在嘗試第三個 b，結果發現接下來是 c。此時就需要回溯到上一步， b{1,3} 匹配完畢（匹配到了 bb），然後再匹配 c，匹配到了 c 匹配結束。
動態規劃#
算法策略#
動態規劃也是將複雜問題分解成小問題求解的策略，與分治算法不同的是，分治算法要求各子問題是相互獨立的，而動態規劃各子問題是相互關聯的。
所以，動態規劃適用於子問題重疊的情況，即不同的子問題具有公共的子子問題，在這種情況下，分治策略會做出很多不必要的工作，它會反復求解那些公共子子問題，而動態規劃會對每個子子問題求解一次，然後保存在表格中，如果遇到一致的問題，從表格中獲取即可，所以它無需解決每一個子子問題，避免了大量的不必要操作。
適用場景#
動態規劃適用於求解最優解問題，比如，從面額不定的 100 個硬幣中任意選取多個湊成 10 元，求怎樣選取硬幣才可以使最後選取的硬幣數最少又剛好湊夠了 10 元。這就是一個典型的動態規劃問題。它可以分成一個個子問題（每次選取硬幣），每個子問題又有公共的子子問題（選取硬幣），子問題之間相互關聯（已選取的硬幣總金額不能超過 10 元），邊界條件就是最終選取的硬幣總金額為 10 元。
針對上例，也許你也可以說，我們可以使用回溯算法，不斷的去試探，但回溯算法是使用與求解廣度的解（滿足要求的解），如果是用回溯算法，我們需要嘗試去找所有滿足條件的解，然後找到最優解，時間複雜度為 O (2^n^) ，這性能是相當差的。大多數適用於動態規劃的問題，都可以使用回溯算法，只是使用回溯算法的時間複雜度比較高而已。
最後，總結一下，我們使用動態規劃求解問題時，需要遵循以下幾個重要步驟：
- 定義子問題
- 實現需要反復執行解決的子子問題部分
- 識別並求解出邊界條件
使用動態規劃求解的一些經典問題#
- 爬樓梯問題：假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
- 背包問題：給出一些資源（有總量及價值），給一個背包（有總容量），往背包裡裝資源，目標是在背包不超過總容量的情況下，裝入更多的價值
- 硬幣找零：給出面額不定的一定數量的零錢，以及需要找零的錢數，找出有多少種找零方案
- 圖的全源最短路徑：一個圖中包含 u、v 頂點，找出從頂點 u 到頂點 v 的最短路徑
- 最長公共子序列：找出一組序列的最長公共子序列（可由另一序列刪除元素但不改變剩下元素的順序實現）
這裡以最長公共子序列為例。
爬樓梯問題#
這裡以動態規劃經典問題爬樓梯問題為例，介紹求解動態規劃問題的步驟。
第一步：定義子問題
如果用 dp[n] 表示第 n 級台階的方案數，並且由題目知：最後一步可能邁 2 個台階，也可邁 1 個台階，即第 n 級台階的方案數等於第 n-1 級台階的方案數加上第 n-2 級台階的方案數
第二步：實現需要反復執行解決的子子問題部分
dp[n] = dp[n−1] + dp[n−2]
第三步：識別並求解出邊界條件
// 第 0 級 1 種方案
dp[0]=1
// 第 1 級也是 1 種方案
dp[1]=1
最後一步：把尾碼翻譯成代碼，處理一些邊界情況
let climbStairs = function(n) {
let dp = [1, 1]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
複雜度分析：
- 時間複雜度：O (n)
- 空間複雜度：O (n)
優化空間複雜度：
let climbStairs = function(n) {
let res = 1, n1 = 1, n2 = 1
for(let i = 2; i <= n; i++) {
res = n1 + n2
n1 = n2
n2 = res
}
return res
}
空間複雜度：O (1)
枚舉算法#
算法策略#
枚舉算法的思想是：將問題的所有可能的答案一一列舉，然後根據條件判斷此答案是否合適，保留合適的，丟棄不合適的。
解題思路#
- 確定枚舉對象、枚舉範圍和判定條件。
- 逐一列舉可能的解，驗證每個解是否是問題的解。
總結#
算法是編程的 "里子"，不管你是前端還是後端，作為一名計算機工程師，具備一定的算法能力，是一種基本要求。