前端数据结构的算法实现

前端面试中算法题是比较难的一部分，今天总结下数据结构中的算法实现。

排序

快速排序

找到一个数作为参考，比这个数字大放左边，比它小放右边，然后分别对左边和右边做相同操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;   // 递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0, 1);
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < current) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat(current,quickSort(right));  // 递归
}

冒泡排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


function bubbleSort(arr){
  var len = arr.length;
  for(let outer = len;outer >= 2;outer--){
    for(let inner = 0;inner <= outer-1;inner++){
     if(arr[inner] > arr[inner+1]){
       let temp = arr[inner];
       arr[inner] = arr[inner+1];
       arr[inner+1] = temp;
     }
    }
  }
  return arr;
}

外层循环，从最大值开始递减，因为内层是两两比较，因此最外层当>=2时即可停止；
内层是两两比较，从0开始，比较inner与inner+1，因此，临界条件是inner<outer -1

选择排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


function selectSort(arr){
  var len = arr.length;
  for(let i=0;i < len-1; i++){
    for(let j=i; j<len; j++){
      if(arr[j] < arr[i]){
        [arr[i],arr[j]]=[arr[j],arr[i]];
      }
    }
  }
  return arr
}

插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function insertSort(arr){
  for(let i=1;i<arr.length;i++){
    for(let j=i;j>0;j--){
      if(arr[j]<arr[j-1]){
        [arr[j],arr[j-1]]=[arr[j-1],arr[j]];
      }else{
        break;
      }
    }
  }
  return arr;
}

栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Stack {
    constructor() {
        this.stack = []
    }
    push(item) {
        this.stack.push(item)
    }
    pop() {
        this.stack.pop()
    }
    getLength() {
        return this.stack.length
    }
    isEmpty() {
        return this.getLength() === 0
    }
}

应用(匹配括号)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


var isMatch = function(arr){
  let  map = {
   '(':-1,
    ')':1,
    '[':-2,
    ']':2,
    '{':-3,
    '}':3
  }
  let stack = []
  for(let i = 0; i<arr.length; i++){
    if(map[arr[i]] < 0){
      stack.push(arr[i])
    }else{
      let last = stack.pop()
      if(map[last] + map[arr[i]] != 0) return false
    }
  }
  if(stack.length > 0) return false
  return true
};

队列

简单单链队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Queue {
  constructor(){
    this.queue = []
  }
  enQueue(item){
    this.queue.push(item)
  }
  deQueue(){
    return this.queue.shift()
  }
  getHeader(){
      return this.queue[0]
  }
  getLength(){
    return this.queue.length
  }
  isEmpty(){
    return this.getLength() === 0
  }
}

循环队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class SqQueue{
 constructor(length){
   this.queue = new Array(length + 1)
   this.first = 0
   this.last = 0
   this.size = 0
 }
 enQueue(item){
    // 判断队尾+1是否为队头
    // 是就代表需要扩容数组
    // %this.queue.length 为了防止数组越界
    if(this.first===(this.last + 1) % this.queue.length){
     this.resize(this.getLength() * 2 + 1)
    }
    this.queue[this.last] = item
    this.size++
    this.last = (this.last+1) % this.queue.length
  }
  deQueue(){
    if(this.isEmpty()){
      throw Error('Queue is empty')
    }
    let r = this.queue[this.first]
    this.queue[this.first] = null
    this.first = (this.first+1) % this.queue.length
    this.size--

    // 判断当前队列大小是否过小
    // 在队列空间等于总长度的1/4时缩小总长度为当前一半
    if(this.size === this.getLength()/4 && this.getLength() / 2 !== 0){
      this.resize(this.getLength() / 2)
    }
    return r
  }
  getHeader() {
      if (this.isEmpty()) {
        throw Error('Queue is empty')
      }
      return this.queue[this.first]
    }
    getLength(){
      return this.queue.length - 1
    }
    isEmpty(){
      return this.first ==== this.last
    }
    resize(length){
     let q = new Array(length)
     for(let i = 0;i < length; i++){
        q[i] = this.queue[(i + this.first) % this.queue.length]
      }
      this.queue = q
      this.first = 0
      this.last = this.size
    }
}

链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


class Node {
  constructor(v, next) {
    this.value = v
    this.next = next
  }
}
class LinkList {
  constructor() {
    // 链表长度
    this.size = 0
    // 虚拟头部
    this.dummyNode = new Node(null, null)
  }
  find(header, index, currentIndex) {
    if (index === currentIndex) return header
    return this.find(header.next, index, currentIndex + 1)
  }
  addNode(v, index) {
    this.checkIndex(index)
    // 当往链表末尾插入时，prev.next 为空
    // 其他情况时，因为要插入节点，所以插入的节点的 next 应该是prev.next
    // 然后设置 prev.next 为插入的节点
    let prev = this.find(this.dummyNode, index, 0)
    prev.next = new Node(v, prev.next)
    this.size++
    return prev.next
  }
  insertNode(v, index) {
    return this.addNode(v, index)
  }
  addToFirst(v) {
    return this.addNode(v, 0)
  }
  addToLast(v) {
    return this.addNode(v, this.size)
  }
  removeNode(index, isLast) {
    this.checkIndex(index)
    index = isLast ? index - 1 : index
    let prev = this.find(this.dummyNode, index, 0)
    let node = prev.next
    prev.next = node.next
    node.next = null
    this.size--
    return node
  }
  removeFirstNode() {
    return this.removeNode(0)
  }
  removeLastNode() {
    return this.removeNode(this.size, true)
  }
  checkIndex(index) {
    if (index < 0 || index > this.size) throw Error('Index error')
  }
  getNode(index) {
    this.checkIndex(index)
    if (this.isEmpty()) return
    return this.find(this.dummyNode, index, 0).next
  }
  isEmpty() {
    return this.size === 0
  }
  getSize() {
    return this.size
  }
}

