前端日记

面试官：说说你对算法的理解？应用场景？ 一、是什么算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制 也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出 如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题 一个程序=算法+数据结构，数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的，两者不可分割 因此，算法的设计和选择要同时结合数据结构，简单地说数据结构的设计就是选择存储方式，如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构 针对上述，可以得出一个总结：不同的算法可能用不同的时间、空间或效率来完成同样的任务 二、特性关于算法的五大特性，有如下： 有限性（Finiteness）：一个算法必须保证执行有限步之后结束 确切性（Definiteness）： 一个算法的每一步骤必须有确切的定义 输入（Input）：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件 输出（Output）：一个算法有 ...

面试官：说说你对二分查找的理解？如何实现？应用场景？ 一、是什么在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法 想要应用二分查找法，则这一堆数应有如下特性： 存储在数组中 有序排序 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较 如果在某一步骤数组为空，则代表找不到 这种搜索算法每一次比较都使搜索范围缩小一半 如下图所示： 相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快，区别如下所示： 二、如何实现基于二分查找的实现，如果数据是有序的，并且不存在重复项，实现代码如下： 123456789101112131415161718192021function BinarySearch(arr, target) { if (arr.length <= 1) return -1 // 低位下标 let lowIndex = 0 // 高位 ...

面试官：说说你对堆的理解？如何实现？应用场景？ 一、是什么堆(Heap)是计算机科学中一类特殊的数据结构的统称 堆通常是一个可以被看做一棵完全二叉树的数组对象，如下图： 总是满足下列性质： 堆中某个结点的值总是不大于或不小于其父结点的值 堆总是一棵完全二叉树 堆又可以分成最大堆和最小堆： 最大堆：每个根结点，都有根结点的值大于两个孩子结点的值 最小堆：每个根结点，都有根结点的值小于孩子结点的值 二、操作堆的元素存储方式，按照完全二叉树的顺序存储方式存储在一个一维数组中，如下图： 用一维数组存储则如下： 1[0, 1, 2, 3, 4, 5, 6, 7, 8] 根据完全二叉树的特性，可以得到如下特性： 数组零坐标代码的是堆顶元素 一个节点的父亲节点的坐标等于其坐标除以2整数部分 一个节点的左节点等于其本身节点坐标 * 2 + 1 一个节点的右节点等于其本身节点坐标 * 2 + 2 根据上述堆的特性，下面构建最小堆的构造函数和对应的属性方法： 123456789101112131415161718192021222324252627282930313233343536 ...

面试官：说说你对链表的理解？常见的操作有哪些？ 一、是什么链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点（链表中每一个元素称为结点）组成 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域 节点用代码表示，则如下： 123456class Node { constructor(val) { this.val = val; this.next = null; }} data 表示节点存放的数据 next 表示下一个节点指向的内存空间 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1) 链表的结构也十分多，常见的有四种形式： 单链表：除了头节点和尾节点，其他节点只包含一个后继指针 循环链表：跟单链表唯一 ...

面试官：说说你对冒泡排序的理解？如何实现？应用场景？ 一、是什么冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法 冒泡排序的思想就是在每次遍历一遍未排序的数列之后，将一个数据元素浮上去（也就是排好了一个数据） 如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序” 假如我们要把 12、35、99、18、76 这 5 个数从大到小进行排序，那么数越大，越需要把它放在前面 思路如下： 从后开始遍历，首先比较 18 和 76，发现 76 比 18 大，就把两个数交换顺序，得到 12、35、99、76、18 接着比较 76 和 99，发现 76 比 99 小，所以不用交换顺序 接着比较 99 和 35，发现 99 比 35 大，交换顺序 接着比较 99 和 12，发现 99 比 12 大，交换顺序 最终第 1 趟排序的结果变成了 99、12、35、76、18，如下图所示： 上述可以看到，经过第一趟的排序，可以得到最大的元素，接下来第二趟排序则对剩下的的4个元素进行排序，如下图所示： 经过第 2 趟排序，结果为 99、76、12、35、18 然 ...

