一面一面 4:从容应对算法题目:从容应对算法题目
由冯·诺依曼机组成我们知道:数据存储和运算是计算机工作的主要内容。程序=数据结构+算法,所以计算机类工程师必须掌握一定的数据结构和算法知
识。
知识点梳理知识点梳理
常见的数据结构
栈、队列、链表
集合、字典、散列集
常见算法
递归
排序
枚举
算法复杂度分析
算法思维
分治
贪心
动态规划
高级数据结构
树、图
深度优先和广度优先搜索
本小节会带领大家快速过一遍数据结构和算法,重点讲解一些常考、前端会用到的算法和数据结构。
数据结构数据结构
数据结构决定了数据存储的空间和时间效率问题,数据的写入和提取速度要求也决定了应该选择怎样的数据结构。
根据对场景需求的不同,我们设计不同的数据结构,比如:
读得多的数据结构,应该想办法提高数据的读取效率,比如 IP 数据库,只需要写一次,剩下的都是读取;
读写都多的数据结构,要兼顾两者的需求平衡,比如 LRU Cache 算法。
算法是数据加工处理的方式,一定的算法会提升数据的处理效率。比如有序数组的二分查找,要比普通的顺序查找快很多,尤其是在处理大量数据的
时候。
数据结构和算法是程序开发的通用技能,所以在任何面试中都可能会遇见。随着近几年 AI、大数据、小游戏越来越火,Web 前端职位难免会跟数据结
构和算法打交道,面试中也会出现越来越多的算法题目。学习数据结构和算法也能够帮助我们打开思路,突破技能瓶颈。
前端常遇见的数据结构问题前端常遇见的数据结构问题
现在我来梳理下前端常遇见的数据结构:
简单数据结构(必须理解掌握)
有序数据结构:栈、队列、链表,有序数据结构省空间(存储空间小)
无序数据结构:集合、字典、散列表,无序数据结构省时间(读取时间快)
复杂数据结构
树、堆
图
对于简单数据结构,在 ES 中对应的是数组(Array )和对象(Object )。可以想一下,数组的存储是有序的,对象的存储是无序的,但是我要在对象
中根据key 找到一个值是立即返回的,数组则需要查找的过程。
这里我通过一个真实面试题目来说明介绍下数据结构设计。
题目:使用 ECMAScript(JS)代码实现一个事件类Event ,包含下面功能:绑定事件、解绑事件和派发事件。