JavaScript算法&数据结构

JavaScript数据结构和算法,面试手撕代码。

排序

这里基本语法选用ES5了,经测试ES6对性能影响蛮大的。

测试性能: 在执行前打上console.time(label),执行后打上console.timeEnd(label)

随机生成数组:

1
2
3
4
5
6
7
8
function randomArr(lower, upper, num) {
var arr = []
for (var i = 0; i < num; i++)
arr.push(Math.floor(Math.random() * (lower - upper) + upper))
return arr
}

var arr = randomArr(1, 100, 10000)

冒泡排序

156.190ms, O(n2), O(1), 稳定

1
2
3
4
5
6
7
8
function bubbleSort(arr) {
var len = arr.length
for (var i = 0; i < len; i++)
for (var j = 0; j < len - i - 1; j++)
if (arr[j] > arr[j + 1])
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
return arr
}

选择排序

60.689ms, O(n2), O(1), 稳定

1
2
3
4
5
6
7
8
9
10
11
function selectSort(arr) {
var len = arr.length
for (var i = 0; i < len; i++) {
var min = i
for (var j = i; j < len; j++) {
min = arr[j] < arr[min] ? j : min
}
[arr[i], arr[min]] = [arr[min], arr[i]]
}
return arr
}

快速排序

14.673ms, O(nlog2n), O(nlog2n), 不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function quickSort(arr) {
if (arr.length <= 1) return arr
var left = [], right = []
var pivot = Math.floor(arr.length / 2)
var pivotValue = arr.splice(pivot, 1)[0]
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivotValue) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), pivotValue, ...quickSort(right)]
}

拷贝

基本数据类型: undefinedbooleannumberstringnull, symbol

存放在栈内存中的简单数据段,数据大小确定,内存空间大小可以分配,是直接按值存放的,所以可以直接访问。对其进行赋值时,拷贝的是值;修改后它的原始值是不会改变的。

引用类型: object, array

引用类型是存放在堆内存中的,变量实际上是一个存放在栈内存的指针,这个指针指向堆内存中的地址。每个空间大小不一样,要根据情况开进行特定的分配。对其进行赋值时,拷贝的是地址空间;修改后它的原始值会一起改变。

和原数据是否指向同一对象 第一层数据为基本数据类型 原数据中包含子对象
赋值 改变会使原数据一同改变 改变会使原数据一同改变
浅拷贝 改变不会使原数据一同改变 改变会使原数据一同改变
深拷贝 改变不会使原数据一同改变 改变不会使原数据一同改变

示例对象:

1
2
3
4
5
6
7
8
9
10
11
const user = {
name: 'zhaoo',
gender: 0,
social: {
email: 'izhaoo@163.com',
qq: '894519210',
wechat: undefined,
},
vip: null,
friendId: [1, 43, 23, 21]
}

赋值

1
user1 = user

浅拷贝

assign
1
const user1 = Object.assign({}, user)

深拷贝

JSON
1
user1 = JSON.parse(JSON.stringify(user))
递归遍历
1
2
3
4
5
6
7
8
9
10
11
module.exports = function clone(target) {
if (typeof target === 'object') {
let cloneTarget = Array.isArray(target) ? [] : {};
for (const key in target) {
cloneTarget[key] = clone(target[key]);
}
return cloneTarget;
} else {
return target;
}
};

防抖节流

防抖

任务频繁触发的情况下,只有任务触发的间隔超过指定间隔的时候,任务才会执行

搜索补全

1
2
3
4
5
6
7
8
9
function debounce(fn) {
let timeout = null;
return function() {
clearTimeout(timeout);
timeout = setTimeout(() => {
fn.call(this, arguments);
}, 1000);
};
}

节流

指定时间间隔内只会执行一次任务

懒加载监听滚动条位置、发送验证码计时器

1
2
3
4
5
6
7
8
9
10
11
12
13
function throttle(fn) {
let canRun = true;
return function() {
if(!canRun) {
return;
}
canRun = false;
setTimeout( () => {
fn.call(this, arguments);
canRun = true;
}, 1000);
};
}

手写源码

