英文 | https://medium.com/frontend-canteen/algorithms-for-front-end-interviews-4aa329bb2ce4

翻譯 | 楊小愛

前端是一個不斷變化的領域，總是有很多新的東西需要我們?nèi)W習，這給我們帶來了不小的學習成本。

但從長遠來看，許多事情也不會改變。一旦你掌握了這些底層技能，就刻意持續(xù)一生，這就是掌握了底層邏輯的好處。例如，算法。

當我們在前端談論算法時，有兩種觀點：

有人認為算法在前端完全不重要，前端工程師沒必要學算法。

也有人聲稱前端程序員也是程序員，需要深入學習算法，就像算法工程師一樣。

我認為這兩種觀點都有些極端。

首先，算法在前端項目中也有很多應用。例如：

VirtualDOM 是 React 和 Vue 中的核心機制之一。它需要使用哈希表數(shù)據(jù)結(jié)構(gòu)和diff算法。

在解析模板語法和生成 AST 時，我們需要使用樹形數(shù)據(jù)結(jié)構(gòu)。

瀏覽器的瀏覽歷史，以及各種撤消和重做功能，都需要用到棧。

所以算法對我們前端開發(fā)者來說肯定是有用的。

但同時我們也需要明白：前端更注重工程。

前端工程師最重要的是什么？在我看來，最重要的是工程能力。

所謂工程能力，本質(zhì)上就是解決問題的能力。無論是編碼技能還是架構(gòu)思維，其本質(zhì)都是服務于解決問題的最終目標。

完成項目是我們的終極目標，算法只是手段。

作為前端工程師，你不需要在算法領域投入太多精力。您無需獲得 ACM 獎或完全理解厚書 Introduction to Algorithms。

所以在這里，我選擇了前端面試中經(jīng)常出現(xiàn)的算法題，然后經(jīng)過總結(jié)整理，今天將其分享給你。

1、如何對數(shù)組進行排序？

排序算法是計算機科學中最古老、最基本的主題之一。大約有十幾種常見的排序算法。

當然，我們不必完全掌握這些排序算法。如果我們需要先選擇一個排序算法來學習，那么我認為應該是快速排序。

為什么？因為：

快速排序本身被廣泛使用。
JavaScript 中 Array 的 sort 方法是通過 V8 引擎中的快速排序?qū)崿F(xiàn)的。

（準確的說，當數(shù)組元素少于10個時，V8使用插入排序算法，當數(shù)組元素多于10個時，使用快速排序算法。）

“快速排序”的思路很簡單，整個排序過程只需要三個步驟：

選擇數(shù)組中的一個元素作為“樞軸”。我們可以選擇任何元素作為樞軸，但中間的元素更直觀。
所有小于樞軸的元素都被移動到樞軸的左側(cè)；所有大于或等于樞軸的元素都被移動到樞軸的右側(cè)。
對于樞軸左右的兩個子集，重復第一步和第二步，直到所有子集中只剩下一個元素。

例如，我們有一個需要排序的數(shù)組：

let arr = [86, 24, 64, 48, 15, 30, 90, 49]

執(zhí)行

首先，定義一個參數(shù)為數(shù)組的快速排序函數(shù)。

var quickSort = function(arr) {};

然后，檢查數(shù)組中的元素個數(shù)，如果小于等于 1，則返回。

var quickSort = function(arr) {  if (arr.length <= 1) { return arr; }};

接下來，選擇樞軸，將其與原始數(shù)組分開，并定義兩個空數(shù)組來存儲兩個子集。

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 = [];
};

然后，開始遍歷數(shù)組，小于主元的元素放入左子集中，大于主元的元素放入右子集中。

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]);
　　　　}
　　}
};

最后，通過使用遞歸重復這個過程，得到排序后的數(shù)組。

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、如何在排序后的數(shù)組中找到某個值？

對數(shù)組進行排序后，讓我們使用排序后的數(shù)組。

假設我們有一個有序數(shù)組，我們想檢查這個數(shù)組中是否存在某個值。那么我們應該怎么做呢？

