乐趣区

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

前言:

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

本书特点:零碎全面(涵盖前端核心技术点),简洁,针对性强(针对面试场景设计)。

欢送在 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…

退出移动版