2021秋季校招前端面试题之算法高频面试题集锦
最近越来越多的小伙伴开始了秋招面试之旅，相信大家在面试中，也常常会被问到算法。本篇文章将为大家分享一些关于在前端面试中出现频率比较高的算法题。
举例说明你对尾递归的理解，以及有哪些应用场景？
一、递归
递归（英语：Recursion）
在数学与计算机科学中，是指在函数的定义中使用函数自身的方法
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数
其核心思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
一般来说，递归需要有边界条件、递归前进阶段和递归返回阶段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回
下面实现一个函数 pow(x, n)，它可以计算 x 的 n 次方
使用迭代的方式，如下：
function pow(x, n) {let result = 1;// 再循环中，用 x 乘以 result n 次for (let i = 0; i < n; i++) {result *= x;}return result;}
使用递归的方式，如下：
function pow(x, n) {if (n == 1) {return x;} else {return x * pow(x, n - 1);}}
pow(x, n) 被调用时，执行分为两个分支：
if n==1 = x/pow(x, n) =\else = x * pow(x, n - 1)
也就是说pow 递归地调用自身 直到 n == 1
为了计算 pow(2, 4)，递归变体经过了下面几个步骤：
pow(2, 4) = 2 * pow(2, 3)pow(2, 3) = 2 * pow(2, 2)pow(2, 2) = 2 * pow(2, 1)pow(2, 1) = 2
因此，递归将函数调用简化为一个更简单的函数调用，然后再将其简化为一个更简单的函数，以此类推，直到结果
二、尾递归
尾递归，即在函数尾位置调用自身（或是一个尾调用本身的其他函数等等）。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数
尾递归在普通尾调用的基础上，多出了2个特征：
在尾部调用的是函数自身
可通过优化，使得计算仅占用常量栈空间
在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出
这时候，我们就可以使用尾递归，即一个函数中所有递归形式的调用都出现在函数的末尾，对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误
实现一下阶乘，如果用普通的递归，如下：
function factorial(n) {if (n === 1) return 1;return n * factorial(n - 1);}factorial(5) // 120
如果n等于5，这个方法要执行5次，才返回最终的计算表达式，这样每次都要保存这个方法，就容易造成栈溢出，复杂度为O(n)
如果我们使用尾递归，则如下：
function factorial(n, total) {if (n === 1) return total;return factorial(n - 1, n * total);}factorial(5) // 120
可以看到，每一次返回的就是一个新的函数，不带上一个函数的参数，也就不需要储存上一个函数了。尾递归只需要保存一个调用栈，复杂度 O(1)
二、应用场景
数组求和
function sumArray(arr, total) {if(arr.length === 1) {return total}return sum(arr, total + arr.pop())}
使用尾递归优化求斐波那契数列
function factorial2 (n, start = 1, total = 1) {if(n <= 2){return total}return factorial2 (n -1, total, total + start)}
数组扁平化
let a = [1,2,3, [1,2,3, [1,2,3]]]// 变成let a = [1,2,3,1,2,3,1,2,3]// 具体实现function flat(arr = [], result = []) {arr.forEach(v => {if(Array.isArray(v)) {result = result.concat(flat(v, []))}else {result.push(v)}})return result}
数组对象格式化
let obj = {a: '1',b: {c: '2',D: {E: '3'}}}// 转化为如下：let obj = {a: '1',b: {c: '2',d: {e: '3'}}}// 代码实现function keysLower(obj) {let reg = new RegExp("([A-Z]+)", "g");for (let key in obj) {if (obj.hasOwnProperty(key)) {let temp = obj[key];if (reg.test(key.toString())) {// 将修改后的属性名重新赋值给temp，并在对象obj内添加一个转换后的属性temp = obj[key.replace(reg, function (result) {return result.toLowerCase()})] = obj[key];// 将之前大写的键属性删除delete obj[key];}// 如果属性是对象或者数组，重新执行函数if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {keysLower(temp);}}}return obj;};
实现一个函数，判断输入是不是回文字符串？
解法一
function isPlalindrome(input) {if (typeof input !== 'string') return false;return input.split('').reverse().join('') === input;}
解法二
function isPlalindrome(input) {if (typeof input !== 'string') return false;let i = 0, j = input.length - 1while(i < j) {if(input.charAt(i) !== input.charAt(j)) return falsei ++j --}return true}
什么是时间复杂度？
时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。
随着n的不断增大，时间复杂度不断增大，算法花费时间越多。
常见的时间复杂度
常数阶O(1)
对数阶O(log2 n)
线性阶O(n)
线性对数阶O(n log2 n)
平方阶O(n^2)
立方阶O(n^3)
k次方阶O(n^K)
指数阶O(2^n)
计算方法
选取相对增长最高的项
最高项系数是都化为1
若是常数的话用O(1)表示
举个例子：如f(n)=3*n^4+3n+300 则 O(n)=n^4
通常我们计算时间复杂度都是计算最坏情况。计算时间复杂度的要注意的几个点:
如果算法的执行时间不随n的增加而增长，假如算法中有上千条语句，执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
举例如下：代码执行100次，是一个常数，复杂度也是O(1)。
let x = 1;while (x <100) {x++;}
有多个循环语句时候，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的方法决定的。
举例如下：在下面for循环当中，外层循环每执行一次，内层循环要执行n次，执行次数是根据n所决定的，时间复杂度是O(n^2)。
for (i = 0; i < n; i++){for (j = 0; j < n; j++) {// ...code}}
循环不仅与n有关，还与执行循环判断条件有关。
举例如下：在代码中，如果arr[i]不等于1的话，时间复杂度是O(n)。如果arr[i]等于1的话，循环不执行，时间复杂度是O(0)。
for(var i = 0; i<n && arr[i] !=1; i++) {// ...code}
请手写“冒泡排序”。
算法描述
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) { //相邻元素两两对比var temp = arr[j+1]; //元素交换arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
改进冒泡排序
设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
function bubbleSort2(arr) {console.time('改进后冒泡排序耗时');var i = arr.length-1; //初始时,最后位置保持不变while ( i> 0) {var pos= 0; //每趟开始时,无记录交换for (var j= 0; j< i; j++)if (arr[j]> arr[j+1]) {pos= j; //记录交换的位置var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;}i= pos; //为下一趟排序作准备}console.timeEnd('改进后冒泡排序耗时');return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
继续优化
传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
function bubbleSort3(arr3) {var low = 0;var high= arr.length-1; //设置变量的初始值var tmp,j;console.time('2.改进后冒泡排序耗时');while (low < high) {for (j= low; j< high; ++j) //正向冒泡,找到最大者if (arr[j]> arr[j+1]) {tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;}--high; //修改high值, 前移一位for (j=high; j>low; --j) //反向冒泡,找到最小者if (arr[j]<arr[j-1]) {tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;}++low; //修改low值,后移一位}console.timeEnd('2.改进后冒泡排序耗时');return arr3;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
请手写“选择排序”
算法简介
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
代码实现
function selectionSort(arr) {var len = arr.length;var minIndex, temp;console.time('选择排序耗时');for (var i = 0; i < len - 1; i++) {minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) { //寻找最小的数minIndex = j; //将最小数的索引保存}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}console.timeEnd('选择排序耗时');return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析
最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
请手写“插入排序”
算法简介
插入排序（Insertion-Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
代码实现
function insertionSort(array) {if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {console.time('插入排序耗时：');for (var i = 1; i < array.length; i++) {var key = array[i];var j = i - 1;while (j >= 0 && array[j] > key) {array[j + 1] = array[j];j--;}array[j + 1] = key;}console.timeEnd('插入排序耗时：');return array;} else {return 'array is not an Array!';}}
改进插入排序
查找插入位置时使用二分查找的方式
function binaryInsertionSort(array) {if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {console.time('二分插入排序耗时：');for (var i = 1; i < array.length; i++) {var key = array[i], left = 0, right = i - 1;while (left <= right) {var middle = parseInt((left + right) / 2);if (key < array[middle]) {right = middle - 1;} else {left = middle + 1;}}for (var j = i - 1; j >= left; j--) {array[j + 1] = array[j];}array[left] = key;}console.timeEnd('二分插入排序耗时：');return array;} else {return 'array is not an Array!';}}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析
最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)
请手写“希尔排序”
算法简介
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现
function shellSort(arr) {var len = arr.length,temp,gap = 1;console.time('希尔排序耗时:');while(gap < len/5) { //动态定义间隔序列gap =gap*5+1;}for (gap; gap > 0; gap = Math.floor(gap/5)) {for (var i = gap; i < len; i++) {temp = arr[i];for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {arr[j+gap] = arr[j];}arr[j+gap] = temp;}}console.timeEnd('希尔排序耗时:');return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析
最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) =O(nlog n)
请手写“快速排序”
算法简介
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述和实现
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现
/*方法说明：快速排序@param array 待排序数组*///方法一function quickSort(array, left, right) {console.time('1.快速排序耗时');if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {if (left < right) {var x = array[right], i = left - 1, temp;for (var j = left; j <= right; j++) {if (array[j] <= x) {i++;temp = array[i];array[i] = array[j];array[j] = temp;}}quickSort(array, left, i - 1);quickSort(array, i + 1, right);}console.timeEnd('1.快速排序耗时');return array;} else {return 'array is not an Array or left or right is not a number!';}}//方法二var quickSort2 = function(arr) {console.time('2.快速排序耗时');if (arr.length <= 1) { return arr; }var pivotIndex = Math.floor(arr.length / 2);var pivot = arr.splice(pivotIndex, 1)[0];var left = [];var right = [];for (var i = 0; i < arr.length; i++){if (arr[i] < pivot) {left.push(arr[i]);} else {right.push(arr[i]);}}console.timeEnd('2.快速排序耗时');return quickSort2(left).concat([pivot], quickSort2(right));};var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)
更多面试题请访问小程序【微信面试题宝典】，部分面试题来自互联网，如有侵权，联系删除。
END