我們可以遍歷數(shù)組以確定該值是否存在于數(shù)組中，但是這種方法效率太低。

對于排序數(shù)組，我們有一個更有效的方法，就是二分查找。

執(zhí)行二分搜索的基本步驟是：

以整個數(shù)組的中間元素作為搜索鍵開始。
如果搜索鍵的值等于項目，則返回搜索鍵的索引。
或者搜索鍵的值小于區(qū)間中間的項，則將區(qū)間縮小到下半部分。
否則，將其縮小到上半部分。
從第二點開始反復檢查，直到找到值或區(qū)間為空。

例如，這是一個排序數(shù)組：

[15, 24, 30, 48, 49, 64, 86, 90, 100, 121, 130]

如果我們要檢查這個數(shù)組中是否存在 48：

執(zhí)行

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;}

用法：

比較

二分搜索比正常的線性搜索更快。

但是，你只能在排序數(shù)組上使用二進制搜索！

3、如何反轉(zhuǎn)單鏈表？

鏈表是表示一系列節(jié)點的數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點包含兩條信息：節(jié)點的值和指向列表中下一個節(jié)點的指針/引用。鏈表的開頭稱為頭，鏈表末尾的節(jié)點稱為尾，指向空值；null。

與數(shù)組相比，鏈表的主要好處是更容易在列表中插入或刪除節(jié)點。另一方面，不允許隨機訪問數(shù)據(jù)，因為與數(shù)組不同，鏈表沒有索引。

鏈表也廣泛用于前端項目。例如，React 的 Fiber 使用鏈表。

我們可以這樣創(chuàng)建一個鏈表：

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)

如果我們被要求反轉(zhuǎn)一個鏈表，我們需要讓尾部成為頭部：

我們可以迭代或遞歸地反轉(zhuǎn)鏈表，但我們將只關注通過以下步驟來解釋今天的迭代方法：

1)、初始化三個指針：prev、current 和 next：

prev：此指針將跟蹤當前節(jié)點之前的節(jié)點，我們將其設置為空，因為單鏈表節(jié)點沒有對其前一個節(jié)點的引用。
current：這個將從列表的頭部開始，并跟蹤我們當前所在的節(jié)點。
next：此指針將在其引用更改之前存儲下一個節(jié)點，并且最初設置為 null。

2）、遍歷所有節(jié)點，遍歷鏈表，只要有節(jié)點，每次迭代執(zhí)行以下操作：

設置為 current.next 的 next （我們需要在更改之前存儲 current 的下一個節(jié)點）。
將 current.next 設置為 prev（我們現(xiàn)在可以通過反轉(zhuǎn)鏈接來更改當前的下一個）。
將 prev 設置為 current（此步驟將前一個節(jié)點向前移動）。
設置當前等于下一個（這一步將當前節(jié)點向前移動）。
對所有節(jié)點重復步驟 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、如何檢查括號是否有效？

前端開發(fā)經(jīng)常需要解析模板語法，所以面試中經(jīng)常會問到下面這個問題。

描述：

給定一個僅包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 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 僅包含括號 '()[]{}'。

分析：

對于這類問題，我們一般更喜歡使用棧數(shù)據(jù)結(jié)構(gòu)。為什么可以用堆棧來完成？

想想有效的括號是什么意思？是對稱的意思。

根據(jù)棧的后進先出原則，數(shù)據(jù)的入棧和出棧順序是對稱的。比如1、2、3、4、5、6依次入棧，對應的出棧順序為6、5、4、3、2、1：

123456 654321

因此，你可以在這里記住一個規(guī)則：如果問題涉及括號或其他對稱結(jié)構(gòu)，則相關解決方案很可能與堆棧有關。

我們的想法是：遍歷整個字符串：

如果找到左括號，則將其添加到堆棧中。
如果找到右括號，則彈出堆棧頂部的一個元素，并確定當前的右括號是否匹配它。

對于有效的括號，整個流程可能如下所示：

執(zhí)行：

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;};