call

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//每个函数有this和args两个默认参数
Function.prototype.myCall = function (context) {
//传入的对象为空(null,number...)时指定为全局环境
var context = context || window
//用this获取调用myCall的函数
//fn.call(a, 'yck', '24') => this = fn
context.fn = this
//args是伪数组,没有slice这个方法
var args = [...arguments].slice(1)
//执行并保存结果
var result = context.fn(...args)
//删除这个fn对象
delete context.fn
//返回结果
return result
}

apply

1
2
3
4
5
6
7
8
9
10
11
12
Function.prototype.myApply = function (context) {
var context = context || window
context.fn = this
var result
if (arguments[1]) {
result = context.fn(...arguments[1])
} else {
result = context.fn()
}
delete context.fn
return result
}

bind

1
2
3
4
5
6
7
8
9
10
11
12
13
Function.prototype.myBind = function (context) {
// if (typeof this !== 'function') {
// throw new TypeError('Error')
// }
var fn = this
var args = [...arguments].slice(1)
return function F() {
if (this instanceof F) {
return new fn(...args, ...arguments)
}
return fn.apply(context, args.concat(...arguments))
}
}

new

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function new() {
let obj = new Object()
let Constructor = [].shift.call(arguments)
obj.__proto__ = Constructor.prototype
let result = Constructor.apply(obj, arguments)
return typeof result === 'object' ? result : obj
}

function student(name, gender) {
this.name = name
this.gender = gender
}

var zhaoo = new(student, 'zhaoo', 'male')
  1. 创建一个空的简单JavaScript对象(即{});
  2. 链接该对象(即设置该对象的构造函数)到另一个对象 ;
  3. 将步骤1新创建的对象作为this的上下文 ;
  4. 如果该函数没有返回对象,则返回this。

数据结构

后进先出 (LIFO)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Stack {
constructor() {
this.stack = []
}
push(item) {
this.stack.push(item)
}
pop() {
this.stack.pop()
}
peek() {
return this.stack[this.getCount() - 1]
}
getCount() {
return this.stack.length
}
isEmpty() {
return this.getCount() === 0
}
}

队列

先进先出 (FIFO)

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
class PriorityQueue {
constructor() {
this.queue = [{
priority
value
}]
}
enQueue(item) {
if (this.isEmpty()) {
this.queue.push(item)
} else {
var flag = false; //判断是否排队
for (let i = this.queue.length - 1; i > 0; i--) {
if (this.queue[i].priority <= item.priority) {
this.queue.splice(i, 0, item)
flag = true
break
}
}
//循环后未入队,优先级最大,插入到第一位
if (!flag) {
this.queue.unshift(item);
}
}
}
}

链表

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
// 节点
function Node (el) {
this.el = el;
this.next = null;
}

// 构造函数
function Link () {
this.head = new Node('head');
}

// 链表结尾追加一个节点
Link.prototype.append = function (el) {
var currNode = this.head;
while (currNode.next != null) {
currNode = currNode.next;
}
currNode.next = new Node(el);
}

// 按节点的值查找节点
Link.prototype.find = function (el) {
var currNode = this.head;
while (currNode && currNode.el != el) {
currNode = currNode.next;
}
return currNode;
}

// 插入一个节点
Link.prototype.insert = function (newEl, oldEl) {
var newNode = new Node(newEl);
var findNode = this.find(oldEl);
if (findNode) {
newNode.next = findNode.next;
findNode.next = newNode;
} else {
throw new Error('找不到给定插入的节点');
}
}

// 展示链表中的元素
Link.prototype.display = function () {
var currNode = this.head.next;
while (currNode) {
console.log(currNode.el);
currNode = currNode.next;
}
}

// 寻找给定节点的前一个节点
Link.prototype.findPrev = function (el) {
var currNode = this.head;
while (currNode.next && currNode.next.el !== el) {
currNode = currNode.next;
}
return currNode;
}

// 删除给定的节点
Link.prototype.remove = function (el) {
var prevNode = this.findPrev (el);
if (prevNode.next != null) {
prevNode.next = prevNode.next.next;
} else {
throw new Error('找不到要删除的节点');
}
}

双向链表

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

// 双链表构造函数
function DNode (el) {
this.el = el;
this.prev = null;
this.next = null;
}

function DLink() {
this.head = new DNode('head');
}

// 在链表结尾添加一个新的节点
DLink.prototype.append = function (el) {
var currNode = this.head;
while (currNode.next != null) {
currNode = currNode.next;
}
var newNode = new Node(el);
newNode.next = currNode.next;
newNode.prev = currNode;
currNode.next = newNode;
}

