Docs

Appearance

彩蛋2前端开发如何有针对性地学习算法？ ​

为了应一些朋友的诉求，今天这节彩蛋我主要针对算法进行讲解，带你重新学习数据结构，以便更好地应对各种算法题目。

你也知道算法题目是各种大厂必考的题目，但是由于工作比较忙而没有时间刷题；即便想好好复习一下算法，却又因为知识点太多而无从下手；还有一些非计算机专业出身的前端同学，对数据结构算法并没有系统学习过，面对那么多知识点也比较盲从，不知道哪些需要掌握、哪些不需要掌握。那么希望这一讲彩蛋，能帮助你形成对数据结构算法学习的思路，提升你的学习效率。

话不多说，先来看看数据结构的存储方式。

数据结构的存储方式 ​

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。根据这两种分类我们来分别看看几个数据结构的 JavaScript 代码描述方式。

顺序存储 ​

先来看看 JS 实现一个栈的代码，它是比较典型的顺序存储方式。

javascript
class Stack {
  constructor() {
    this.items = []
  }
  
  push(element) {
    this.items.push(element)
  }
  pop() {
    return this.items.pop()
  }
  get size() {
    return this.items.length
  }
  get isEmpty() {
    return !this.items.length
  }
  clear() {
    this.items = []
  }
  print() {
    console.log(this.items.toString())
  }
}
// 初始化一个栈
var s = new Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
console.log(s)
console.log(s.isEmpty)
console.log(s.size)

上面的代码比较简单，通过 ES6 的语法 class 来描述非常简洁、容易让人理解。那么再看类似的队列，下面这个数据结构应该怎么用 JavaScript 来描述呢？

javascript
class Queue {
  constructor() {
    this.items = []
  }
  enqueue(element) {
    this.items.push(element)
  }
  shift() {
    return this.items.shift()
  }
  get size() {
    return this.items.length
  }
  get isEmpty() {
    return !this.items.length
  }
  clear() {
    this.items = []
  }
  print() {
    console.log(this.items.toString())
  }
}
// 初始化一个队列
var s = new Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.enqueue(4)
console.log(s)
console.log(s.isEmpty)
console.log(s.size)

从上面的两种数据结构的实现方式可以看出，队列和栈都是顺序存储结构，是用数组来模拟实现的，但是两者唯一的区别就在于一个是先进后出，另外一个是先进先出。

这两个数据结构模拟起来都比较简单，我们再看看较为复杂的链式存储、二叉树和链表等，都是怎么用 JavaScript 来描述的。

链式存储 ​

下面代码展示的是最基本的链表的 JS 实现逻辑，也是链式存储最典型的例子。

