共计 2944 个字符，预计需要花费 8 分钟才能阅读完成。
前言：
想零碎学习前端面试题，强烈推荐浏览 在线电子书（反对手机版，不断更新）。
本书特点：零碎全面（涵盖前端核心技术点），简洁，针对性强（针对面试场景设计）。
欢送在 github 上留言反馈
算法
斐波那契数列介绍？
别称：黄金分割数列
从第三位起，每个数字都是前两位数字之和
[3, 5, 8, 13, 21]
// 迭代法生成斐波那契数列
function fib(n) {var fib_n = function(curr, next, n) {if (n == 0) {return curr;}
else {return fib_n(next, curr+next, n-1);
}
}
return fib_n(0, 1, n);
}
alert(fib(40));常见的算法有哪些？
- 排序算法：疾速排序，归并排序、计数排序（8 大排序算法）
- 搜索算法：回溯、递归、剪枝技巧
- 图论：最短树、最小生成树、网络流建模
- 动静布局：背包问题、最长子序列、计数问题
- 根底技巧：分治、倍增、二分、贪婪
参考资料：
互联网公司最常见的面试算法题有哪些？
分治算法？
实用状况：
- 规模放大到肯定水平就能够 容易地解决
- 能够合成为若干个较小的雷同问题，具备 最优子结构性质
- 子问题的解 能够合并 为该问题的解
- 子问题互相独立，子问题不蕴含公共的子问题
实现流程：
相似数学归纳法，找到解决问题的求解方程公式，而后依据方程公式设计递归程序
- 【合成】原问题合成为若干个规模较小，互相独立，与原问题模式雷同的子问题
- 【解决】规模较小而容易则间接解决，否则递归解决子问题（思考随着问题规模增大时的求解办法）
- 【合并】将子问题的解合并的为原问题的解，找到求解的递归函数（各种规模和因子），设计递归程序即可
应用案例：
- 二分搜寻
- 疾速排序
参考资料：
五大罕用算法之一：分治算法
递归算法介绍？
函数中存着调用函数自身的状况，这种景象就叫递归
联想（汉诺塔）：
把用木块（一共 5 块）叠起来的金字塔，转换到另一个柱子上，能够应用一个两头柱子，每次只能挪动一个木块，大木块不能压在小木块下面，最小门路
通用解决思路（步骤）：
- 【实现雷同函数】把一个问题分解成具备雷同解决思路的子问题，能调用一个函数实现
- 【终止条件】函数调用前判断终止条件
参考资料：
动静布局算法？
参考资料：
牛逼了，原来大神都是这样学动静布局的…
贪婪算法介绍？
贪婪算法（贪心法），只思考当下最优解，不思考全局。心愿从：部分最优解 -> 全局最优解，并常常却不是
步骤：
- 【拆分】：把问题拆成若干步骤
- 【每步最优解】每一步都选取以后状态 最好 / 优的抉择（部分最无利的抉择）
- 【循环】重叠出的后果也是最好 / 优的解
联想（找零钱，起码数量）：找零钱：31 块
核心思想：只思考当下最优解，不思考全局
- 找出符合条件中（x≤31），最优抉择：20 元
- 找出符合条件中（x≤11），最优抉择：10 元
- 找出符合条件中（x≤1），最优抉择：1 元
毛病案例：找零钱 41 元
如果此时货币面值里有（25 元，20 元，10 元，5 元，1 元）
- 贪婪算法的策略：25+10+5+1
- 理论最优解策略：20+20+1
长处：
- 简略，高效，省去了为找最优解可能须要穷举操作，通常作为其余算法的辅助算法来应用
毛病：
- 不思考总体，每次选取部分最优解，不再进行回溯解决，所以很少状况下失去最优解
参考资料：
小白带你学 — 贪婪算法（Greedy Algorithm)
回溯算法介绍（属于深度优先搜寻）？
回溯法（试探法）：是一种选优搜寻法，按选优条件向前搜寻，以达到目标。但当摸索到某一步时，发现原来先把并不优或达不到指标，就退回一步从新先把，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态点称为“回溯点”
回溯法属性深度优先搜寻，因为是全局搜寻，复杂度绝对高。
联想：
走迷宫，
- 【试探性执行】先抉择一条路，开始走
- 【发现不通，筹备返回】如果此路不通，再回到（回溯）上一个岔路口
- 【在节点换条路走】再下一条路，直到找到目的地；
参考资料：
小白带你学 — 回溯算法（Back Tracking)
数组排序？
- array 的 sort 办法
- 冒泡排序
常见的排序算法有哪些?
- 冒泡排序:：相邻数对大小调换地位，循环比照两层实现
- 抉择排序：抉择排序是最直观的排序，通过确认一个 key 最大或最小值，再和其余数中找到最大 / 小的值替换到对就地位
- 插入排序：
- 希尔排序
- 归并排序
- 疾速排序：通过一趟排序将待排序记录分隔成独立的两局部，其中一部分记录的数据均比另一部分的数据小，则可别离对这两局部记录持续进行排序，以达到整个序列有序；
- 堆排序
- 计数排序：
- 桶排序
- 基数排序
参考资料（蕴含算法可视化动图）：https://github.com/damonare/S…
冒泡排序
定义：相邻数对大小调换地位，循环比照两层实现
冒泡排序：
抉择排序
定义: 抉择排序是最直观的排序，通过确认一个 key 最大或最小值，再和其余数中找到最大 / 小的值替换到对就地位
算法实现：
- 确认比拟值：默认第一个
- 找到最小数：找到残余数中比比拟值小的数
- 地位替换：把找到的最小值替换到比拟值的地位
- 反复步骤：二层循环
疾速排序
定义：通过一趟排序将待排序记录分隔成独立的两局部，其中一部分记录的数据均比另一部分的数据小，则可别离对这两局部记录持续进行排序，以达到整个序列有序；
算法实现：
- 确认基准：从数列中挑出一个元素，称为‘基准’(pivot)
- 分区操作：小于基准放前，大于基于放后，实现后，基准就位于两头地位
- 递归操作（确认基准 -> 分区操作)：反复下面操作步骤
插入排序
定义：通过构建有序序列，对于未排序数据，在已排序序列中，从后向前扫描，找到相应地位并插入（联想：打扑克牌摸牌过程）
实现：
- 开始：先取第一个元素，默认为有序数列
- 摸牌并比拟：在曾经排序的数列上找到，从后向前查找，发现比他小的数据，就插入在它的前面
希尔排序
是简略插入排序的改进版，它与插入排序的不同之处在于，它会优先比拟间隔较远的元素，别名放大增量排序
定义：希尔排序的外围在于距离序列（可提前设定好，也可动静定义距离序列）的设定
常见的查找算法？
二分查找法
- 应用范畴：找查对象是一个有序的数据结构
- 介绍：在一个有序数据中，将数据折中，每次折中的数据要和查找的数据进行比拟，而后一直的放大查找的范畴，直到查到找或者区间为 0 为止；
-
案例：
- 判断一个字母，数据在数组中的索引；
- 猜数字游戏
线性查找
- 应用范畴：不限
- 特点：简略遍历，判断是否存在
- 案例：判断一个指标对象，在数据中的索引
二叉树介绍？
二叉树是一种十分根底和重要的数据结构
使用：
- 前序：显示目录
- 中序：实现表达式，在编译器底层很用
- 后序：计算目录内的文件及其信息
特点：
- 每个结点的长度都不大于 2
- 每个结点的孩子结点秩序不能任意颠倒
二叉结的遍历办法分类：（要应用到栈、队列、递归等）
- 深度优先遍历
- 广度优先遍历
深度优先遍历和广度优先遍历的区别?
二叉树的遍历概念。
深度优先遍历（DFS）：
定义：从根节点登程，沿着左子树方向进行纵向遍历，直到找到叶子节点为 止。而后右子树节点遍历，直到遍历完所有可达节点为止。
分类：
- 前序：
- 中序：
- 后序：
广度优先遍历（BFS）：
定义：从根节点登程，在横向遍历二叉树的根底上，纵向遍历二叉树的档次；
遍历思维：递归
图示：
上图搜寻程序
DFS:ABDECFG
BFS:ABCDEFG
表达式用二叉树进行示意：
(a+b*c)-d/e
参考资料：https://juejin.im/entry/68449…