算法学习与案例
数据结构:计算机存储,组织数据的方式
算法:一系列解决问题的清晰指令
时间复杂度:定性描述该算法的运行时间(一个函数,用大O表示,比如O(1),O(n),O(logN))
O(1)
let i = 0;
i += 1
O(n)
for(let i=0;i<n;i+=1){
console.log(i)
}
O(1)+O(n)=O(n)---先后顺序时间复杂度计算取大的
O(n)*O(n)=O(n^2)---嵌套时间复杂度
for(let i=0;i<n;i+=1){
for(let j=0;j<n;j+=1){
console.log(i,j)
}
}
O(logN)
let i =1;
while(i<n){
console.log(i)
i *= 2;
}
空间复杂度:算法在运行过程中临时占用存储空间大小的度量(一个函数,用大O表示,比如O(1),O(n),O(n^2))
O(1)
let i = 0;
i += 1
O(n)
const list = [];
for(let i=0;i<n;i+=1){
list.push(i)
}
O(n^2)
const matrix = []
for(let i=0;i<n;i+=1){
matrix([]);
for(let j=0;j<n;j+=1){
matrix[i].push(j)
}
}
栈是一个后进先出的数据结构(push,pop)
javascript 中没有栈,但是可以用Array实现栈的所有功能
- 需要后进先出的场景
- 十进制转二进制,判断字符串的括号是否有效,函数调用堆栈
参考 /stack/2.callStack.js
队列是一个先进先出的数据结构(push,pop)
javascript 中没有栈,但是可以用Array实现栈的所有功能
- 需要先进先出的场景
- 食堂排队打饭,js异步中的任务队列,计算最近请求次数
setTimeout(()=>console.log(1),0)
console.log(2)
执行流程:setTimeout丢给webApis处理
主事件执行console.log(2)
webapi将setTimeout结果丢入 Callback Queue(队列)
主事件执行完后,顺序执行队列中的console.log(2)
- 多个元素组成的列表
- 元素存储不连续,用next指针连在一起
- javaScript中没有链表,但是可以用Object模拟链表。
- 数组:增删非首尾元素时,往往需要移动元素。
- 链表:增删非首尾元素,不需要移动元素,只需要更改next的指向即可
原型链的本质是链表
原型链上的节点是各种原型对象,比如 Function.prototype,Object.prototype....
原型链通过__proto__属性链接各种原型对象
obj--__proto__-->Object.prototype--__proto__-->null
func--__proto__-->Function.prototype--__proto__-->Object.prototype--__proto__-->null
arr--__proto__-->Array.prototype--__proto__-->Object.prototype--__proto__-->null
- 如果A沿着原型链能找到B.prototype,那么A instanceof B 为 true
- 如果在A对象上没有找到x属性,那么就会沿着原型链找x属性
集合是一种无序且唯一的数据结构
ES6中有集合,名为Set
集合的常用操作:去重,判断某元素是否在集合中,求交集
- 使用Set对象:new , add , delete , has ,size
- 迭代Set: 多种迭代方法,Set与Array互转,求交集/差集
与集合类似,字典也是一种存储唯一值得数据结构,但它是以键值对的形式来存储
ES6中有字典,名为Map
字典的常用操作:键值对的增删改查。
一种分层数据的抽象模型
前端工作中常见的树包括:Dom ,级联选择 , 树形控件...
JS中没有树,但是可以用Object和Array构建树
树的常用操作:深度/广度优先遍历,先中后序遍历。
- 深度优先遍历:尽可能深的搜索树的分支
- 广度优先遍历:先访问离根节点最近的节点
- 访问根节点。
- 对根节点的children挨个进行深度优先遍历
- 新建一个队列,把根节点入队
- 把队头出队并访问。
- 把对头的children挨个入队
- 重复第二.三步,直到队列为空
树中每个节点最多只能有两个子节点
在JS中通常用Object来模拟二叉树
- 访问根节点
- 对根节点的左子树进行递归先序遍历
- 对根节点的右子树进行递归先序遍历
- 对根节点的左子树进行中序遍历。
- 访问根节点
- 对根节点的右子树进行中序遍历。
- 对根节点的左子树进行后序遍历。
- 对根节点的右子树进行后序遍历。
- 访问根节点
图是网络结构的抽象模型,是一组由边连接的点
图可以表示任何二元关系,比如道路,航班...
JS中没有图,但是可以用Object和Array构建图
图的表示法:邻接矩阵,邻接表,关联矩阵...
尽可能深的搜索图的分支
- 访问根节点
- 对根节点的没有访问过的相邻节点挨个进行深度优先遍历
先访问离根节点最近的节点
- 新建一个队列,把根节点入队
- 把队头出队并访问。
- 把对头的没有访问过的相邻节点入队
- 重复第二.三步,直到队列为空
- 比较所有相邻元素,如果第一个比第二个大,则交换它们
- 一轮下来,可以保证最后一个数是最大的
- 执行n-1轮,就可以完成排序
- 找到数组中的最小值,选中它并将其放置在第一位
- 接着找到第二小的值,选中它并将其放置在第二位
- 以此类推,执行n-1轮
- 从第二个数开始往前比
- 比它大的往后排
- 以此类推进行到最后一个数
- 分:把数组劈成两半,再递归的对子数组进行“分”操作,直到分成一个个单独的数
- 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子树组合并为一个完整数组
- 合并两个有序数组:
- 新建一个空数组res,用于存放最终排序后的数组
- 比较两个有序数组头部,较小者出队并推入res中
- 如果两个数组还有值,就重复第二步
- 分区:从数组中任意选择一个"基准",所有比基准小的元素放在基准前面,比基准大的元素放在基准的后面。
- 递归:递归的对基准前后的子数组进行分区。
- 遍历数组。
- 找到跟目标值相等的元素,就返回它的下标。
- 遍历结束后,如果没有搜索到的目标值,就返回-1。
- 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
- 如果目标值大于或者小于中间元素,则在大于或小于中间元素的那一半数组中搜索
分而治之:将一个问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并以解决原来的问题。
-
场景一:归并排序
- 分:把数组从中间一分为二
- 解:递归的对两个子数组进行归并排序。
- 合:合并有序子数组。
-
场景二:快速排序
- 分:选基准,按基准把数组分成两个子数组。
- 解:递归的对两个子数组进行快速排序。
- 合:对两个子数组进行合并。
动态规划:它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。
- 场景一:斐波那契数列
- 定义子问题:F(n) = F(n-1) + F(n-2)
- 反复执行:从2循环到n,执行上述公式
贪心算法:期盼通过每个阶段的局部最优选择,从而达到全局的最优解,结果并不一定是最优
- 场景一:零钱兑换
回溯算法:一种渐进式寻找并构建问题解决方式的策略。
回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并选择另一个动作,知道讲问题解决。
- 场景一:全排列
- 用递归模拟出所有情况
- 遇到包含重复元素的情况,就回溯
- 收集所有到达递归终点的情况,并返回
练习地址:Leetcode