算法 - 前端面试宝典

[TOC]
斐波那契数列介绍？
别称：黄金分割数列
从第三位起，每个数字都是前两位数字之和
[3, 5, 8, 13, 21]
1
    //迭代法生成斐波那契数列
2
    function fib(n) {
3
        var fib_n = function(curr, next, n) {
4
            if (n == 0) {
5
                return curr;
6
            }
7
            else {
8
                return fib_n(next, curr+next, n-1);
9
            }
10
        }
11
        return fib_n(0, 1, n);
12
    }
13
    alert(fib(40));
Copied!
常见的算法有哪些？
排序算法：快速排序，归并排序 、计数排序（8大排序算法）
搜索算法：回溯、递归、剪枝技巧
图论：最短树、最小生成树、网络流建模
动态规划：背包问题、最长子序列、计数问题
基础技巧：分治、倍增、二分、贪心
参考资料：
​互联网公司最常见的面试算法题有哪些？​
分治算法？
适用情况：
1.规模缩小到一定程度就可以容易地解决
2.可以分解为若干个较小的相同问题，具有最优子结构性质
3.子问题的解可以合并为该问题的解
4.子问题相互独立，子问题不包含公共的子问题
实现流程：
类似数学归纳法，找到解决问题的求解方程公式，然后根据方程公式设计递归程序
1.【分解】原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2.【解决】规模较小而容易则直接解决，否则递归解决子问题（考虑随着问题规模增大时的求解方法）
3.【合并】将子问题的解合并的为原问题的解，找到求解的递归函数（各种规模和因子），设计递归程序即可
使用案例：
二分搜索
快速排序
参考资料：
​五大常用算法之一：分治算法​
递归算法介绍？
函数中存着调用函数本身的情况，这种现象就叫递归
联想（汉诺塔）：
把用木块（一共5块）叠起来的金字塔，转换到另一个柱子上，可以使用一个中间柱子，每次只能移动一个木块，大木块不能压在小木块上面，最小路径
通用解决思路（步骤）：
【实现相同函数】把一个问题分解成具有相同解决思路的子问题，能调用一个函数实现
【终止条件】函数调用前判断终止条件
img
参考资料：
动态规划算法？
参考资料：
​牛逼了，原来大神都是这样学动态规划的…​
贪心算法介绍？
贪心算法（贪婪法），只考虑当下最优解，不考虑全局。希望从：局部最优解-> 全局最优解，并经常却不是
步骤：
1.【拆分】：把问题拆成若干步骤
2.【每步最优解】每一步都选取当前状态 最好/优的选择（局部最有利的选择）
3.【循环】堆叠出的结果也是最好/优的解
联想（找零钱，最少数量）：找零钱：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)​
数组排序？
1.array的sort  方法 
2.冒泡排序
常见的排序算法有哪些?
1.冒泡排序: ：相邻数对大小互换位置，循环对比两层完成
2.选择排序：选择排序是最直观的排序，通过确认一个key最大或最小值，再和其他数中找到最大/小的值交换到对就位置
3.插入排序：
4.希尔排序
5.归并排序
6.快速排序：通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的数据均比另一部分的数据小，则可分别对这两部分记录继续进行排序，以达到整个序列有序；
7.堆排序
8.计数排序：
9.桶排序
10.基数排序
参考资料（包含算法可视化动图）：https://github.com/damonare/Sorts​
冒泡排序
定义：相邻数对大小互换位置，循环对比两层完成
冒泡排序：
Could not load image
img
选择排序
定义:选择排序是最直观的排序，通过确认一个key最大或最小值，再和其他数中找到最大/小的值交换到对就位置
算法实现：
确认比较值：默认第一个
找到最小数：找到剩余数中比比较值小的数 
位置替换： 把找到的最小值替换到比较值的位置
重复步骤： 二层循环
img
快速排序
定义：通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的数据均比另一部分的数据小，则可分别对这两部分记录继续进行排序，以达到整个序列有序；
算法实现：
确认基准：从数列中挑出一个元素，称为‘基准’(pivot)
分区操作：小于基准放前，大于基于放后，完成后，基准就位于中间位置
递归操作（确认基准->分区操作)：重复上面操作步骤 
img
插入排序
定义：通过构建有序序列，对于未排序数据，在已排序序列中，从后向前扫描，找到相应位置并插入（联想：打扑克牌摸牌过程）
实现：
开始：先取第一个元素，默认为有序数列
摸牌并比较：在已经排序的数列上找到，从后向前查找，发现比他小的数据，就插入在它的后面
希尔排序
是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素，别名缩小增量排序
定义：希尔排序的核心在于间隔序列（可提前设定好，也可动态定义间隔序列）的设定
常见的查找算法？
二分查找法
使用范围：找查对象是一个有序的数据结构
介绍：在一个有序数据中，将数据折中，每次折中的数据要和查找的数据进行比较，然后不断的缩小查找的范围，直到查到找或者区间为0为止；
案例：
判断一个字母，数据在数组中的索引；
猜数字游戏
线性查找
使用范围：不限
特点：简单遍历，判断是否存在
案例：判断一个目标对象，在数据中的索引
二叉树介绍？
二叉树是一种非常基础和重要的数据结构
运用：
前序：显示目录
中序：实现表达式，在编译器底层很用
后序：计算目录内的文件及其信息
特点：
每个结点的长度都不大于2
每个结点的孩子结点次序不能任意颠倒
二叉结的遍历方法分类：（要使用到栈、队列、递归等）
深度优先遍历
广度优先遍历
深度优先遍历和广度优先遍历的区别?
二叉树的遍历概念。
深度优先遍历（DFS）：
定义：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为 止。然后右子树节点遍历，直到遍历完所有可达节点为止。
分类：
前序：
中序：
后序：
广度优先遍历（BFS）：
定义：从根节点出发，在横向遍历二叉树的基础上，纵向遍历二叉树的层次；
遍历思想：递归
图示：
img
上图搜索顺序
DFS:ABDECFG
BFS:ABCDEFG
表达式用二叉树进行表示：
(a+bc)-d/*e
Could not load image
img
参考资料： https://juejin.im/entry/6844903456277266446​