算法

[TOC]

斐波那契数列介绍？

别称：黄金分割数列

从第三位起，每个数字都是前两位数字之和

[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大排序算法）

• 搜索算法：回溯、递归、剪枝技巧

• 图论：最短树、最小生成树、网络流建模

• 动态规划：背包问题、最长子序列、计数问题

• 基础技巧：分治、倍增、二分、贪心

参考资料：

互联网公司最常见的面试算法题有哪些？

分治算法？

适用情况：

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

冒泡排序

定义：相邻数对大小互换位置，循环对比两层完成

冒泡排序：

img

选择排序

定义:选择排序是最直观的排序，通过确认一个key最大或最小值，再和其他数中找到最大/小的值交换到对就位置

算法实现：

• 确认比较值：默认第一个

• 找到最小数：找到剩余数中比比较值小的数

• 位置替换： 把找到的最小值替换到比较值的位置

• 重复步骤： 二层循环

img

快速排序

定义：通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的数据均比另一部分的数据小，则可分别对这两部分记录继续进行排序，以达到整个序列有序；

算法实现：

• 确认基准：从数列中挑出一个元素，称为‘基准’(pivot)

• 分区操作：小于基准放前，大于基于放后，完成后，基准就位于中间位置

• 递归操作（确认基准->分区操作)：重复上面操作步骤

img

插入排序

定义：通过构建有序序列，对于未排序数据，在已排序序列中，从后向前扫描，找到相应位置并插入（联想：打扑克牌摸牌过程）

实现：

• 开始：先取第一个元素，默认为有序数列

• 摸牌并比较：在已经排序的数列上找到，从后向前查找，发现比他小的数据，就插入在它的后面

希尔排序

是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素，别名缩小增量排序

定义：希尔排序的核心在于间隔序列（可提前设定好，也可动态定义间隔序列）的设定

常见的查找算法？

二分查找法

• 使用范围：找查对象是一个有序的数据结构

• 介绍：在一个有序数据中，将数据折中，每次折中的数据要和查找的数据进行比较，然后不断的缩小查找的范围，直到查到找或者区间为0为止；

• 案例：

  • 判断一个字母，数据在数组中的索引；

  • 猜数字游戏

线性查找

• 使用范围：不限

• 特点：简单遍历，判断是否存在

• 案例：判断一个目标对象，在数据中的索引

二叉树介绍？

二叉树是一种非常基础和重要的数据结构

运用：

• 前序：显示目录

• 中序：实现表达式，在编译器底层很用

• 后序：计算目录内的文件及其信息

特点：

• 每个结点的长度都不大于2

• 每个结点的孩子结点次序不能任意颠倒

二叉结的遍历方法分类：（要使用到栈、队列、递归等）

• 深度优先遍历

• 广度优先遍历

深度优先遍历和广度优先遍历的区别?

二叉树的遍历概念。

深度优先遍历（DFS）：

定义：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为 止。然后右子树节点遍历，直到遍历完所有可达节点为止。

分类：

• 前序：

• 中序：

• 后序：

广度优先遍历（BFS）：

定义：从根节点出发，在横向遍历二叉树的基础上，纵向遍历二叉树的层次；

遍历思想：递归

图示：

img

上图搜索顺序

DFS:ABDECFG

BFS:ABCDEFG

表达式用二叉树进行表示：

(a+bc)-d/*e

img

参考资料： https://juejin.im/entry/6844903456277266446