title: data structures and algorithms
date: 2023-10-07 12:48:44
tags:

时间复杂度与空间复杂度

时间复杂度:函数体执行多少次
O(n)、O(n^2)…
O(logN)：logN就是2的多少次方为N

let i
1
2
3
4
let i=1
while(i<n){
	i*=2
}

空间复杂度：算法在运行过程中临时占用存储空间大小的量度
O(1)：只声明了一个变量，占用的内存为1

1
2
let i=0;
i+=1;

O(n):声明了一个数组，在list数组中添加了n个值，相当于占用了n个单元

1
2
3
4
const list=[]
for(let i=0;i<n;i++){
	list.push(i);
}

O(n^2):相当于一个矩阵，嵌套了两层数组，存储了n^2个变量

1
2
3
4
5
6
7
const a=[]
for(let i=0;i<n;i++){
	a.push([])
	for(let j=0;j<n;j++){
		a[i].push(j);
	}
}

数据结构

栈：后进先出的数据结构

用数组模拟栈，使用push()入栈，pop()出栈

使用场景

比如：
1.十进制转二进制
余数要倒序输出，使用栈余数入栈，然后再出栈，就可以实现余数倒序输出

2.判断字符串的括号是否有效
给你一个字符串里面都是一些括号，判断括号是否是有效的 (((())))))
越靠后的左括号，对应的右括号越靠前
所有左括号入栈，遇到一个右括号，出栈一个左括号，最后栈空了就是合法的

3.函数调用堆栈
最后调用的函数是最先被执行完的

1
2
3
4
5
function greeting(){
	sayHi();
}
function sayHi(){}
greeting()

前端与栈

函数调用堆栈

队列：先进先出的数据结构

用数组模拟队列，使用push()入队，shift()出队

使用场景

比如：
1.食堂排队打饭
先进先出，保证有序

2.JS异步中的任务队列
JS是单线程的，无法同时处理异步中的并发任务
使用任务队列先后处理异步任务

3.计算最近请求次数
有新请求就入队，3000ms前发出的请求出队，队列的长度就是最近请求次数

前端与队列

JS异步中的任务队列

1
2
setTimeout(()=>console.log(1),0);
console.log(2);//2 1

js是单线程的，js引擎从任务队列中拿出一个，如果有异步任务，比如DOM操作，ajax，setTimeout等等，会把异步任务给WebAPIs处理，js引擎继续执行，而WebAPIs会把异步任务的回调函数（比如onclick,setTimeout）继续加在任务队列的后面，而js引擎是从队列前面取任务的，所以异步任务是后执行的。如果回调函数中还有异步任务，会继续做事件的循环。

链表

在模拟链表时，每个节点通常都有一个 val 属性，用来存储节点的值，以及一个指向下一个节点的引用next

1
2
3
4
const a={val:'a'};
const b={val:'b'};
const c={val:'c'};
const d={val:'d'};

单链表

1.遍历链表

1
2
3
4
5
6
7
//定义一个指针p指向a
let p=a;
while(p){
	a.next=b;
	b.next=c;
	c.next=d;
}

2.插入

1
2
3
const e={val:'e'}
c.next=e;
e.next=d;

3.删除

1
c.next=d;

如果只给定了要删除的节点，无法获取要删除节点的上一个节点，解决：将被删除的节点转移到下个节点（下个节点的值先赋值在当前节点）。

前端与链表

JS中的原型链

  1. 如果A沿着原型链能找到B.prototype，那么A instanceof B为true
  2. 如果A对象上没有找到属性，那么会沿着原型链找x属性。
面试题

简述instanceOf的原理，并用代码实现

解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false。

1
2
3
4
5
6
7
8
9
10
11
const instanceOf=(A,B)=>{
    let p=A;
    while(p){
        if(p=B.protoType){
            return true;
        }
        p=p.__proto__;
    }
    return false;
}
instanceOf([],Array)//true

如果A对象上没有找到属性，那么会沿着原型链找x属性

1
2
3
4
5
6
7
8
9
let foo={},
    F=function(){};
Object.prototype.a='value a';
Function.prototype.b='value b';

foo.a//value a
foo.b//undefined
F.a//value a
F.b///value b

使用链表指针获取JSON的节点值

1
2
3
4
5
6
7
8
9
const json={
    a:{b:{c:1}},
    d:{e:2}
}
const path=['d','e'];
let p=json;
path.forEach(k=>{
    p=p[k];
})

集合

一种无序且唯一的数据结构

ES6中有集合，名为Set。 includes()的数组搜索需要线性时间，而字典的has()可以快速搜索，对于数组很大的可以使用Set代替。

常用操作

去重、判断某元素是否在集合中、求交集…

1.去重

1
2
3
const arr=[1,1,2,2]
//想要数组，直接加...将集合转成数组
const arr2=[...new Set(arr)]

2.判断元素是否在集合中

1
2
const set=new Set(arr)
const has=set.has(2)//true

3.求交集

1
2
const set2=new Set([2,3])
const set3=new Set([...set].filter(item=>set2.has(item)))//或者使用数组的includes方法代替集合的has

前端与集合

使用Set对象：new、add、delete、has、size

1
2
3
4
5
6
7
8
9
const set =new Set()
set.add(5)
set.add(5)//只会加一个5，因为是唯一的
const obj={a:1,b:2}//键不加引号是标识符（变量，属性，函数等）加引号是字符串（如果包含不符合标识符的字符作为建，要使用引号）
set.add(obj)
set.add({a:1,b:2})//会加在集合中，因为obj和{'a':1,'b':2}虽然看起来一样，但是他们在内存中的位置不一样，代表不同的对象
set.delete(5)
set.has(5)//返回值false
set.size//2

迭代Set：多种迭代方法（3)、Set和Array互转(2)(1)、求交集/差集

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
//接上面的代码
//迭代方法
for(let item of set){
    console.log(item)//{a:1,b:2}
}
for(let item of set.keys()){
    console.log(item)//{a:1,b:2}
}
for(let item of set.values()){
    console.log(item)//{a:1,b:2}
}
//集合中的key和value值是相同的
for(let [key,value] of set.entries()){
    console.log(key,value)
}

//Set转成Array
const arr=[...set]
const arr1=Array.from(set)
//Array转set
const set1=new Set(arr)

//求交集
const num1=[1,1,2,2]
const num2=[2,2]
const num3=[...new Set(num1)].filter(item=>num2.includes(item))//数组
const num4=[...new Set(num1)].filter(item=>set.has(item))//null

//求差集
const num5=[...new Set(num1)].filter(item=>!num2.includes(item))

字典

与集合类似，字典也是一种存储唯一值的数据结构，但它以键值对的形式来存储，ES6中有字典，名为Map

增

1
2
3
4
5
const map =new Map()
map.set('a','aa')
map.set(1,'num')
let x='xixi'
map.set(x,'value')

删

1
map.delete('a')

改

1
map.set(1,'numvalue')

查

1
map.get(x)