美团前端一面必会手写面试题汇总

手写 Promise

const PENDING = "pending";
const RESOLVED = "resolved";
const REJECTED = "rejected";

function MyPromise(fn) {
   
  // 保存初始化状态
  var self = this;

  // 初始化状态
  this.state = PENDING;

  // 用于保存 resolve 或者 rejected 传入的值
  this.value = null;

  // 用于保存 resolve 的回调函数
  this.resolvedCallbacks = [];

  // 用于保存 reject 的回调函数
  this.rejectedCallbacks = [];

  // 状态转变为 resolved 方法
  function resolve(value) {
   
    // 判断传入元素是否为 Promise 值，如果是，则状态改变必须等待前一个状态改变后再进行改变
    if (value instanceof MyPromise) {
   
      return value.then(resolve, reject);
    }

    // 保证代码的执行顺序为本轮事件循环的末尾
    setTimeout(() => {
   
      // 只有状态为 pending 时才能转变，
      if (self.state === PENDING) {
   
        // 修改状态
        self.state = RESOLVED;

        // 设置传入的值
        self.value = value;

        // 执行回调函数
        self.resolvedCallbacks.forEach(callback => {
   
          callback(value);
        });
      }
    }, 0);
  }

  // 状态转变为 rejected 方法
  function reject(value) {
   
    // 保证代码的执行顺序为本轮事件循环的末尾
    setTimeout(() => {
   
      // 只有状态为 pending 时才能转变
      if (self.state === PENDING) {
   
        // 修改状态
        self.state = REJECTED;

        // 设置传入的值
        self.value = value;

        // 执行回调函数
        self.rejectedCallbacks.forEach(callback => {
   
          callback(value);
        });
      }
    }, 0);
  }

  // 将两个方法传入函数执行
  try {
   
    fn(resolve, reject);
  } catch (e) {
   
    // 遇到错误时，捕获错误，执行 reject 函数
    reject(e);
  }
}

MyPromise.prototype.then = function(onResolved, onRejected) {
   
  // 首先判断两个参数是否为函数类型，因为这两个参数是可选参数
  onResolved =
    typeof onResolved === "function"
      ? onResolved
      : function(value) {
   
          return value;
        };

  onRejected =
    typeof onRejected === "function"
      ? onRejected
      : function(error) {
   
          throw error;
        };

  // 如果是等待状态，则将函数加入对应列表中
  if (this.state === PENDING) {
   
    this.resolvedCallbacks.push(onResolved);
    this.rejectedCallbacks.push(onRejected);
  }

  // 如果状态已经凝固，则直接执行对应状态的函数

  if (this.state === RESOLVED) {
   
    onResolved(this.value);
  }

  if (this.state === REJECTED) {
   
    onRejected(this.value);
  }
};

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

二叉树层次遍历

// 二叉树层次遍历

class Node {
   
  constructor(element, parent) {
   
    this.parent = parent // 父节点 
    this.element = element // 当前存储内容
    this.left = null // 左子树
    this.right = null // 右子树
  }
}

class BST {
   
  constructor(compare) {
   
    this.root = null // 树根
    this.size = 0 // 树中的节点个数

    this.compare = compare || this.compare
  }
  compare(a,b) {
   
    return a - b
  }
  add(element) {
   
    if(this.root === null) {
   
      this.root = new Node(element, null)
      this.size++
      return
    }
    // 获取根节点 用当前添加的进行判断 放左边还是放右边
    let currentNode = this.root 
    let compare
    let parent = null 
    while (currentNode) {
   
      compare = this.compare(element, currentNode.element)
      parent = currentNode // 先将父亲保存起来
      // currentNode要不停的变化
      if(compare > 0) {
   
        currentNode = currentNode.right
      } else if(compare < 0) {
   
        currentNode = currentNode.left
      } else {
   
        currentNode.element = element // 相等时 先覆盖后续处理
      }
    }

    let newNode = new Node(element, parent)
    if(compare > 0) {
   
      parent.right = newNode
    } else if(compare < 0) {
   
      parent.left = newNode
    }

    this.size++
  }
  // 层次遍历 队列
  levelOrderTraversal(visitor) {
   
    if(this.root == null) {
   
      return
    }
    let stack = [this.root]
    let index = 0 // 指针 指向0
    let currentNode 
    while (currentNode = stack[index++]) {
   
      // 反转二叉树
      let tmp = currentNode.left
      currentNode.left = currentNode.right
      currentNode.right = tmp
      visitor.visit(currentNode.element)
      if(currentNode.left) {
   
        stack.push(currentNode.left)
      }
      if(currentNode.right) {
   
        stack.push(currentNode.right)
      }
    
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91