二叉查找树BST

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Node{
  constructor(value){
    this.value = value
    this.left = null
    this.right = null
  }
}
class BST{
  constructor(){
    this.root = null
    this.size = 0
  }
  getSize(){
      return this.size
  }
  isEmpty(){
     return this.size === 0
  }
  addNode(v) {
    this.root = this._addChild(this.root, v)
  }
  // 添加节点时，需要比较添加的节点值和当前节点值的大小
  _addChild(node, v) {
    if (!node) {
      this.size++
      return new Node(v)
    }
    if (node.value > v) {
      node.left = this._addChild(node.left, v)
    } else if (node.value < v) {
      node.right = this._addChild(node.right, v)
    }
    return node
  }
}

堆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


class MaxHeap{
  constructor(){
    this.heap=[]
  }
  size(){
    return this.heap.length
  }
  empty(){
    return this.size() == 0
  }
  add(item){
    this.heap.push(item)
    this._shiftUp(this.size()-1)
  }
  removeMax(){
    this._shiftDown(0)
  }
  getParentIndex(k){
    return parseInt((k - 1) / 2)
  }
  getLeftIndex(k){
    return k * 2 + 1
  }
  _shiftUp(k){
    // 如果当前节点比父节点大，就交换
    while(this.heap[k]>this.heap[this.getParentIndex(k)]){
      this._swap(k,this.getParentIndex(k))
      // 将索引变成父节点
      k = this.getParentIndex(k)
    }
  }
  _swap(left, right) {
    let rightValue = this.heap[right]
    this.heap[right] = this.heap[left]
    this.heap[left] = rightValue
  }
  _shiftDown(k){
    // 交换首位并删除末尾
    this._swap(k, this.size() - 1)
    this.heap.splice(this.size() - 1, 1)
    // 判断节点是否有孩子，二叉堆有左必有右
    while(this.getLeftIndex(k) < this.size()){
      let j=this.getLeftIndex(k)
      // 判断是否有右孩子 并且右是否比左大
      if(j+1 < this.size() && this.heap[j+1] > this.heap[j])
        j++
      // 判断父节点是否比子节点都大
      if(this.heap[k] >= this.heap[j]) break
      this._swap(k, j)
      k = j
    }
  }
}

二叉树的先序/中序/后序遍历

递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function TreeNode(val){
  this.val = val;
  this.left = this.right = null;
}
var traversal = function(root){
  if(root){
    // 先序
    console.log(root);
    traversal(root.left);
    // 中序 左之后输出
    // console.log(root);
    traversal(root.right);
    // 后序 左右根
    // console.log(root);
  }
}

非递归实现

先序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


function pre(root) {
    if (root) {
        let stack = [];
        stack.push(root); //先push根节点
        while (stack.length > 0) {
          // 弹出栈顶元素
            root = stack.pop();
            console.log(root);

            // 栈是先进后出 先序遍历是先左后右
            // 所以先push右边 再push左边
            if(root.right){
              stack.push(root.right);
            }
            if(root.left){
             stack.push(root.left);
            }
        }
    }
}

中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


function mid(root){
  if(root){
    let stack = [];
    // 中序遍历是左根右
    // 先把左边节点遍历到底 依次push进栈
    // 当左边没有节点时打印栈顶元素 然后寻找右节点
    // 左边打印不出东西就打印父节点，然后看右节点
    while(stack.length>0 || root){
      if(root){
        stack.push(root);
        root = root.left;
      }else{
        root = stack.pop();
        console.log(root);
        root = root.right;
      }
    }
  }
}

后序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


function pos(root){
  if(root){
    let stack1 = [];
    let stack2 = [];
    // 左右根 对于栈来说 先push根节点
    // 然后push右节点 最后左节点
    stack1.push(root);
    while(stack1.length > 0){
      root = stack1.pop();
      stack2.push(root);
      if(root.left){
        stack1.push(root.left);
      }
      if(root.right){
        stack1.push(root.right);
      }
    }
    while(stack2.length > 0){
      console.log(s2.pop());
    }
  }
}

动态规划

解决斐波那契数列问题

斐波那契数列从 0 和 1 开始，那么这就是这个子问题的最底层
通过数组来存储每一位所对应的斐波那契数列的值

1
2
3
4
5
6
7
8
9


function fib(n){
  let array=new Array(n+1).fill(null)
  array[0] = 0
  array[1] = 1
  for(let i=2; i <= n; i++){
    array[i] = array[i-1]+array[i-2]
  }
  return array[n]
}

学习算法时，可视化界面可以帮助我们更好的理解，推荐配合VisualAlgo或Algorithm Visualizer。