面试官：说说你对分而治之、动态规划的理解？区别？ 一、分而治之分而治之是算法设计中的一种方法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并 关于分而治之的实现，都会经历三个步骤： 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题 合并：将各子问题的解合并为原问题的解 实际上，关于分而治之的思想，我们在前面已经使用，例如归并排序的实现，同样经历了实现分而治之的三个步骤： 分解：把数组从中间一分为二 解决：递归地对两个子数组进行归并排序 合并：将两个字数组合并称有序数组 同样关于快速排序的实现，亦如此： 分：选基准，按基准把数组分成两个字数组 解：递归地对两个字数组进行快速排序 合：对两个字数组进行合并 同样二分搜索也能使用分而治之的思想去实现，代码如下： 12345678910111213function binarySearch(arr,l,r,target){ if(l> r) ...

面试官：说说你对贪心算法、回溯算法的理解？应用场景？ 一、贪心算法贪心算法，又称贪婪算法，是算法设计中的一种思想 其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的 举个零钱兑换的例子，如果你有1元、2元、5元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最少 如果现在你要兑换11元，按照贪心算法的思想，先选择面额最大的5元钱币进行兑换，那么就得到11 = 5 + 5 + 1 的选择，这种情况是最优的 但是如果你手上钱币的面额为1、3、4，想要兑换6元，按照贪心算法的思路，我们会 6 = 4 + 1 + 1这样选择，这种情况结果就不是最优的选择 从上面例子可以看到，贪心算法存在一些弊端，使用到贪心算法的场景，都会存在一个特性： 一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法 至于是否选择贪心算法，主要看是否有如下两大特性： 贪心选择：当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择 最优子结构：如果一个问题的最优解包含 ...

面试官：说说你对图的理解？相关操作有哪些？ 一、是什么在计算机科学中，图是一种抽象的数据类型，在图中的数据元素通常称为结点，V是所有顶点的集合，E是所有边的集合 如果两个顶点v, w，只能由v向w，而不能由w向v，那么我们就把这种情况叫做一个从 v 到 w 的有向边。v 也被称做初始点，w也被称为终点。这种图就被称做有向图 如果v和w是没有顺序的，从v到达w和从w到达v是完全相同的，这种图就被称为无向图 图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系 常见表达图的方式有如下： 邻接矩阵 邻接表 邻接矩阵通过使用一个二维数组G[N][N]进行表示N个点到N-1编号，通过邻接矩阵可以立刻看出两顶点之间是否存在一条边，只需要检查邻接矩阵行i和列j是否是非零值，对于无向图，邻接矩阵是对称的 邻接表存储方式如下图所示： 在javascript中，可以使用Object进行表示，如下： 123456789const graph = { A: [2, 3, 5], B: [2], C: [0, 1, 3], ...

面试官：说说你对插入排序的理解？如何实现？应用场景？ 一、是什么插入排序（Insertion Sort），一般也被称为直接插入排序。对于少量元素的排序，它是一个有效、简单的算法 其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据 插入排序的工作方式像许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下 然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置，该正确位置需要从右到左将它与已在手中的每张牌进行比较 例如一个无序数组 3、1、7、5、2、4、9、6，将其升序的结果则如下： 一开始有序表中无数据，直接插入3 从第二个数开始，插入一个元素1，然后和有序表中记录3比较，1<3，所以插入到记录 3 的左侧 向有序表插入记录 7 时，同有序表中记录 3 进行比较，3<7，所以插入到记录 3 的右侧 向有序表中插入记录 5 时，同有序表中记录 7 进行比较，5<7，同时 5>3，所以插入到 3 和 7 中间 照此规律，依次将无序表中的记录 4，9 和 6插入到有序表中 二、如何实现 ...

面试官：说说你对归并排序的理解？如何实现？应用场景？ 一、是什么归并排序（Merge Sort）是建立归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用 将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序 例如对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1） 然后进行两两合并，使 n 个有序表变为n/2 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表） 通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止 例如对无序表{49，38，65，97，76，13，27}进行归并排序分成了分、合两部分： 如下图所示： 归并合过程中，每次得到的新的子表本身有序，所以最终得到有序表 上述分成两部分，则称为二路归并，如果分成三个部分则称为三路归并，以此类推 二、如何实现关于归并排序的算法思路如下： 分：把数组分成两半，再递归对子数组进行分操作，直至到一个个单独数字 合：把两个数合成有序数组，再对有序数组进行合并操作，直到全部子数组合成一个完整的数组 ...