一面 4：從容應對算法題目 · Web 前端面試指南與高頻考題解析

由馮·諾依曼機組成我們知道：數據存儲和運算是計算機工作的主要內容。`程序=數據結構+算法`，所以計算機類工程師必須掌握一定的數據結構和算法知識。 ## 知識點梳理 * 常見的數據結構 * 棧、隊列、鏈表 * 集合、字典、散列集 * 常見算法 * 遞歸 * 排序 * 枚舉 * 算法復雜度分析 * 算法思維 * 分治 * 貪心 * 動態規劃 * 高級數據結構 * 樹、圖 * 深度優先和廣度優先搜索本小節會帶領大家快速過一遍數據結構和算法，重點講解一些常考、前端會用到的算法和數據結構。 * * * ## 數據結構數據結構決定了數據存儲的空間和時間效率問題，數據的寫入和提取速度要求也決定了應該選擇怎樣的數據結構。根據對場景需求的不同，我們設計不同的數據結構，比如： * 讀得多的數據結構，應該想辦法提高數據的讀取效率，比如 IP 數據庫，只需要寫一次，剩下的都是讀取； * 讀寫都多的數據結構，要兼顧兩者的需求平衡，比如 LRU Cache 算法。算法是數據加工處理的方式，一定的算法會提升數據的處理效率。比如有序數組的二分查找，要比普通的順序查找快很多，尤其是在處理大量數據的時候。數據結構和算法是程序開發的通用技能，所以在任何面試中都可能會遇見。隨著近幾年 AI、大數據、小游戲越來越火，Web 前端職位難免會跟數據結構和算法打交道，面試中也會出現越來越多的算法題目。學習數據結構和算法也能夠幫助我們打開思路，突破技能瓶頸。 ## 前端常遇見的數據結構問題現在我來梳理下前端常遇見的數據結構： * 簡單數據結構（必須理解掌握） * 有序數據結構：棧、隊列、鏈表，有序數據結構省空間（存儲空間小） * 無序數據結構：集合、字典、散列表，無序數據結構省時間（讀取時間快） * 復雜數據結構 * 樹、堆 * 圖對于簡單數據結構，在 ES 中對應的是數組（`Array`）和對象（`Object`）。可以想一下，數組的存儲是有序的，對象的存儲是無序的，但是我要在對象中根據`key`找到一個值是立即返回的，數組則需要查找的過程。這里我通過一個真實面試題目來說明介紹下數據結構設計。 > 題目：使用 ECMAScript（JS）代碼實現一個事件類`Event`，包含下面功能：綁定事件、解綁事件和派發事件。在稍微復雜點的頁面中，比如組件化開發的頁面，同一個頁面由兩三個人來開發，為了保證組件的獨立性和降低組件間耦合度，我們往往使用「訂閱發布模式」，即組件間通信使用事件監聽和派發的方式，而不是直接相互調用組件方法，這就是題目要求寫的`Event`類。這個題目的核心是一個事件類型對應回調函數的數據設計。為了實現綁定事件，我們需要一個`_cache`對象來記錄綁定了哪些事件。而事件發生的時候，我們需要從`_cache`中讀取出來事件回調，依次執行它們。一般頁面中事件派發（讀）要比事件綁定（寫）多。所以我們設計的數據結構應該盡量地能夠在事件發生時，更加快速地找到對應事件的回調函數們，然后執行。經過這樣一番考慮，我簡單寫了下代碼實現： ``` class Event { constructor() { // 存儲事件的數據結構 // 為了查找迅速，使用了對象（字典） this._cache = {}; } // 綁定 on(type, callback) { // 為了按類查找方便和節省空間， // 將同一類型事件放到一個數組中 // 這里的數組是隊列，遵循先進先出 // 即先綁定的事件先觸發 let fns = (this._cache[type] = this._cache[type] || []); if (fns.indexOf(callback) === -1) { fns.push(callback); } return this; } // 觸發 trigger(type, data) { let fns = this._cache[type]; if (Array.isArray(fns)) { fns.forEach((fn) => { fn(data); }); } return this; } // 解綁 off(type, callback) { let fns = this._cache[type]; if (Array.isArray(fns)) { if (callback) { let index = fns.indexOf(callback); if (index !== -1) { fns.splice(index, 1); } } else { //全部清空 fns.length = 0; } } return this; } } // 測試用例 const event = new Event(); event.on('test', (a) => { console.log(a); }); event.trigger('test', 'hello world'); event.off('test'); event.trigger('test', 'hello world'); ``` 類似于樹、堆、圖這些高級數據結構，前端一般也不會考查太多，但是它們的查找方法卻常考，后面介紹。高級數據應該平時多積累，好好理解，比如理解了堆是什么樣的數據結構，在面試中遇見的「查找最大的 K 個數」這類算法問題，就會迎刃而解。 ## 算法的效率是通過算法復雜度來衡量的算法的好壞可以通過算法復雜度來衡量，算法復雜度包括時間復雜度和空間復雜度兩個。時間復雜度由于好估算、好評估等特點，是面試中考查的重點。空間復雜度在面試中考查得不多。常見的時間復雜度有： * 常數階 `O(1)` * 對數階 `O(logN)` * 線性階 `O(n)` * 線性對數階 `O(nlogN)` * 平方階 `O(n^2)` * 立方階 `O(n^3)` * !k次方階 `O(n^k)` * 指數階`O(2^n)` 隨著問題規模 n 的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低。一般做算法復雜度分析的時候，遵循下面的技巧： 1. 看看有幾重循環，一般來說一重就是`O(n)`，兩重就是 `O(n^2)`，以此類推 2. 如果有二分，則為`O(logN)` 3. 保留最高項，去除常數項 > 題目：分析下面代碼的算法復雜度（為了方便，我已經在注釋中加了代碼分析） ``` let i =0; // 語句執行一次 while (i < n) { // 語句執行 n 次 console.log(`Current i is ${i}`); //語句執行 n 次 i++; // 語句執行 n 次 } ``` 根據注釋可以得到，算法復雜度為`1 + n + n + n = 1 + 3n`，去除常數項，為`O(n)`。 ``` let number = 1; // 語句執行一次 while (number < n) { // 語句執行 logN 次 number *= 2; // 語句執行 logN 次 } ``` 上面代碼`while`的跳出判斷條件是`number<n`，而循環體內`number`增長速度是`(2^n)`，所以循環代碼實際執行`logN`次，復雜度為：`1 + 2 * logN = O(logN)` ``` for (let i = 0; i < n; i++) {// 語句執行 n 次 for (let j = 0; j < n; j++) {// 語句執行 n^2 次 console.log('I am here!'); // 語句執行 n^2 次 } } ``` 上面代碼是兩個`for`循環嵌套，很容易得出復雜度為：`O(n^2)` ## 人人都要掌握的基礎算法枚舉和遞歸是最最簡單的算法，也是復雜算法的基礎，人人都應該掌握！枚舉相對比較簡單，我們重點說下遞歸。遞歸由下面兩部分組成： 1. 遞歸主體，就是要循環解決問題的代碼 2. 遞歸的跳出條件，遞歸不能一直遞歸下去，需要完成一定條件后跳出關于遞歸有個經典的面試題目是： > 實現 JS 對象的深拷貝 **什么是深拷貝？** 「深拷貝」就是在拷貝數據的時候，將數據的所有**引用結構**都拷貝一份。簡單的說就是，在內存中存在兩個數據結構完全相同又相互獨立的數據，將引用型類型進行復制，而不是只復制其引用關系。分析下怎么做「深拷貝」： 1. 首先假設深拷貝這個方法已經完成，為 deepClone 2. 要拷貝一個數據，我們肯定要去遍歷它的屬性，如果這個對象的屬性仍是對象，繼續使用這個方法，如此往復 ``` function deepClone(o1, o2) { for (let k in o2) { if (typeof o2[k] === 'object') { o1[k] = {}; deepClone(o1[k], o2[k]); } else { o1[k] = o2[k]; } } } // 測試用例 let obj = { a: 1, b: [1, 2, 3], c: {} }; let emptyObj = Object.create(null); deepClone(emptyObj, obj); console.log(emptyObj.a == obj.a); console.log(emptyObj.b == obj.b); ``` 遞歸容易造成爆棧，尾部調用可以解決遞歸的這個問題，Chrome 的 V8 引擎做了尾部調用優化，我們在寫代碼的時候也要注意尾部調用寫法。遞歸的爆棧問題可以通過將遞歸改寫成枚舉的方式來解決，就是通過`for`或者`while`來代替遞歸。我們在使用遞歸的時候，要注意做優化，比如下面的題目。 > 題目：求斐波那契數列（兔子數列） 1,1,2,3,5,8,13,21,34,55,89...中的第 n 項下面的代碼中`count`記錄遞歸的次數，我們看下兩種差異性的代碼中的`count`的值： ``` let count = 0; function fn(n) { let cache = {}; function _fn(n) { if (cache[n]) { return cache[n]; } count++; if (n == 1 || n == 2) { return 1; } let prev = _fn(n - 1); cache[n - 1] = prev; let next = _fn(n - 2); cache[n - 2] = next; return prev + next; } return _fn(n); } let count2 = 0; function fn2(n) { count2++; if (n == 1 || n == 2) { return 1; } return fn2(n - 1) + fn2(n - 2); } console.log(fn(20), count); // 6765 20 console.log(fn2(20), count2); // 6765 13529 ``` ## 快排和二分查找前端中面試排序和查找的可能性比較小，因為 JS 引擎已經把這些常用操作優化得很好了，可能項目中你費勁寫的一個排序方法，都不如`Array.sort`速度快且代碼少。因此，掌握快排和二分查找就可以了。快排和二分查找都基于一種叫做「分治」的算法思想，通過對數據進行分類處理，不斷降低數量級，實現`O(logN)`（對數級別，比`O(n)`這種線性復雜度更低的一種，快排核心是二分法的`O(logN)`，實際復雜度為`O(N*logN)`）的復雜度。 ### 快速排序快排大概的流程是： 1. 隨機選擇數組中的一個數 A，以這個數為基準 2. 其他數字跟這個數進行比較，比這個數小的放在其左邊，大的放到其右邊 3. 經過一次循環之后，A 左邊為小于 A 的，右邊為大于 A 的 4. 這時候將左邊和右邊的數再遞歸上面的過程具體代碼如下： ``` // 劃分操作函數 function partition(array, left, right) { // 用index取中間值而非splice const pivot = array[Math.floor((right + left) / 2)] let i = left let j = right while (i <= j) { while (compare(array[i], pivot) === -1) { i++ } while (compare(array[j], pivot) === 1) { j-- } if (i <= j) { swap(array, i, j) i++ j-- } } return i } // 比較函數 function compare(a, b) { if (a === b) { return 0 } return a < b ? -1 : 1 } function quick(array, left, right) { let index if (array.length > 1) { index = partition(array, left, right) if (left < index - 1) { quick(array, left, index - 1) } if (index < right) { quick(array, index, right) } } return array } function quickSort(array) { return quick(array, 0, array.length - 1) } // 原地交換函數，而非用臨時數組 function swap(array, a, b) { ;[array[a], array[b]] = [array[b], array[a]] } const Arr = [85, 24, 63, 45, 17, 31, 96, 50]; console.log(quickSort(Arr)); // 本版本來自：https://juejin.im/post/5af4902a6fb9a07abf728c40#heading-12 ``` ### 二分查找二分查找法主要是解決「在一堆有序的數中找出指定的數」這類問題，不管這些數是一維數組還是多維數組，只要有序，就可以用二分查找來優化。二分查找是一種「分治」思想的算法，大概流程如下： 1. 數組中排在中間的數字 A，與要找的數字比較大小 2. 因為數組是有序的，所以： a) A 較大則說明要查找的數字應該從前半部分查找 b) A 較小則說明應該從查找數字的后半部分查找 3. 這樣不斷查找縮小數量級（扔掉一半數據），直到找完數組為止 > 題目：在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。 ``` function Find(target, array) { let i = 0; let j = array[i].length - 1; while (i < array.length && j >= 0) { if (array[i][j] < target) { i++; } else if (array[i][j] > target) { j--; } else { return true; } } return false; } //測試用例 console.log(Find(10, [ [1, 2, 3, 4], [5, 9, 10, 11], [13, 20, 21, 23] ]) ); ``` 另外筆者在面試中遇見過下面的問題： > 題目：現在我有一個 1~1000 區間中的正整數，需要你猜下這個數字是幾，你只能問一個問題：大了還是小了？問需要猜幾次才能猜對？拿到這個題目，筆者想到的就是電視上面有個「猜價格」的購物節目，在規定時間內猜對價格就可以把實物抱回家。所以問題就是讓面試官不停地回答我猜的數字比這個數字大了還是小了。這就是二分查找！猜幾次呢？其實這個問題就是個二分查找的算法時間復雜度問題，二分查找的時間復雜度是`O(logN)`，所以求`log1000`的解就是猜的次數。我們知道`2^10=1024`，所以可以快速估算出：`log1000`約等于 10，最多問 10 次就能得到這個數！ ## 面試遇見不會的算法問題怎么辦面試的時候，在遇見算法題目的時候，應該揣摩面試官的意圖，聽好關鍵詞，比如：有序的數列做查找、要求算法復雜度是`O(logN)`這類一般就是用二分的思想。一般來說算法題目的解題思路分以下四步： 1. 先降低數量級，拿可以計算出來的情況（數據）來構思解題步驟 2. 根據解題步驟編寫程序，優先將特殊情況做好判斷處理，比如一個大數組的問題，如果數組為兩個數長度的情況 3. 檢驗程序正確性 4. 是否可以優化（由淺到深），有能力的話可以故意預留優化點，這樣可以體現個人技術能力 ## 正則匹配解題很多算法題目利用 ES 語法的特性來回答更加簡單，比如正則匹配就是常用的一種方式。筆者簡單通過幾個真題來匯總下正則的知識點。 > 題目：字符串中第一個出現一次的字符請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符「go」時，第一個只出現一次的字符是「g」。當從該字符流中讀出前六個字符「google」時，第一個只出現一次的字符是「l」。這個如果用純算法來解答需要遍歷字符串，統計每個字符出現的次數，然后按照字符串的順序來找出第一次出現一次的字符，整個過程比較繁瑣，如果用正則就簡單多了。 ``` function find(str){ for (var i = 0; i < str.length; i++) { let char = str[i] let reg = new RegExp(char, 'g'); let l = str.match(reg).length if(l===1){ return char } } } ``` 當然，使用`indexOf/lastIndexOf`也是一個取巧的方式。再來看一個千分位問題。 > 題目：將`1234567` 變成 `1,234,567`，即千分位標注這個題目可以用算法直接來解，如果候選人使用正則來回答，這樣主動展現了自己其他方面的優勢，即使不是算法解答出來的，面試官一般也不會太難為他。這道題目可以利用正則的「零寬斷言」`(?=exp)`，意思是它斷言自身出現的位置的后面能匹配表達式 exp。數字千分位的特點是，第一個逗號后面數字的個數是3的倍數，正則：`/(\d{3})+$/`；第一個逗號前最多可以有 1~3 個數字，正則：`/\d{1,3}/`。加起來就是`/\d{1,3}(\d{3})+$/`，分隔符要從前往后加。對于零寬斷言的詳細介紹可以閱讀「[零寬斷言](https://deerchao.net/tutorials/regex/regex.htm#lookaround)」這篇文章。 ``` function exchange(num) { num += ''; //轉成字符串 if (num.length <= 3) { return num; } num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, (v) => { console.log(v) return v + ','; }); return num; } console.log(exchange(1234567)); ``` 當然上面講到的多數是算法題目取巧的方式，下面這個題目是純正則考查，筆者在面試的過程中碰見過，這里順便提一下。 > 題目，請寫出下面的代碼執行結果 ``` var str = 'google'; var reg = /o/g; console.log(reg.test(str)) console.log(reg.test(str)) console.log(reg.test(str)) ``` 代碼執行后，會發現，最后一個不是為`true`，而是`false`，這是因為`reg`這個正則有個`g`，即`global`全局的屬性，這種情況下`lastIndex`就發揮作用了，可以看下面的代碼執行結果就明白了。 ``` console.log(reg.test(str), reg.lastIndex) console.log(reg.test(str), reg.lastIndex) console.log(reg.test(str), reg.lastIndex) ``` 實際開發中也會犯這樣的錯誤，比如為了減少變量每次都重新定義，會把用到的變量提前定義好，這樣在使用的時候容易掉進坑里，比如下面代碼： ``` (function(){ const reg = /o/g; function isHasO(str){ // reg.lastIndex = 0; 這樣就可以避免這種情況 return reg.test(str) } var str = 'google'; console.log(isHasO(str)) console.log(isHasO(str)) console.log(isHasO(str)) }()) ``` ## 小結本小節介紹了數據結構和算法的關系，作為普通的前端也應該學習數據結構和算法知識，并且順帶介紹了下正則匹配。具體來說，本小節梳理了以下幾部分數據結構和算法知識點： 1. 經常用到的數據結構有哪些，它們的特點有哪些 2. 遞歸和枚舉是最基礎的算法，必須牢牢掌握 3. 排序里面理解并掌握快速排序算法，其他排序算法可以根據個人實際情況大概了解 4. 有序查找用二分查找 5. 遇見不會的算法問題，先縮小數量級，然后分析推導當然算法部分還有很多知識，比如動態規劃這些算法思想，還有圖和樹常用到的廣度優先搜索和深度優先搜索。這些知識在前端面試和項目中遇見得不多，感興趣的讀者可以在梳理知識點的時候根據個人情況自行決定是否復習。