javascript
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}
class LinkedList {
  constructor() {
    this.head = null
    this.length = 0
  }
  append(element) {
    const node = new Node(element)
    let current = null
    if (this.head == null) {
      this.head = node
    } else {
      current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
    this.length++
  }
  insert(position, element) {
    if (position < 0 && position > this.length) {
       return false 
    } else {
      const node = new Node(element)
      let current = this.head
      let previous = null
      let index = 0
      if (position === 0) {
        this.head = node
        node.next = current
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node
      }
      this.length++
      return true
    }
  }
  
  removeAt(position) {
    if (position < 0 && position > this.length) {
      return false
    } else {
      let current = this.head
      let previous = null
      let index = 0
      if (position === 0) {
        this.head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length--
      return true
    }
  }
  findIndex(element) {
    let current = this.head
    let index = -1
    while (current) {
      if (current.element === element) {
        return index + 1
      }
      index++
      current = current.next
    }
    return -1
  }
  remove(element) {
    const index = this.findIndex(element)
    return this.removeAt(index)
  }
  get size() {
    return this.length
  }
  get isEmpty() {
    return !this.length
  }
  toString() {
    let current = this.head
    let slink = ''
    while (current) {
      slink += `${current.element}-`
      current = current.next
    }
    return slink
  }
}
// 初始化一个链表
var s = new LinkedList()
s.append(1)
s.append(2)
s.append(3)
s.append(4)
console.log(s)
console.log(s.isEmpty)
console.log(s.size)

这段代码同样用 ES6 比较简明的语法实现了链表的数据结构，只要你基本了解数据结构链表的思路，那么对上面的代码理解起来不是很难。

下面我们再看稍微复杂一些的二叉树的 JS 代码描述。

javascript
class Node {
  constructor(element) {
    this.element = element
    this.left = null
    this.right = null
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null
  }
  insert(element) {
    const temp = new Node(element)
    var insertNode = function(root, node) {
      if (node.element > root.element) {
        if (root.right === null) {
          root.right = node
        } else {
          insertNode(root.right, node)
        }
      } else {
        if (root.left === null) {
          root.left = node
        } else {
          insertNode(root.left, node)
        }
      }
    }
    if (!this.root) {
      this.root = temp
    } else {
      insertNode(this.root, temp)
    }
  }
  // 中序遍历
  inOrderTraverse(callback) {
    const inOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        inOrderTraverseNode(node.left, callback)
        callback(node.element)
        inOrderTraverseNode(node.right, callback)
      }
    }
    inOrderTraverseNode(this.root, callback)
  }
  // 前序遍历
  preOrderTraverse(callback) {
    const preOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        callback(node.element)
        preOrderTraverseNode(node.left, callback)
        preOrderTraverseNode(node.right, callback)
      }
    }
    preOrderTraverseNode(this.root, callback)
  }
  // 后序遍历
  postOrderTraverse(callback) {
    const postOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        postOrderTraverseNode(node.left, callback)
        postOrderTraverseNode(node.right, callback)
        callback(node.element)
      }
    }
    postOrderTraverseNode(this.root, callback)
  }
  min() {
    const minNode = node => {
      return node ? (node.left ? minNode(node.left) : node) : null
    }
    return minNode(this.root)
  }
  max() {
    const maxNode = node => {
      return node ? (node.right ? maxNode(node.right) : node) : null
    }
    return maxNode(this.root)
  }
  search(key) {
    const searchNode = (node, key) => {
      if (node === null) return
      if (node.element === key) {
        console.log(node)
        return node
      } else {
        return searchNode((key < node.element) ? node.left : node.right, key)
      }
    }
    searchNode(this.root, key)
  }
}
// 初始化一个BST
const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
console.log(tree)
// 调用二叉树对应地获取最大最小，以及搜索的方法
var m = tree.min()
console.log(m.element)
var max = tree.max()
console.log(max)
var r = tree.search(12)
console.log(r)

到这里是不是发现二叉树要比上面栈、队列以及链表要复杂一些了呢？仔细看二叉树的核心实现逻辑，不管是前、中、后序遍历，还是获取最值以及查找，本质上都是算法中一个比较重要的思想，那就是递归。递归调用自身的方法不断地往下遍历，这是二叉树相关题目比较重要的一个思路，你需要好好掌握，以便能轻松解决一系列二叉树的相关算法题目。

下面再和你说说关于算法该如何刷题。

算法刷题指南 ​

首先要明确的是数据结构是工具，算法是通过合适的工具解决特定问题的方法。也就是说，学习算法之前，最起码得了解那些常用的数据结构，知道它们的特性和缺陷。

那么该如何在 LeetCode 刷题呢？我的建议是你在熟悉了基本数据结构，并且能很轻松用 JS 实现常见的数据结构之后，就可以去刷题了。LeetCode 刷题也有套路，建议你当数据结构基本都了解并能实现的基础上，可以先直接刷二叉树相关的题目，因为这块比较容易抽象出通用的思路（本讲的最后我会带你看二叉树这部分怎么突破）。

其实总结下来，算法刷题无非就是找到这几类题目的解题思路：

  1. If-else, switch（branch）

  2. for，while loop（Iteration）

  3. 递归 Recursion（Divide, Backtrace）

  4. 搜索 Search：深度优先搜索（Depth first search）、广度优先搜索（Breadth first search）、A* 等

  5. 动态规划（Dynamic Programming）

  6. 二分查找（Binary Search）

  7. 贪心算法（Greedy）

  8. 数学（Math）& 位运算等

上面提到的二叉树相关的实现思路以及相关的题目，其实就是第三类递归的思路，如果你把递归的思路掌握好，那对于二叉树相关的题目你将会得心应手。动态规划也类似，核心思路就是动态递推，从最小的开始计算，一步一步推导累加到第 n 次之后的结果。

针对算法和数据结构那么多知识点，我为你总结了一个脑图，方便你分别击破。

算法数据结构脑图 ​

里面的分支有很多，下面我们专门针对上面提到的二叉树来进行深入探讨，看看递归的思想是如何解决二叉树相关问题的。

带你攻克一个难点 ​

