英文 | https://medium.com/frontend-canteen/algorithms-for-front-end-interviews-4aa329bb2ce4
翻譯 | 楊小愛
前端是一個不斷變化的領域，總是有很多新的東西需要我們去學習，這給我們帶來了不小的學習成本。
但從長遠來看，許多事情也不會改變。一旦你掌握了這些底層技能，就刻意持續一生，這就是掌握了底層邏輯的好處。例如，算法。
當我們在前端談論算法時，有兩種觀點：
有人認為算法在前端完全不重要，前端工程師沒必要學算法。
也有人聲稱前端程式員也是程式員，需要深入學習算法，就像算法工程師一樣。
我認為這兩種觀點都有些極端。
首先，算法在前端項目中也有很多應用。例如：
VirtualDOM 是 React 和 Vue 中的核心機制之一。它需要使用哈希表資料結構和diff算法。
在解析模闆文法和生成 AST 時，我們需要使用樹形資料結構。
浏覽器的浏覽曆史，以及各種撤消和重做功能，都需要用到棧。
是以算法對我們前端開發者來說肯定是有用的。
但同時我們也需要明白：前端更注重工程。
前端工程師最重要的是什麼？在我看來，最重要的是工程能力。
所謂工程能力，本質上就是解決問題的能力。無論是編碼技能還是架構思維，其本質都是服務于解決問題的最終目标。
完成項目是我們的終極目标，算法隻是手段。
作為前端工程師，你不需要在算法領域投入太多精力。您無需獲得 ACM 獎或完全了解厚書 Introduction to Algorithms。
是以在這裡，我選擇了前端面試中經常出現的算法題，然後經過總結整理，今天将其分享給你。
1、如何對數組進行排序？
排序算法是計算機科學中最古老、最基本的主題之一。大約有十幾種常見的排序算法。
當然，我們不必完全掌握這些排序算法。如果我們需要先選擇一個排序算法來學習，那麼我認為應該是快速排序。
為什麼？因為：
- 快速排序本身被廣泛使用。
- JavaScript 中 Array 的 sort 方法是通過 V8 引擎中的快速排序實作的。
（準确的說，當數組元素少于10個時，V8使用插入排序算法，當數組元素多于10個時，使用快速排序算法。）
“快速排序”的思路很簡單，整個排序過程隻需要三個步驟：
- 選擇數組中的一個元素作為“樞軸”。我們可以選擇任何元素作為樞軸，但中間的元素更直覺。
- 所有小于樞軸的元素都被移動到樞軸的左側；所有大于或等于樞軸的元素都被移動到樞軸的右側。
- 對于樞軸左右的兩個子集，重複第一步和第二步，直到所有子集中隻剩下一個元素。
例如，我們有一個需要排序的數組：
let arr = [86, 24, 64, 48, 15, 30, 90, 49] 
執行
首先，定義一個參數為數組的快速排序函數。
var quickSort = function(arr) {
}; 然後，檢查數組中的元素個數，如果小于等于 1，則傳回。
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
}; 接下來，選擇樞軸，将其與原始數組分開，并定義兩個空數組來存儲兩個子集。
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2) ;
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
}; 然後，開始周遊數組，小于主元的元素放入左子集中，大于主元的元素放入右子集中。
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2) ;
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
}; 最後，通過使用遞歸重複這個過程，得到排序後的數組。
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}; 用法：
2、如何在排序後的數組中找到某個值？
對數組進行排序後，讓我們使用排序後的數組。
假設我們有一個有序數組，我們想檢查這個數組中是否存在某個值。那麼我們應該怎麼做呢？
我們可以周遊數組以确定該值是否存在于數組中，但是這種方法效率太低。
對于排序數組，我們有一個更有效的方法，就是二分查找。
執行二分搜尋的基本步驟是：
- 以整個數組的中間元素作為搜尋鍵開始。
- 如果搜尋鍵的值等于項目，則傳回搜尋鍵的索引。
- 或者搜尋鍵的值小于區間中間的項，則将區間縮小到下半部分。
- 否則，将其縮小到上半部分。
- 從第二點開始反複檢查，直到找到值或區間為空。
例如，這是一個排序數組：
[15, 24, 30, 48, 49, 64, 86, 90, 100, 121, 130] 如果我們要檢查這個數組中是否存在 48：
執行
function binarySearch(arr, x) {
// left index of the current interval
let l = 0;
// right index of the current interval
let r = arr.length - 1;
// middle index of the current interval
let mid;
while (r >= l) {
mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x) {
return mid;
}
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x) {
r = mid - 1;
}
// Else the element can only be present
// in right subarray
if (arr[mid] < x) {
l = mid + 1;
}
}
// We reach here when element is not
// present in array
return -1;
} 用法：
比較
二分搜尋比正常的線性搜尋更快。
但是，你隻能在排序數組上使用二進制搜尋！
3、如何反轉單連結清單？
連結清單是表示一系列節點的資料結構，其中每個節點包含兩條資訊：節點的值和指向清單中下一個節點的指針/引用。連結清單的開頭稱為頭，連結清單末尾的節點稱為尾，指向空值；null。
與數組相比，連結清單的主要好處是更容易在清單中插入或删除節點。另一方面，不允許随機通路資料，因為與數組不同，連結清單沒有索引。
連結清單也廣泛用于前端項目。例如，React 的 Fiber 使用連結清單。
我們可以這樣建立一個連結清單：
function Node(value) {
this.value = value
this.next = null
}
let head = new Node(1)
head.next = new Node(3)
head.next.next = new Node(9)
head.next.next.next = new Node(6)
head.next.next.next.next = new Node(2) 如果我們被要求反轉一個連結清單，我們需要讓尾部成為頭部：
我們可以疊代或遞歸地反轉連結清單，但我們将隻關注通過以下步驟來解釋今天的疊代方法：
1)、初始化三個指針：prev、current 和 next：
- prev：此指針将跟蹤目前節點之前的節點，我們将其設定為空，因為單連結清單節點沒有對其前一個節點的引用。
- current：這個将從清單的頭部開始，并跟蹤我們目前所在的節點。
- next：此指針将在其引用更改之前存儲下一個節點，并且最初設定為 null。
2）、周遊所有節點，周遊連結清單，隻要有節點，每次疊代執行以下操作：
- 設定為 current.next 的 next （我們需要在更改之前存儲 current 的下一個節點）。
- 将 current.next 設定為 prev（我們現在可以通過反轉連結來更改目前的下一個）。
- 将 prev 設定為 current（此步驟将前一個節點向前移動）。
- 設定目前等于下一個（這一步将目前節點向前移動）。
- 對所有節點重複步驟 2。
3）、 傳回 prev 指針作為反向清單的新頭。
const reverseList = head => {
let prev = null
let next = null
let current = head
while(current !== null){
next = current.next
current.next = prev
prev = current
current = next
}
return prev
} 用圖解釋：
4、 如何檢查括号是否有效？
前端開發經常需要解析模闆文法，是以面試中經常會問到下面這個問題。
描述：
給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字元串 s，确定輸入字元串是否有效。
輸入字元串在以下情況下有效：
- 括号必須用相同類型的括号閉合。
- 括号必須以正确的順序閉合。
示例 1：
Input: s = "()"
Output: true 示例2：
Input: s = "()[]{}"
Output: true 示例3：
Input: s = "(]"
Output: false 示例4：
Input: s = "([)]"
Output: false 示例5：
Input: s = "{[]}"
Output: true 限制：
- 1 <= s.length <= 104
- s 僅包含括号 '()[]{}'。
分析：
對于這類問題，我們一般更喜歡使用棧資料結構。為什麼可以用堆棧來完成？
想想有效的括号是什麼意思？是對稱的意思。
根據棧的後進先出原則，資料的入棧和出棧順序是對稱的。比如1、2、3、4、5、6依次入棧，對應的出棧順序為6、5、4、3、2、1：
123456
654321 是以，你可以在這裡記住一個規則：如果問題涉及括号或其他對稱結構，則相關解決方案很可能與堆棧有關。
我們的想法是：周遊整個字元串：
- 如果找到左括号，則将其添加到堆棧中。
- 如果找到右括号，則彈出堆棧頂部的一個元素，并确定目前的右括号是否比對它。
對于有效的括号，整個流程可能如下所示：
執行：
const isValid = function(s) {
if (!s) {
return true;
}
// array can be used as a stack
const stack = [];
const len = s.length;
for (let i = 0; i < len; i++) {
// cache
const ch = s[i];
if (ch === "(" || ch === "{" || ch === "[") {
stack.push(leftToRight[ch]);
}
else {
// If the stack is not empty and the
// openning parenthesis at the top of the stack does not
// match the current character, it is invalid.
if (!stack.length || stack.pop() !== ch) {
return false;
}
}
}
// If all parentheses can be matched successfully,
// then the final stack should be empty
return !stack.length;
}; 總結
以上就是我分享的4個常見的算法問題。當然，這些内容還遠遠不夠，但是由于文章篇幅關系，這次就不繼續了。
很多初級前端開發者，尤其是自學成才的（比如我），面對面試可能會有點害怕，尤其是在我們不擅長的算法領域。
在面試前多練習算法題，為自己搭建知識庫。提前準備有助于增強自信心。
面試的時候，積極思考自己的知識庫和面試題之間的關系，然後多說自己擅長什麼，即使内容和題本身關系不大。
面試結束後，主動與面試官溝通，問他問題的邏輯。同時，你可以把面試中不懂的問題記錄下來，然後仔細研究。畢竟，這不會是你的最後一次面試。
今天的内容就先到這裡了，感謝你的閱讀。