乐趣区

关于面试:前端面试宝典常用算法篇

jiezi

前言：

想零碎学习前端面试题，强烈推荐浏览 在线电子书（反对手机版，不断更新）。

本书特点：零碎全面（涵盖前端核心技术点），简洁，针对性强（针对面试场景设计）。

欢送在 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 大排序算法）
  • 搜索算法：回溯、递归、剪枝技巧
  • 图论：最短树、最小生成树、网络流建模
  • 动静布局：背包问题、最长子序列、计数问题
  • 根底技巧：分治、倍增、二分、贪婪

参考资料：

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

分治算法？

实用状况：

  1. 规模放大到肯定水平就能够 容易地解决
  2. 能够合成为若干个较小的雷同问题，具备 最优子结构性质
  3. 子问题的解 能够合并 为该问题的解
  4. 子问题互相独立，子问题不蕴含公共的子问题

实现流程：

相似数学归纳法，找到解决问题的求解方程公式，而后依据方程公式设计递归程序

  1. 【合成】原问题合成为若干个规模较小，互相独立，与原问题模式雷同的子问题
  2. 【解决】规模较小而容易则间接解决，否则递归解决子问题（思考随着问题规模增大时的求解办法）
  3. 【合并】将子问题的解合并的为原问题的解，找到求解的递归函数（各种规模和因子），设计递归程序即可

应用案例：

  • 二分搜寻
  • 疾速排序

参考资料：

五大罕用算法之一：分治算法

递归算法介绍？

函数中存着调用函数自身的状况，这种景象就叫递归

联想（汉诺塔）：

把用木块（一共 5 块）叠起来的金字塔，转换到另一个柱子上，能够应用一个两头柱子，每次只能挪动一个木块，大木块不能压在小木块下面，最小门路

通用解决思路（步骤）：

  • 【实现雷同函数】把一个问题分解成具备雷同解决思路的子问题，能调用一个函数实现
  • 【终止条件】函数调用前判断终止条件

参考资料：

动静布局算法？

参考资料：

牛逼了，原来大神都是这样学动静布局的…

贪婪算法介绍？

贪婪算法（贪心法），只思考当下最优解，不思考全局。心愿从：部分最优解 -> 全局最优解，并常常却不是

步骤：

  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/S…

冒泡排序

定义：相邻数对大小调换地位，循环比照两层实现

冒泡排序：

抉择排序

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

算法实现：

  • 确认比拟值：默认第一个
  • 找到最小数：找到残余数中比比拟值小的数
  • 地位替换：把找到的最小值替换到比拟值的地位
  • 反复步骤：二层循环

疾速排序

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

算法实现：

  • 确认基准：从数列中挑出一个元素，称为‘基准’(pivot)
  • 分区操作：小于基准放前，大于基于放后，实现后，基准就位于两头地位
  • 递归操作（确认基准 -> 分区操作)：反复下面操作步骤

插入排序

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

实现：

  • 开始：先取第一个元素，默认为有序数列
  • 摸牌并比拟：在曾经排序的数列上找到，从后向前查找，发现比他小的数据，就插入在它的前面

希尔排序

是简略插入排序的改进版，它与插入排序的不同之处在于，它会优先比拟间隔较远的元素，别名放大增量排序

定义：希尔排序的外围在于距离序列（可提前设定好，也可动静定义距离序列）的设定

常见的查找算法？

二分查找法

  • 应用范畴：找查对象是一个有序的数据结构
  • 介绍：在一个有序数据中，将数据折中，每次折中的数据要和查找的数据进行比拟，而后一直的放大查找的范畴，直到查到找或者区间为 0 为止；

  • 案例：

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

线性查找

  • 应用范畴：不限
  • 特点：简略遍历，判断是否存在
  • 案例：判断一个指标对象，在数据中的索引

二叉树介绍？

二叉树是一种十分根底和重要的数据结构

使用：

  • 前序：显示目录
  • 中序：实现表达式，在编译器底层很用
  • 后序：计算目录内的文件及其信息

特点：

  • 每个结点的长度都不大于 2
  • 每个结点的孩子结点秩序不能任意颠倒

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

  • 深度优先遍历
  • 广度优先遍历

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

二叉树的遍历概念。

深度优先遍历（DFS）：

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

分类：

  • 前序：
  • 中序：
  • 后序：

广度优先遍历（BFS）：

定义：从根节点登程，在横向遍历二叉树的根底上，纵向遍历二叉树的档次；

遍历思维：递归

图示：

上图搜寻程序

DFS:ABDECFG

BFS:ABCDEFG

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

(a+b*c)-d/e

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

退出移动版