在看二叉树相关题目之前，你需要对上面的 JS 实现二叉树的代码非常了解，尤其是前、中、后序遍历的过程，以及递归找二叉树中的最值的思路。有了这些基础之后，我们挑 LeetCode 的几个例子，看看怎么用递归的思路解决二叉树一系列的问题，类似的题目如下：

  1. 94 题：二叉树的中序遍历

  2. 102 题：二叉树的层序遍历

  3. 103 题：二叉树的锯齿形层序遍历

  4. 104 题：二叉树的最大深度

  5. 144 题：二叉树的前序遍历

  6. 199 题：二叉树的右视图

还有其他类似的题目，这里就不举例了，我们先看这六道题如何击破。

那么把这六道题目抽象起来，形成的思路以及代码模板大致如下：

java
// root为传入的二叉树
var XXXTraversal = function(root) {
    // 定义一个返回的遍历结果的组数
    let res = []
    // 定义一个内部需要不断递归的函数
    function traverse(r) {
        if(!r) return;
        traverse(r.left);  // 递归遍历左子树
        res.push(r.val);    // 将根节点push进待返回的数组
        traverse(r.right);  // 递归遍历右子树
    }
    traverse(root);    // 循环遍历
    return res;      // 最后返回
};

那么根据这个基本的模板，我们就可以衍生出上面几道题的答案了。只需要把 8、9、10 行代码的位置稍做调整，二叉树的前、中、后序遍历的题目就迎刃而解了。对于层序遍历，我们只需要根据上面稍加改造就能通过 LeetCode 的编译，如下所示。

javascript
var levelOrder = function(root) {
    let arr =[];
    function traverse(root, depth) {
        if(root === null) return [];
        if(arr[depth] === undefined) { // 改造外面定义的待返回的数组变成二维
            arr[depth] = [];
        }
        arr[depth].push(root.val);    // 把根节点在最先push进去
        traverse(root.left, depth + 1);  // 层数+1对应arr里的二维数组的序号 
        traverse(root.right, depth + 1); // 同上
    }
    traverse(root, 0);
    return arr;
};
/*
  通过测试得到的返回结果是一个二维数组：[[3],[9,20],[15,7]] 
*/

那么第 102 道题的答案已经出来了。再看下第 199 题，如何在中序遍历递归的基础上实现二叉树的右视图？这道题其实就是通过递归的方式找到二叉树的右子树进行遍历输出，它的逻辑和层序遍历其实类似，只不过在递归的过程中进行拦截，确保层数和数组个数一致的时候，只存储右子树的节点就好。

看一下基于层序遍历改造之后的实现 199 题的代码逻辑。

javascript
var rightSideView = function(root) {
    var arr = [];
    function traverse(root, depth) {
        if(root === null) return;
        if(depth === arr.length) {  // 这加了逻辑拦截，只能push一个右节点
            arr.push(root.val);
        }
        depth++;    // 和层序遍历每进入一层 depth 加一逻辑基本一致
        traverse(root.right, depth);  // 先进入右子树遍历，上面的if拦截
        traverse(root.left, depth);  // 遍历的时候左子树已经存不进arr数组了
    }
    traverse(root, 0);
    return arr;
};

通过上面几道二叉树的遍历的题目，就可以总结出这一系列题目的解题思路了。其核心都是用递归的思路来解决二叉树的遍历问题，只不过通过调整遍历的顺序以及存储数据的方式，把最后遍历的节点数字存储到对应的返回数组中，最后都能通过代码变化得到想要的效果。

那么类似的题目也就能迎刃而解了，二叉树是应用递归思路最多的例子，那么除了这部分，例如动态规划如何来刷题呢？思路也类似，找到一两道动态规划比较典型的题目，总结和抽象出通用的解题思路，之后就可以更容易地去解决类似的题目了。

总结 ​

这一讲我们讨论了前端开发如何学习数据结构和刷题的方法，根据脑图复习了数据结构和算法。你要知道，算法可是通往大厂的必备技能，面试中一定会出现相应的题目。因此如果你不能有效地刷题、找到解决算法和数据结构的通用方法，是很难应对 LeetCode 中那么多算法编程题目的。因为随便出一个变形的算法题目你可能就不会了，你非常有必要从每道题目的细节中提炼出解决某一类题目的通用方法，这样你才能灵活从容地应对面试。

希望我的分享可以为你算法的提升带来帮助，也希望你能在各种面试中脱颖而出，成为一名优秀的前端人。