Lee前端技术栈

题目：写一个函数，输入n,求斐波那契数列的第n项，即F(n)斐波那契数列的定义如下，F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)(n>1), 既： 0，1，1，2，3，5，8，13，21，44，65…

分析：斐波那契数列数列，是1202年由意大利数学家提出，用来描述兔子的增长过程发明的，既该序列是由前两项数值相加而成的。

所以，简单的代码实现就是递归：

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

let fib = n => {
    if (n < 2) {
        return n
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}
fib(0) //   0
fib(1) //   1
fib(2) //   1
fib(5) //   5
fib(6) //   8
fib(10) //   55

我们可以看到代码实现非常的简单，但是存在的问题是执行效率太低了。从上图中可以看到，递归树中太多的值被重新计算。那么如何提高该数列的执行效率呢？答案是动态规划。来看下面的具体代码：

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

let fib = n => {
    let val = []
    for (let i = 0; i <= n;i++) {
        val[i] = 0
    }
    if (n === 1 || n === 2) {
        return 1
    } else {
        val[1] = 1
        val[2] = 2
        for (var i = 3; i <= n; ++i) {
            val[i] = val[i-1] + val[i-2]
        }
        return val[n-1]
    }
}
fib(0) //   0
fib(1) //   1
fib(2) //   1
fib(5) //   5
fib(6) //   8
fib(10) //   55

我们通过val数组来保存中间值结果来优化递归执行效率低的问题。所以这样应该是斐波那契数列的一个优化版本。That’s all.

题目：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

解析：题目中看似比较简单只是计算了一个数字加上1而已，但是这里却有不少的坑，比如：

• 最后加一后是不是需要向前一位进一；
• 加一之后，有那些位需要进一
• 如果一个数字加一后，比原来的数多了一位怎么办。

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

let plusOne = digits => {
    if (!digits.length) {
        return
    }
    //  数字要从后向前遍历
    for (let i = digits.length - 1;i >= 0; i--) {
        //  从后向前加一
        digits[i]++
        if (digits[i] >= 10) {
            //  如果某一位数加一大于等于10，
            //  将本位数改为0，前一位数加一
            digits[i] = 0
        } else {
            //  否则，说明只是简单的加一，直接返回数组极好
            return digits
        }
    }
    //  当出现加完一后，新数要比原数多一位，只需要在最前面加1就好
    digits.unshift(1)
    return digits
}

yes, do you understand?

题目：设计一个支持 push，pop，top操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

  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

  let MinStack = function () { this.data = [] } MinStack.prototype.push = function (x) { this.data.push(x) } MinStack.prototype.pop() = function () { this.data.pop() } MinStack.prototype.top = function () { if (!this.data.length) return return this.data.slice(this.data.length - 1, this.data.length) } MinStack.prototype.getMin = function () { let num = this.data[0] for (let i = 1; i < this.data.length;i++) { if (num >= this.data[i]) { num = this.data[i] } } return num } let stack = new MinStack() stack.push(3) stack.push(1) stack.push(5) stack.push(2) stack.push(4) stack.pop() // 4 stack.top() // 2 stack.getMin() // 1

  That’s all.

题目：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

分析：其实上图中的关系可以看出，杨辉三角的层级比题目要求的索引少1，那么在这个基础上，我们就可以将上一题稍加改造就OK了。

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

let getRow = rowIndex => {
    let result = []
    for (let i = 0; i < rowIndex + 1;i++) {
        let tempArr = []
        for (let j = 0;j < i;j++) {
            let sum = 0
            if (!result[i-1]) {
                sum = 1
            } else {
                let left = result[i-1][j-1] || 0
                let right = result[i-1][j] || 0
                sum = left + sum + right
            }
            tempArr.push(sum || 1)
        }
        result.push(tempArr)
    }
    return result[rowIndex]
}

That’s all!

Promise是解决异步编程的解决方案，比传统的回调解决方案，要更加强大合理。所谓Promise,其实就是一个容器，保存在未来才会结束的事件。从语法上讲，Promise是一个对象。他有俩个特点：
（1）Promise的状态不受外界影响，Promise是一个异步操作，有三种状态，padding，fulfilled, rejected.只有异步操作的结果，可以决定当前的状态是哪一种？任何其他操作都无法改变这个状态。
（2）一旦状态改变就不会再变。任何时候都可以得到这个结果。只能从padding到fulfilled，从padding到rejected.
Promise也有缺点：
（1）一旦创建，就无法取消。创建就会立即执行，无法中途取消。
（2）如果不设置回调，那么Promise内部的错误不会反映到外部。
（3）当Promise处于padding状态的时候，并不能确认进行到什么阶段。
Promise的一些方法：

Promise.prototype.then()

then()方法定义在原型上，他的作用是为Promise实例添加状态时的回调函数。可以有俩个为function的参数，第一个为resolved状态的回调，第二个为rejected状态的回调，他们都是可选的。then()返回一个新的Promise,注意不是原来的那个实例，因此可以采用链式调用，后面接着then()

Promise.prototype.catch()

Promise.prototype.catch()方法是.then(null, rejection)或.then(undefined, rejection)的别名，用于指定发生错误时的回调函数。then()方法指定的回调函数，如果运行中抛出错误，也会被catch()方法捕获。如果then()方法的错误被下一个then()方法的第二个参数捕获，则不会被catch()捕获。。如果 Promise 状态已经变成resolved，再抛出错误是无效的。如果没有使用catch()方法处理错误，那么Promise对象跑出的错误不会传递到外层。另外需要注意的是：在链式调用中，如果前面的then()方法并没有错误，那么就会跳过后面的catch()方法,继续执行后面的then()方法，如果这是出现错误只能被其后面的catch捕获，与前面的catch()无关。还有，当在catch()方法中跑出错误时，本身是不能捕获到错误的，只能是后面的catch()来捕获。

Promise.prototype.finally()

finally()方法的执行，与Promise的状态无关。finally()方法，旨在与不管promise对象最后的状态是什么都会执行的操作。finally方法的回调函数不接受任何参数，这意味着没有办法知道，前面的 Promise 状态到底是fulfilled还是rejected。这表明，finally方法里面的操作，应该是与状态无关的，不依赖于 Promise 的执行结果。

Promise.all()

Promise.all()的参数是一个数组，数组中是一个个Promise实例。当数组中所有的Promise实例的状态都变成fulfilled，Promise的状态才会变成fulfilled，此时返回值是一个数组。反之，只要有一个状态是rejected,那么Promise的状态就会变成rejected，此时返回值是第一个被rejected的实例的返回值。
如果某个promise实例是rejected，但是同时有自己的catch()，那么相对于Promise.all()并不会是rejected状态。而应该是正常返回到Promise.all()的fulfilled状态。

Promise.race()

Promise.race()和Promise.all()相似，他们区别在于。Promise.race()中的Promise实例，只要有一个状态发生变化，那么Promise.race()的状态就会发生变化。

Promise.allSettled()

Promise.allSettled()方法接受一组 Promise 实例作为参数，包装成一个新的 Promise 实例。只有等到所有这些参数实例都返回结果，不管是fulfilled还是rejected，包装实例才会结束。一旦结束，状态总是fulfilled，不会变成rejected。状态变成fulfilled后，Promise 的监听函数接收到的参数是一个数组，每个成员对应一个传入Promise.allSettled()的 Promise 实例。
Promise.allSettle()的最大用处在于：他可以返回所有Promise的结果。

Promise.any()

该方法接受一组 Promise 实例作为参数，包装成一个新的 Promise 实例返回。只要参数实例有一个变成fulfilled状态，包装实例就会变成fulfilled状态；如果所有参数实例都变成rejected状态，包装实例就会变成rejected状态。

Promise.any()跟Promise.race()方法很像，只有一点不同，就是Promise.any()不会因为某个 Promise 变成rejected状态而结束，必须等到所有参数 Promise 变成rejected状态才会结束。

Promise.resolve()

Promise.resolve()的作用是将现有对象转化为Promise对象。
（1）参数是一个Promise对象
此时，什么都不做，返回原来的Promise对象
（2）参数是一个thenable对象

1
2
3
4
5

let thenable = {
    then: function(resolve, reject) {
        resolve(42);
    }
};

Promise.resolve()方法会将这个对象转为 Promise 对象，然后就立即执行thenable对象的then()方法。
（3）参数不是具有then()方法的对象，或根本就不是对象
如果参数是一个原始值，或者是一个不具有then()方法的对象，则Promise.resolve()方法返回一个新的 Promise 对象，状态为resolved。
（4）Promise.resolve()方法允许调用时不带参数，直接返回一个resolved状态的 Promise 对象。所以，如果希望得到一个 Promise 对象，比较方便的方法就是直接调用Promise.resolve()方法。

Promise.reject()

Promise.reject(reason)方法也会返回一个新的 Promise 实例，该实例的状态为rejected。后面可以接catch()方法。

Promise.try()

Promise.try()方法有点像try{}catch{}的用法，可以让同步函数，同步执行，异步函数，异步执行的时候，对于抛出的错误可以捕获。

1
2
3

Promise.try(() => database.users.get({id: userId}))
    .then(...)
    .catch(...)

Promise的应用

加载图片，一旦加载完成，Promise的状态就发生改变。

1
2
3
4
5
6
7
8

const preloadImage = function (path) {
    return new Promise(function (resolve, reject) {
        const image = new Image();
        image.onload  = resolve;
        image.onerror = reject;
        image.src = path;
    });
};

Set, WeakSet, Map, WeakMap都是ES2015提供的新的数据结构。

Set结构

Set类似于数组，但是成员是唯一的，要求没有重复的成员值。Set本身是一种构造函数。用来生成Set数据结构。可以接受一个数组为参数作为初始化。

1
2

let set = new Set([1,2,3,2,1,4])
[...set] // [1,2,3,4]

所以，为数组去重是set结构的一个重要用途。同理，那么也可以为字符串去重。

1
2

[...new Set('aaccdd')].join('')
//  'abc'

向set结构中不会发生类型转化，所以5和’5’是俩个完全不同的值。这是因为set内部对于值的判断类似于精确元算符号(===)但是，也有例外，NaN被认为是相等的俩个值，俩个对象总是不相等的俩个值。

set的属性和方法：

1
2
3
4
5
6

Set.prototype.constructor //    构造函数，默认就是Set函数
Set.prototype.size  //  返回Set成员的数量
Set.prototype.add(value) // 向Set中添加成员
Set.prototype.has(value) // 表示是否为Set成员
Set.prototype.delete(value) //  删除Set成员中的成员，返回是否删除成功true[false]
Set.prototype.clear()   //  清空Set所有成员

set结构的四种遍历方法:
（1）keys()，values()，entries()
keys方法、values方法、entries方法返回的都是遍历器对象,由于 Set 结构没有键名，只有键值（或者说键名和键值是同一个值），所以keys方法和values方法的行为完全一致。
（2）forEach()
Set 结构的实例与数组一样，也拥有forEach方法，用于对每个成员执行某种操作，没有返回值。

WeakSet

WeakSet 结构与 Set 类似，也是不重复的值的集合。但是，它与 Set 有两个区别。

(1)区别1:WeakSet的成员只能是对象，而不能是其他类型的值。
(2)区别2:WeakSet中的对象是弱引用对象，即垃圾回收机制不考虑 WeakSet 对该对象的引用，也就是说，如果其他对象都不再引用该对象，那么垃圾回收机制会自动回收该对象所占用的内存，不考虑该对象还存在于 WeakSet 之中。这是因为垃圾回收机制根据对象的可达性（reachability）来判断回收，如果对象还能被访问到，垃圾回收机制就不会释放这块内存。
(3)区别2:WeakMap是不可以遍历的。
因为WeakMap方法的以上的特点。WeakSet 的成员是不适合引用的，因为它会随时消失。另外，由于 WeakSet 内部有多少个成员，取决于垃圾回收机制有没有运行，运行前后很可能成员个数是不一样的，而垃圾回收机制何时运行是不可预测的。所以，WeakMap只有以下三个方法：

1
2
3

Set.prototype.add(value) // 向Set中添加成员
Set.prototype.has(value) // 表示是否为Set成员
Set.prototype.delete(value) //  删除Set成员中的成员，返回是否删除成功true[false]

Map

Map类似于对象，也是键值的集合。对象是’字符串-值’的对应。Map结构是’值-值’的对应关系，也就是说Map结构的键不仅仅可以是字符串，可以是任意类型的值。是一种更加完善的hash结构。
Map本身就是一个构造函数，可以通过new字段来创建Map,接受一个表示键值对的数组作为参数。

1
2
3
4

let map = new Map([
    ['name', '张三']
    ['age', 21]
])

Map结构的属性和方法

1
2
3
4
5
6

map.size()  //  返回map结构成员的总数
Map.prototype.set(key, value)   //  为Map添加成员
Map.prototype.get(key)   //  为Map成员
Map.prototype.has(key)   //  判断是否为Map成员
Map.prototype.delete(key)   //  删除Map成员
Map.prototype.clear(key)   //  清空Map成员

Map结构的遍历同Set一样，也是有四种方法：
（1）keys()，values()，entries()
keys方法、values方法、entries方法返回的都是遍历器对象,由于 Map 结构没有键名，只有键值（或者说键名和键值是同一个值），所以keys方法和values方法的行为完全一致。
（2）forEach()
Map 结构的实例与数组一样，也拥有forEach方法，用于对每个成员执行某种操作，没有返回值。
Map结构可以同其他数据结构进行相互转化：
（1）Map转为数组：扩展运算符[…map]
（2）数组转为Map: new Map([[‘name’, ‘张三’], [‘age’, 23]])
（3）对象转map：可以通过Object.entries()参照数组转Map,因为Object.entries()返回的是键值对数组
（4）map转对象：通过遍历的方式
（5）map转JSON，

• 键名是字符串：直接通过JSON.stringify()转化为JSON
• 键名是非字符串：选择转为数组 JSON，先将map结构转化为数组，再将数组转化为JSON
  （6）JSON转map同上，只不过是调用JSON.parse()

WeakMap

WeakMap结构与Map结构类似，也是用于生成键值对的集合。但是有俩点区别：
（1）WeakMap只接受对象作为键名（null除外），不接受其他类型的值作为键名。
（2）WeakMap的键名所指向的对象，不计入垃圾回收机制。WeakMap作为临时存储非常方便。WeakMap 弱引用的只是键名，而不是键值。键值依然是正常引用。

题目： 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

分析：在「杨辉三角」中，每个数是它左上方和右上方的数的和。这就是我们要实现的规律。

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

let generate = numRows => {
    let result = []
    for (let i = 0;i < numRows;i++) {
        let tempArr = []
        for (let j = 0; j <= i;j++) {
            let sum = 0
            if (!result[i - 1]) {
                sum = 1
            } else {
                let left = result[i - 1][j - 1] || 0
                let right = result[i - 1][j] || 0
                sum = left + sum + right
            }
            tempArr.push(sum || 1)
        }
        result.push(tempArr)
    }
    return result
}

That’s all!

题目：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

let maxSubArray = nums => {
    if (nums.length <= 1) {
        return nums[0]
    }
    let sum = nums[0]
    for(let i = 1; i < nums.length;i++) {
        if (nums[i - 1] > 0) {
            nums[i] += nums[i - 1]
        }
        sum = sum > nums[i] ? sum : nums[i]
    }
    return sum
}

不知道怎么说什么，所以没有写分析，That’s all.

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

分析：我们首先要创建俩个链表，然后比较俩个链表元素的大小，然后合并为一个新的链表。

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

//  创建链表节点
function Node (val) {
    //  链表元素
    this.val = val
    //  链表元素的指向
    this.next = null
}
//  创建链表
function NodeList () {
    //  表示链表的长度
    this.length = 0
    //  表示链表的头节点
    this.head = null
}
//  实现向列表中添加元素的方法
NodeList.protoType.append = function (data) {
    var node = new Node(data)
    if (!this.head) {
        //  如果不存在头节点，把当前节点作为头节点
        this.head = node
    } else {
        //  如果存在头节点就将每个节点都指向下一个节点
        //  最后将新节点追加到最后
        let current = this.head
        while(current.next) {
            current.next = current
        }
        current.next = node
    }
    this.length++
}
//  创建返回链表的方法
function getList (arr) {
    if (!arr.length) {
        return
    }
    let list = new NodeList()
    for (let i = 0;i < arr.length;i++) {
        list.insert(arr[i])
    }
    return list
}
let l1 = getList([1,2,4])
let l2 = getList([1,3,4])

这里我们就得到了俩个链表l1和l2，应该是这样的：

注意：在写append方法的时候，请不要用箭头函数，箭头函数没有this,会造成错误，本人开发时犯了这样的错，找了很久...
有了这俩个链表，我们可以进入正题，合并这俩个链表，最终得出结果：[1,1,2,3,4,4]:

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

let mergeTwoLists = (l1,l2) => {
    if (l1 === null) {
        return l2
    } else if (l2 === null) {
        return l1
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else if (l1.val > l2.val) {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
    return []
}
mergeTwoLists(l1.head, l2.head)

合并后的链表是这样的。

揭下来，转化为正常的数组：

1
2
3
4
5
6
7
8
9
10

let arrFormat = (data) => {
    let current = data.next
    let arr = []
    while(current) {
        arr.push(current.val)
        current = current.nex
    }
}
arrFormat(mergeTwoLists(l1.head, l2.head))
//  [1,1,2,3,4,4]

至此，完整的链表合并完成，在js中本身没有链表这一数据结构，所以，模拟了链表，链表有俩个属性，val(值)和next(指针)俩个属性。
That’s all!

正在编写中。。。

二叉树和二叉查找树

• 二叉树是一种特殊的保存数据的数据结构。二叉树每个节点的子节点不允许超过两个。可以写出高效的程序在树中插入、查找和删除数据。
• 二叉查找树是一种特殊的二叉树。相对较小的值保存在左节点中，较大的值保存在右节点中。

实现二叉查找树

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

//  先创建一个节点对象
function Node (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
    this.show = show
    //  记数
    this.count = 1
}
function show () {
    return this.data
}
//  创建二叉查找树
function BST () {
    //  初始化根节点为null
    this.root = nul
    //  插入节点
    this.insert = insert
    //  遍历二叉树
    this.inOrder = inOrder
    //  查找指定元素
    this.find = find
    //  查找最小值
    this.getMin = getMin
    //  查找最大值
    this.getMax = getMax
    //  删除节点
    this.remove = remove
    //  更新记数
    this.update = update
}
function insert (data) {
    //  创建一个节点
    var n = new Node(data, null , null)
    //  如果根节点不存在，就把当前节点当作根节点
    if (!this.root) {
        this.root = n
    } else {
        //  否则将根节点设为当前节点
        var current = this.root
        var parent
        while(true) {
            parent = current
            //  如果，插入的数据小于当前节点数据
            //  将插入的数据放到左节点，否则放到右节点
            if (data < current.data) {
                current = current.left
                if (current === null) {
                    parent.left = n
                    break
            } else {
                current = current.right
                if (current === null) {
                    parent.right = n
                    break
                }
            }
        }
    }
}
//  遍历二叉查找树的方式有三种：
//  中序：中序遍历按照节点上的键值，以升序访问 BST 上的所有节点。
//  先序：先序遍历先访问根节点，然后以同样方式访问左子树和右子树。
//  后序：后序 遍历先访问叶子节点，从左子树到右子树，再到根节点。
function inOrder (node) {
    if (!(node === null)) {
        inOrder(node.left)
        inOrder(node.right)
    }
}
// 二叉查找树上查找
// (1)给定值：需要比较该值和当前节点上的值的大小。通过比较，就能确定如果给定值不在当前节点时，该向左遍历还是向右遍历。
// (2)最小值：最小值总在左子节点上，只需要遍历左子节点即可
// (3)最大值：最小值总在右边子节点上，只需要遍历右子节点即可
function find (data) {
    let current = this.root
    while(current !== null) {
        if (current.data === data) {
            return current
        } else if (current.data > data) {
            return current.left
        } else {
            return current.right
        }
    }
    return null
}
function getMin () {
    let current = this.root
    while (!(current.left === null)) {
        current = current.left
    }
    return current.data
}
function getMax () {
    let current = this.root
    while (!(current.right === null)) {
        current = current.right
    }
    return current.data
}
//  删除节点，要先找到要删除的节点
function remove (data) {
    root = removeNode(this.root, data)
}
function removeNode (node, data) {
    if (node === null) {
        return null
    }
    if (node.data === data) {
        // 没有子节点的节点
        if (node.left == null && node.right == null) {
            return null
        }
        // 没有左子节点的节点
        if (node.left == null) {
            return node.right
        }
        // 没有右子节点的节点
        if (node.right == null) {
            return node.left
        }
        //  如果有俩个子节点，要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值
        var tempNode = getSmallest(node.right)
        node.data = tempNode.data
        node.right = removeNode(node.right, tempNode.data)
        return node
    } else if (node.data < data) {
        node.left = removeNode(node.left, data)
        return node
    } else {
        node.right = removeNode(node.right, data)
        return node
    }
}
function getSmallest (node) {
    let current = node
    while (!(current.left === null)) {
        current = current.left
    }
    return current.data
}
function update () {
    var grade = this.find(data)
    grade.count++
    return grade
}

二叉树和二叉查找树的基本不是很复杂，但是想要用好二叉树，会很不容易。且行且珍惜。

题目：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

分析：这种题目应该直接就会想到哈希表法。直接上代码。

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

let firstUniqChar = s => {
    let len = s.length
    //  这里采用的是集合
    let set = new Set()
    for (let i = 0; i < len;i++) {
        set[s[i]] = set[s[i]] ? s[i] + 1 : 1
    }
    for (let j = 0;j < len;j++) {
        if (set[s[j]] === 1) return j
    }
    return -1
}

本题中，空间复杂度为O(1),时间复杂度为O(2N),注意边界值。

集合(set)是一种包含不同元素的数据结构。每个元素只能存在一次，不能有重复元素出现。
• 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
• 如果两个集合的成员完全相同，则称两个集合相等。
• 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。

对集合的几种常见的操作：

• 并集 将两个集合中的成员进行合并，得到一个新集合。
• 交集 两个集合中共同存在的成员组成一个新的集合。
• 补集 属于一个集合而不属于另一个集合的成员组成的集合。

Set类的实现

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

function Set () {
    this.dataStore = []
    //  添加
    this.add = add
    //  删除
    this.remove = remove
    //  长度
    this.size = size
    //  展示
    this.show = show
    //  并集
    this.union = union
    //  交集
    this.intersect = intersect
    //  子集
    this.subset = subset
    // 属于第一个集合但是不属于第二个集合
    this.difference = difference
}
function add (data) {
    if (this.dataStore.indexOf(data) < 0) {
        this.dataStore.push(data)
        return true
    }
    return false
}
function remove (data) {
    let pos = this.dataStore.indexOf(data)
    if (pos > 0) {
        this.dataStore.splice(pos, 1)
        return true
    }
    return false
}
function size () {
    return this.dataStore.length
}
function show () {
    return this.dataStore
}
function union (set) {
    let temp = new Set()
    for (let i = 0;i < this.dataStore.length;i++) {
        temp.add(this.dataStore[i])
    }
    for (let i = 0;i < set.dataStore.length;i++) {
        if (!temp.contains(set.dataStore[i])) {
            temp.dataStore.push(set.dataStore[i])
        }
    }
    return temp
}
function intersect (set) {
    let temp = new Set()
    for(let i = 0;i < this.dataStore.length;i++) {
        if (set.contains(this.dataStore[i])) {
            temp.add(this.dataStore[i])
        }
    }
    return temp
}
function subSet (set) {
    if (this.size() < set.size()) {
        return false
    }
    for(let key of this.dataStore) {
        if (!set.contains(this.dataStore[key])) {
            return false
        }
    }
    return true
}
function contains (data) {
    return this.dataStore.indexOf(data) > -1
}

注：集合的实现相对比较简单。

这是一个简单的问题。key是react用来追踪哪些列表的元素被修改，被添加或者是被删除的辅助标示。在开发过程中我们需要保证某个元素的key在其同级元素中具有唯一性。

在react的diff算法中react会借助元素的key来判断该元素是最新创建的还是被移动而来的，从而减少不必要的元素渲染。除此之外，react还要根据key来判断元素与本地状态的关联关系。

注意点：

• key的值一定要和具体的元素一一对应
• 尽量不要用数组中的index来作为key的值
• 永远不要视图在render的时候用随机数或者是其他的操作来给key加上不稳定的key，这样造成的性能开销比不加key的情况更糟糕。

A higher-order component is a function that takes a component and returns a new component.这是官方给出的关于高阶组件的解释。通俗讲，高阶组件是一个函数接受一个组件返回一个新的组件。

高阶组件的应用场景

• 代码复用，逻辑抽象
• 渲染劫持
• state抽象和更改
• props更改

  实现方式

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

  import React, { Component } from 'react' class WrappedComponent extend Component { return ( <div>这是普通组件</div> ) } const Hoc = WrappedComponent => { // 在此做一些额外的操作 return <WrappedComponent {...this.props}> }

  我们可以看到，Hoc就是一个高阶组件，普通组件WrappedComponent没有什么感知。但是Hoc的出现提高了代码逻辑的复用。

  Hoc和mixin的比较

  mixin的意思是混入。在vue常有这种操作， 而高阶组件属于函数式编程(functional programming)思想，对于被包裹的组件时不会感知到高阶组件的存在，而高阶组件返回的组件会在原来的组件之上具有功能增强的效果。而Mixin这种混入的模式，会给组件不断增加新的方法和属性，组件本身不仅可以感知，甚至需要做相关的处理(例如命名冲突、状态维护)，一旦混入的模块变多时，整个组件就变的难以维护，也就是为什么如此多的React库都采用高阶组件的方式进行开发。