// 根据节点的值查找链表节点
DLink.prototype.find = function (el) {
var currNode = this.head;
while (currNode && currNode.el != el) {
currNode = currNode.next;
}
return currNode;
}

// 插入一个节点
DLink.prototype.insert = function (newEl, oldEl) {
var newNode = new DNode(newEl);
var currNode = this.find(oldEl);
if (currNode) {
newNode.next = currNode.next;
newNode.prev = currNode;
currNode.next = newNode;
} else {
throw new Error('未找到指定要插入节点位置对应的值!')
}
}


// 顺序展示链表节点
DLink.prototype.display = function () {
var currNode = this.head.next;
while (currNode) {
console.log(currNode.el);
currNode = currNode.next;
}
}

// 查找最后一个节点
DLink.prototype.findLast = function () {
var currNode = this.head;
while (currNode.next != null) {
currNode = currNode.next;
}
return currNode;
}

// 逆序展示链表节点
DLink.prototype.dispReverse = function () {
var currNode = this.head;
currNode = this.findLast();
while (currNode.prev != null) {
console(currNode.el);
currNode = currNode.prev;
}
}

// 删除给定的节点
DLink.prototype.remove = function (el) {
var currNode = this.find(el);
if (currNode && currNode.next != null) {
currNode.prev.next = currNode.next;
currNode.next.prev = currNode.prev;
currNode.next = null;
currNode.previous = null;
} else {
throw new Error('找不到要删除对应的节点');
}
}

循环链表

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
// 循环链表构造函数
function CLink() {
this.head = new Node('head');
this.head.next = this.head;
}

// 向循环链表结尾新增一个节点
CLink.prototype.append = function (el) {
var currNode = this.head;
while (currNode.next != null && currNode.next != this.head) {
currNode = currNode.next;
}
var newNode = new Node(el);
newNode.next = currNode.next;
currNode.next = newNode;
}

// 根据节点的值查找链表节点
CLink.prototype.find = function (el) {
var currNode = this.head;
while (currNode && currNode.el != el && currNode.next != this.head) {
currNode = currNode.next;
}
return currNode;
}

// 插入一个节点
CLink.prototype.insert = function (newEl, oldEl) {
var newNode = new Node(newEl);
var currNode = this.find(oldEl);
if (currNode) {
newNode.next = currNode.next;
currNode.next = newNode;
} else {
throw new Error('未找到指定要插入节点位置对应的值!');
}
}

// 展示链表元素节点
CLink.prototype.display = function () {
var currNode = this.head.next;
while (currNode && currNode != this.head) {
console.log(currNode.el);
currNode = currNode.next;
}
}

// 寻找前一个节点
CLink.prototype.findPrev = function (el) {
var currNode = this.head;
while (currNode.next && currNode.next.el !== el) {
currNode = currNode.next;
}
return currNode;
}

// 删除给定的节点
CLink.prototype.remove = function (el) {
var prevNode = this.findPrev(el);
if (prevNode.next != null) {
prevNode.next = prevNode.next.next;
} else {
throw new Error('找不到要删除的节点');
}
}

集合

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
class Collection {
constructor(data) {
this.collection = new Set(data);
}

add(data) {
this.collection.add(data);
}

get() {
return this.collection;
}

remove(data) {
this.collection.remove(data);
}

has(data) {
return this.collection.has(data);
}

size() {
return this.collection.size;
}

values() {
return this.collection;
}

union(collection) {
let arr1 = Array.from(collection);
let arr2 = Array.from(this.collection);
return new Set(arr1.concat(arr2));
}

intersect(collection) {
let arr = new Set();
this.collection.forEach(element => {
if (collection.has(element)) {
arr.add(element);
}
});
return arr;
}

difference(collection) {
let arr = new Set();
this.collection.forEach(element => {
if (!collection.has(element)) {
arr.add(element);
}
});
return arr;
}

sub(collection) {
if (this.size() < collection.size()) {
return false;
} else {
let res = true;
collection.values().forEach(element => {
if (!this.collection.has(element)) {
res = false;
}
});
return res;
}
}
}

参考资料

js 深拷贝 vs 浅拷贝

如何写出一个惊艳面试官的深拷贝?

查看评论