一、时间复杂度
算法的时间复杂度是一个函数,它定性描述该算法的运行时间。
1 | O(1): |
1 | O(n) |
1 | O(n2) |
1 | O(logN) |
二、空间复杂度
算法在运行过程中临时占用存储空间大小的量度
1 | O(1): |
1 | O(n): |
三、数据结构:栈
一个后进先出的数据结构
push:入栈
pop:出栈
应用场景:十进制转二进制、判断字符串的括号是否有效、函数调用堆栈
1 | 场景一 |
1 | 解法1 |
1 | 解法2 |
总结
此题的解题思路是入栈和出栈。
左括号代表入栈,对应的右括号代表出栈,对于stack数组进行push()和pop()操作。最后数组长度为0的话,则满足题目要求,return true。
第一次写好后,虽然题目中的测试用例通过了,但是提交之后没有通过如下测试用例。
输入:”([}}])”
主要是因为在判断右括号不是同类型后,没有直接return false,代码还在执行下去,倒数两个字符‘])’刚好和正数两个字符是同类型闭合,就执行pop()最后变成空数组。
还有一个需要注意的是,审题不够仔细,“字符串可被认为是有效字符串”题目有提到了,但看了一眼没注意,写的时候自然也没考虑到这点。但测试用例是通过的,所以没什么问题。
之后审题要认真一些,一些边界情况要多考虑。
还有一点,执行之后执行用时虽然挺快的,但内存消耗偏大,大概是因为定义了两个对象存储括号吧。
看官方解题法,用的是哈希映射(HashMap)存储,此外他的思路是:哈希映射的键为右括号,值为相同类型的左括号。
这个比我的设计要好。
四、数据结构:队列
一个先进先出的数据结构
1、应用场景:食堂排队打饭、JS异步中的任务队列、计算最近请求次数
2、JS异步中的任务队列:JS是单线程,无法同时处理异步中的并发任务
输入:inputs = [[],[1],[100],[3001],[3002]]
输出:[null,1,2,3,3]
1 | const queue = []; |
1 | 代码:本质队列问题 |
总结
队列问题,虽然写出来了,但是因为之前看过题解。有几个点掌握的不好:1、构造函数this.q的用法2、怎么快速分析问题,转化为代码逻辑,这需要锻炼
五、数据结构:链表
多个元素组成的列表;元素存储不连续,用next指针连在一起
1、优点:增删非首尾元素,不需要移动元素,只需要更改next的指向即可
2、代码
1 | 场景一: |
3、原型链知识点:
如果A沿着原型链能找到B.prototype,那么A instanceof B为true
1 | let a = () => {} |
如果在A对象上没有找到x属性,那么会沿着原型链找x属性
1 | const obj = {} |
4、使用链表指针获取JSON的节点值
1 | const json = { |
5、leetcode:237、206、2、83、141、
面试题
1、instanceof的原理,并用代码实现
知识点:如果A沿着原型链能找到B.prototype,那么A instanceof B为true
解法:遍历A的原型链,如果找到B.proptype,返回true,否则false
1 | const instanceof = (A,B) => { |
2、
知识点:如果在A对象上没有找到x属性,那么会沿着原型链找x属性
解法:明确foo和F变量的原型链,沿着原型链找a属性和b属性
1 | let foo = {} |
总结
1、链表里的元素存储是不连续的,通过next()连接
2、Javascript中没有链表,但可以用Object模拟链表
3、链表常用操作:修改next()、遍历链表
4、js中的原型链也是一个链表,
5、使用链表指针可以获取JSON的节点值
六、数据结构:集合
一种无序且唯一的数据结构Es6中有集合,名为Set;集合的常用操作:去重、判断某元素是否在集合中、求交集
1、代码
1 | // 去重 |
2、set操作
使用Set对象:new、add、delete、has、size
迭代Set:多种迭代方法、Set与Array互传、求交集/差集
1 | let mySet = new Set(); |
3、leetcode:349
七、数据结构:字典
与集合类似,字典也是一种存储唯一值的数据结构,但它是以键值对的形式存储
Es6中有字典,名为Map
1 | const m = new Map(); |
2、leetcode:349、20、1、3、76
八、数据结构:树
树:一种分层数据的抽象模型。(前端工作中常见的树:Dom树、级联选择、树形控件……)JS中没有树,但是可以用Object和Array构建树。树的常用操作:深度/广度优先遍历、先中后序遍历
1、树的深度/广度优先遍历
深度优先遍历:尽可能深的探索树的分支遍历方法(递归):1、访问根节点;2、对根节点的children挨个进行深度优先遍历
1 | dfs: |
广度优先遍历:先访问离根节点最近的节点遍历方法:1、新建一个队列,把根节点入队;2、把队头出队并访问;3、把队头的children挨个入队;4、重复第二、三步,直到队列为空
1 | bfs: |
1 | Json: |
2、二叉树的先中后序遍历
二叉树:树中每个节点最多只能有两个节点在JS中通常用Object模拟二叉树
1 | const binaryTree = { |
先序遍历:1、访问根节点;2、对根节点的左子树进行先序遍历;3、对根节点的右子树进行先序遍历;
1 | preorder: |
中序遍历:1、对根节点的左子树进行中序遍历;2、访问根节点;3、对根节点的右子树进行中序遍历;
1 | inorder: |
后序遍历:1、对根节点的左子树进行后序遍历;2、对根节点的右子树进行后序遍历;3、访问根节点;
1 | postorder: |
1 | JSON: |
3、leecode
104、111、102、94、112
算法题待补充
遍历JSON的所有节点值
1 | const json = { |
渲染Antd树组件
九、数据结构:图
图是网络结构的抽象模型,是一组由边连接的节点。图可以表示任何二元关系,比如道路、航班……
JS中没有图,但是可以用Object和Array构建图
1、图的表示法:邻接矩阵、邻接表、关联矩阵……
2、图的常用操作:深度优先遍历、广度优先遍历
深度优先遍历:1、访问根节点;2、对根节点的没访问过的相邻节点挨个进行深度优先遍历
1 | dfs: |
1 | Json: |
广度优先遍历:1、新建一个队列,把根节点入队;2、把队头出队并访问;3、把队头的没访问过的相邻节点入队;4、重复二三步,直到队列为空
1 | bfs: |
leetcode
65、417、133
十、数据结构:堆
一种特殊的完全二叉树
结构特性:二叉堆,树的每一层都有左侧和右侧子节点(除了最后一层的叶节点),并且最后一层的叶节点尽可能都是左侧子节点。
堆特性:所有的节点都大于等于(最大堆)或小于等于(最小堆)每个它的子节点。
JS中通常用数组表示堆:
左侧子节点的位置是2index+1
右侧子节点的位置是2index+2
父节点的位置是(index-1)/2的商
堆能高效找出最大值和最小值,O(1),找出第K个最大(小)元素
实现最小堆
将值插入堆的底部,即数组的尾部
然后上移:将这个值和他的父节点进行交换,直到父节点小于等于这个插入的值
大小为K的堆中插入元素的时间复杂度为O(logK)
1 | class MinHeap { |
删除堆顶
用数组尾部元素替换堆顶(直接删除堆顶会破坏堆数据结构)
然后下移:将新堆顶和他的子节点进行交换,直到子节点大于等于这个新堆顶
大小为K的堆中删除堆顶的时间复杂度为O(logK)
1 | class MinHeap { |
获取堆顶和堆的大小
1 | peek(){ |
leetcode
215、347、23
ps:
vscode小技巧:打断点,点击F5就能运行