21 历时 8 个月，10w 字！带你进大厂之算法篇。 - AnnGreen1/article GitHub Wiki

历时 8 个月，10w 字！带你进大厂之算法篇。

mp.weixin.qq.com前端从进阶到入院

前言

本系列长期更新，欢迎关注。

之前我对算法的理解，仅仅是为了应付大厂的面试。

但是在两个月的算法练习中，第一次体会到编程不仅仅是技术，还是艺术，感受到了编程是一件很酷的事情

比如简单的循环，就可以解决很复杂的数学问题；递归位置的略微变动，就会产生完全不同的结果

作者：海阔_天空

https://juejin.cn/post/7146975493278367752

算法对于前端来说重要吗？

这个问题可能在我们所处的不同的阶段里，会有完全不同的理解。我通过系统的练习后，真切的感受到了自己的编程技能在提升，逻辑思维能力有了很大不同

算法是一个优秀工程师的必备技能，对于提升编码能力有着举重若轻的作用

期待你的答案

文中给出的题目解法，可能不是最优解，希望大家多多指正，一起交流学习，在此表示感谢

一道题的解法，有很多种，对应的时间复杂度与空间复杂度也各不相同，期待你的答案，希望你可以在其中找到算法的乐趣

算法

如何学习算法

1、先掌握对应的数据结构

以面试中最常见的二叉树为例

先了解如何创建一个二叉树，通过创建的过程，加深对该数据结构的理解，非常有助于了去解答对应的题目

2、分类练习

分类练习，即按照每种数据结构进行统一练习

例如：这段时间只练习二叉树的题目，通过集中的训练，对二叉树有整体的认知。了解前、中、后序遍历的特点、了解二叉搜索树、了解各种题型等体系知识

同时做好对应的笔记，不建议一上来就直接用leetcode刷题

算法基础知识

时间复杂度

表示代码执行的次数，时间与算法中语句执行次数成正比例，哪个算法中执行语句次数多，它花费的时间就越长，时间复杂度是取代码中最复杂的代码来计算

时间复杂度按时间的大小，从小到大排序依次是- O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)

空间复杂度

在算法运算过程中用到的额外的存储空间（不包含原始值的内存大小），反映的对内存占用的趋势，而不是具体内存

最经典的场景

就是利用空间去换时间，降低时间复杂度，减少计算时间

前端数据结构

数组、栈、队列、树、堆、链表、哈希表、图

数组

数组是最简单、也是最常用的数据结构

数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的

特点：查询快，增删慢

1）查询快：数组的地址是连续的，我们通过数组的首地址可以找到数组，通过数组的索引可以快速查找某一个元素

2）增删慢：数组的长度是固定的，我们想要增加/删除一个元素，必须创建一个新的数组，把原数组的数据复制过来

最长递增子序列

先安排一个非常火的题目，方便小伙伴们热热身

该算法在vue3 diff算法中有用到，作用是找到最长递归子序列后，可以减少子元素的移动次数

一个整数数组 nums，找到其中一组最长递增子序列的值

最长递增子序列是指：子序列中的所有元素单调递增

例如：[3,5,7,1,2,8] 的 LIS 是 [3,5,7,8]

//该算法用的是动态规划的思想，时间复杂度为n2，并不是最优算法，最优算法应该是二分查找，最优时间复杂度为nlognfunctionlengthOfLIS(nums){if(!nums.length)return0;//创建一个和原数组等长的数组dp，用来存储每一项的最长递增子序列，比如[1,2,2]表示第二项和第三项的最长递增子序列都为2//该数组每一项初始值都为1，记录当前项的最长递增子序列，后面的项会在当前项的最长递增子序列个数进行累加letdp=newArray(nums.length).fill(1);//双层for循环，每一项都和之前的所有项一一进行比较，计算出该项的最长递增子序列个数，存储到dp中for(leti=0;i<nums.length;i++){//当前项依次和之前的每一项进行比较，累加出当前项的最长递增子序列for(letj=0;j<i;j++){if(nums[j]<nums[i]){//比较当前项已有的最大值和之前项最大值，比如当比较到第三项[1,2,2]时，如第三项比第二项大，所以第三项的计算结果为[1,2,3]dp[i]=Math.max(dp[i],dp[j]+1);}}}//取出一组最长递增子序列的具体值（注意：最长递增子序列有可能有多组值，这里是只取出其中一组值）//找到dp中的最大值，该值就是nums的最长递增子序列的个数letmax=Math.max(...dp);letresult=[];for(leti=max;i>=1;i--){//倒序遍历，根据长度获取对应的值findArrNode(dp,i,result,nums);}returnresult;}functionfindArrNode(dp,value,result,arr){//找到符合条件最后一项的下标，这样才能保证数组的顺序是正确的letindex=dp.lastIndexOf(value);//存储对应的值result.unshift(arr[index]);//对dp进行截取，保证只取最大项之前的数据dp.length=index+1;}//测试console.log(lengthOfLIS([9,1,7,10,4,8,5,2]));//[1,4,5]console.log(lengthOfLIS([1,4,3,5,2,6,0]));//[1,3,5,6]

亮点：网上一般都是只计算出最长递增子序列的长度，这里计算出一组具体的最长递增子序列的值

力扣上最长上升子序列的视频讲解[1]

买卖股票问题

给定一个整数数组，其中第?i?个元素代表了第?i天的股票价格；- 非负整数?fee 代表了交易股票的手续费用，求返回获得利润的最大值

例如数组为：[1, 12, 13, 9, 15, 8, 6, 16]，fee为2，求获得利润的最大值

注：每笔买卖都需要支付一次手续费

/***贪心算法求解*@param{array}list-股票每天的价格列表*@param{number}fee-手续费**/functionbuyStock(list,fee){//min为当前的最小值，即买入点letmin=list[0],sum=0;for(leti=1;i<list.length;i++){//从1开始，依次判断if(list[i]<min){//寻找数组的最小值min=list[i];}else{//计算如果当天卖出是否赚钱lettemp=list[i]-min-fee;if(temp>0){//赚钱存数据sum+=temp;//关键代码：重新计算min，分两种情况，如果后面继续涨，则默认继续持有；若后面跌，则以后面的价格重新买入min=list[i]-fee;}}}returnsum;}console.log(buyStock([1,12,13,9,15,8,6,16],2));//22

买卖股票之交易明细

继续研究买卖股票问题

通过上题，我们知道[1, 12, 13, 9, 15, 8, 6, 16]最终的结果为22

但具体的交易明细是什么，哪几天发生了交易，怎么验证22的结果是否正确呢？

思路

1）增加result对象，把每笔赚钱的交易都记录下来- 2）新增minIndex属性，用来记录每次买入值（最小值）的变化- 3）当minIndex不变时，用新的记录替换掉老的记录- 4）遍历result对象，取出所存储的交易明细

/***贪心算法求解交易明细*@param{array}list-股票每天的价格列表*@param{number}fee-手续费**/functionbuyStock(list,fee){//增加result对象，把每笔赚钱的交易都记录下来letresult={};letmin=list[0],//增加minIndex用来记录每次买入值（最小值）的变化minIndex=0,sum=0;for(leti=1;i<list.length;i++){if(list[i]<min){minIndex=i;min=list[i];}else{lettemp=list[i]-min-fee;if(temp>0){sum+=temp;min=list[i]-fee;//赚钱存数据//当minIndex不变时，用新的记录替换调老的记录result[minIndex]=[list[minIndex],list[i]];}}}letarr=[];//遍历result对象，取出所存储的交易明细Object.keys(result).forEach(key=>{arr.push(result[key]);});return{sum,arr};}console.log(buyStock([1,12,13,9,15,8,6,16],2));//打印结果：{sum: 22, arr:[1, 13], [9, 15], [6, 16](/AnnGreen1/article/wiki/1,-13],-[9,-15],-[6,-16)}

3次交易明细- 1买入，13卖出；- 9买入，15卖出；- 6买入，16卖出

22 = (13 - 1 - 2) + (15 - 9 -2) + (16 - 6 - 2)

硬币找零问题

给定不同面额的硬币，coins 和一个总金额 amount

编写一个函数来计算可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额，返回?-1

示例：输入 coins = [1, 2, 5], amount = 11

输出 3

functionfindCoins(coins,amount){if(coins.length===0)return-1;//用于保存每个目标总额对应的最小硬币个数constf=[];//提前定义已知情况f[0]=0;//遍历[1,amount]这个区间的硬币总额for(leti=1;i<=amount;i++){//求的是最小值，因此我们预设为无穷大，确保它一定会被更小的数更新f[i]=Infinity;//循环遍历每个可用硬币的面额for(letj=0;j<coins.length;j++){//若硬币面额小于目标总额，则问题成立if(i-coins[j]>=0){//状态转移方程f[i]=Math.min(f[i],f[i-coins[j]]+1);}}}//若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1if(f[amount]===Infinity){return-1;}//若有解，直接返回解的内容returnf[amount];}console.log(findCoins([1,2,5],11));//3

LeetCode 19.凑零钱问题动态规划[2]

数组拼接最小值

一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个

如[3, 45, 12]，拼接的最小值为12345

思路：利用sort排序

a和b两个数字可以有两种组合：ab和ba，若ab<ba 则ab排在ba前面

functionprintMinNumber(arr){if(!arr||arr.length==0)returnnull;//sort底层是快排returnarr.sort(compare).join("");}//找到ab和ba这两种组合的最小值functioncompare(a,b){letfront=`${a}${b}`;letafter=`${b}${a}`;returnfront-after;}letarr=[3,45,12];console.log(printMinNumber(arr));//12345

奇偶排序

一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分

思路: 设定两个指针

1）第一个指针start，从数组第一个元素出发，向尾部前进- 2）第二个指针end，从数组的最后一个元素出发，向头部前进- 3）start遍历到偶数，end遍历到奇数时，交换两个数的位置- 4）当start>end时，完成交换

functionexchangeOddEven(arr){letstart=0;letend=arr.length-1;//当start>end时，完成交换while(start<end){//找到第一个偶数while(arr[start]%2===1){start++;}//找到第一个奇数while(arr[end]%2===0){end--;}//重点：始终要加上 start < end的限制，否则会出现中间两个数的位置交换错误if(start<end){//奇数和偶数交换位置[arr[start],arr[end]]=[arr[end],arr[start]];}}returnarr;}lettest=[2,4,5,3,1];console.log(exchangeOddEven(test));//[1,3,5,4,2]

两数之和

给定一个整数数组 nums 和一个目标值 target- 在该数组中找出和为目标值的两个整数，并返回他们

要求时间复杂度：O(n)

思路：利用map存储已遍历的元素 (典型的空间换时间)

//时间复杂度O(n)、空间复杂度O(n)functiontwoNumAdd(arr,target){if(Array.isArray(arr)){//使用map将遍历过的数字存起来letmap={};for(leti=0;i<arr.length;i++){//从map中查找是否有key等于target-nums[i]，如果取到了，则条件成立，返回结果if(map[target-arr[i]]!==undefined){return[target-arr[i],arr[i]];}else{//条件不成立，则将已遍历的值存起来map[arr[i]]=i;}}}return[];}console.log(twoNumAdd([8,2,6,5,4,1,3],7));//[2,5]

三数之和

给定一个数组nums，判断 nums 中是否存在三个元素a，b，c ，使得 a + b + c = target

找出所有满足条件且不重复的三元组合

思路：

将数组排序，然后固定数组中某一项，用双端指针的方式，查到两数之和加上该项的值等于目标值，将三数之和转化为两数之和

题目中说明可能会出现多组结果，所以我们要考虑好去重

1）为了方便去重，我们首先将数组从小到大排列

2）对数组进行遍历，取当前遍历的数nums[i]为一个基准数

3）在寻找数组中设定两个起点，最左侧的left(i+1)和最右侧的right(length-1)

4）判断nums[i] + nums[left] + nums[right]是否等于目标值target

5）如果相等，存储该结果，并分别将left和right各移动一位

6）如果大于目标值，将right向左移动一位，向结果逼近

7）如果小于目标值，将left向右移动一位，向结果逼近

8）一轮遍历结束后i++，进入下一轮查询

functionfindThree(arr,target){arr.sort();letresult=[];for(leti=0;i<arr.length;i++){//跳过重复的arr[i]值,比如[2,1,1],跳过第二个1if(i&&arr[i]===arr[i-1])continue;letleft=i+1;letright=arr.length-1;while(left<right){letsum=arr[i]+arr[left]+arr[right];if(sum>target){right--;}elseif(sum<target){left++;}else{// arr[left++], 先取arr[left]，然后left++, 两步合成一步；arr[right--]同样的逻辑result.push([arr[i],arr[left++],arr[right--]]);while(arr[left]===arr[left-1]){//跳过重复的arr[left]值,left++;}while(arr[right]===arr[right+1]){//跳过重复的arr[right]值right--;}}}}returnresult;}console.log(findThree([5,2,1,1,3,4,6],8));//[1,1,6][1,2,5][1,3,4]

四数之和

给定一个整数数组nums，判断 nums 中是否存在四个元素a，b，c，d ，使得 a + b + c + d = target，找出所有满足条件且不重复的四元组合

思路

到这里其实我们就能发现一些规律，可以像三数之和那样，通过大小指针来逼近结果，从而达到降低一层时间复杂度的效果（重点：将4个数相加，转化为三个数，降低层级）

不管是几数之和，都可以用这种方法来进行降级优化

functionfindFour(arr,target){if(arr.length<4)return[];letresult=[];arr.sort();//最外层控制循环次数，循环次数为arr.length-3for(leti=0;i<arr.length-3;i++){//跳过数组中，重复的起始值if(i&&arr[i]===arr[i-1])continue;//因为数组已进行排序，所有一旦超过目标值，那么以后的值也都比目标值大，所以可以直接结束这一轮循环if(arr[i]+arr[i+1]+arr[i+2]+arr[i+3]>target)break;for(letj=i+1;j<arr.length-2;j++){//注意范围，第二个值的最小值是倒数第3位（以下的代码和三个数求和的逻辑一致）//跳过数组中，第二个值重复的if(j>i+1&&arr[j]===arr[j-1])continue;//第三个数的下标letleft=j+1;letright=arr.length-1;while(left<right){letsum=arr[i]+arr[j]+arr[left]+arr[right];if(sum>target){right--;}elseif(sum<target){left++;}else{//坑点，注意添加后，left++，right--,确保循环继续执行result.push([arr[i],arr[j],arr[left++],arr[right--]]);while(arr[left]===arr[left-1]){//跳过重复的值left++;}while(arr[right]===arr[right+1]){//跳过重复的值right--;}}}}}returnresult;}console.log(findFour([2,1,5,4,3,6,0,7],10));//[0,1,2,7][0,1,3,6][0,1,4,5][0,2,3,5][1,2,3,4]

连续整数之和

输入一个正整数S，打印出所有和为S的连续整数序列

例如：输入15，连续整数序列有：1+2+3+4+5 = 4+5+6 = 7+8 = 15，所以打印出3个连续序列1-5，5-6和7-8

思路:

1）创建一个容器child，用于表示当前的子序列，初始元素为1,2

2）记录子序列的开头元素small和末尾元素big

3）big向右移动子序列末尾增加一个数；small向右移动子序列开头减少一个数

4）当子序列的和大于目标值，small向右移动，子序列的和小于目标值，big向右移动

functionFindContinuousSequence(sum){letresult=[];//记录当前的结果letchild=[1,2];letsmall=1;//初始值1letbig=2;//letcurrentSum=3;//当前数字之和while(big<sum){//big等于sum时，child中只剩一个数，不满足连续正数序列的要求，结束循环while(currentSum<sum&&big<sum){child.push(++big);//currentSum为当前child的和currentSum+=big;}while(currentSum>sum&&small<big){child.shift();//因为删除了最小值，所以small也要响应变化，增加1currentSum-=small++;}if(currentSum===sum&&child.length>1){//child.length大于1，剔除一个数等于sum的情况//child.slice返回一个新的数组result.push(child.slice());child.push(++big);currentSum+=big;}}returnresult;}console.log(FindContinuousSequence(15));//[1,2,3,4,5][4,5,6][7,8]

打印矩阵

输入:- [[ 1, 2, 3 ],- [ 4, 5, 6 ],- [ 7, 8, 9 ]]

要求输出: [1,2,3,6,9,8,7,4,5]

题目要求的是按照顺时针的顺序，从外向内遍历每一个元素，并将他们按顺序返回出来

functionprintMatrix(arr){//map函数用来完成当前矩阵最外一圈的遍历//@param1{Array}二维数组arr表示当前矩阵//@param2{Array}一维数组result用来保存遍历结果letmap=(arr,result)=>{//矩阵的高度即行数letn=arr.length;//遍历矩阵的每一行for(leti=0;i<n;i++){//若第一行按顺序插入if(i===0){result=result.concat(arr[i]);}elseif(i===n-1){//若最后一行倒序插入result=result.concat(arr[i].reverse());}else{//若中间行插入该行最后一个元素并将该元素从矩阵中删除result.push(arr[i].pop());}}//将已经遍历的第一行和最后一行从矩阵中删除arr.pop();arr.shift();//遍历插入最左侧一列此时删除首位两行后矩阵高度已变为n-2for(letj=n-3;j>=0;j--){//避免arr[j]长度为空时插入undefinedif(arr[j].length){result.push(arr[j].shift());}}//截止条件矩阵有元素就继续递归if(arr.length){//把已将遍历元素删除的矩阵进行递归returnmap(arr,result);}else{returnresult;}};//将初始矩阵传入,保存结果的数组初始为空returnmap(arr,[]);}letmatrix=[1,2,3],[4,5,6],[7,8,9](/AnnGreen1/article/wiki/1,2,3],[4,5,6],[7,8,9);console.log(printMatrix(matrix));//[1,2,3,6,9,8,7,4,5]

斐波那契数列

从第3项开始，当前项等于前两项之和：1 1 2 3 5 8 13 21⋯⋯

使用动态规划，将复杂的问题拆分，也就是：F(N) = F(N - 1) + F(N - 2)，然后用数组将已经计算过的值存起来

functionfib(n){//使用dp数组，将之前计算的结果存起来，防止栈溢出letdp=[];dp[0]=1n;//bigint可以用来表示超过2^53-1的大整数dp[1]=1n;for(leti=2;i<=n;i++){ dp[i]= dp[i - 1]+ dp[i - 2];//注意：arr[i]}returndp[n];}console.log(fib(1000));

二叉树

二叉树是树结构中一种典型的结构，每个节点最多只能有两个子节点，一个是左侧子节点，一个是右侧子节点

二叉树图例

二叉树遍历的规律

前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历- 中序遍历：左子树中序遍历 + 根节点 + 右子数中序遍历- 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点

创建一棵二叉树

要求：若新节点的值比父节点小，则放到父节点的左子树上；反之放到右子树上

//二叉树节点classNode{constructor(data,left=null,right=null){this.data=data;this.left=left;this.right=right;}}//构建二叉树classTree{constructor(){this.root=null;}insert(data){varnode=newNode(data,null,null);//创建根节点if(!this.root){this.root=node;return;}varcurrent=this.root;varparent=null;while(current){parent=current;//值比父节点小，放到父节点的左子树上if(data<parent.data){current=current.left;//找到最左侧的节点，将新的节点设置为该节点的左子树节点if(!current){parent.left=node;return;}}else{//值比父节点大，放到父节点的右子树上current=current.right;if(!current){parent.right=node;return;}}}}//定义前序遍历的方法staticpreOrder(node,arr=[]){if(node){arr.push(node.data);this.preOrder(node.left,arr);this.preOrder(node.right,arr);}returnarr;}//定义中序遍历的方法staticmiddleOrder(node,arr=[]){if(node){this.middleOrder(node.left,arr);arr.push(node.data);this.middleOrder(node.right,arr);}returnarr;}//定义后序遍历的方法staticlaterOrder(node,arr=[]){if(node){this.laterOrder(node.left,arr);this.laterOrder(node.right,arr);arr.push(node.data);}returnarr;}//获取二叉树的最大层级staticgetDeep(node,deep=0){if(!node){returndeep;}deep++;//获取左子树的层级letleft=this.getDeep(node.left,deep);//获取右子树的层级letright=this.getDeep(node.right,deep);//取层级最大的值returnMath.max(left,right);}}//创建二叉树，依次插入新节点vart=newTree();t.insert(5);t.insert(3);t.insert(6);t.insert(2);t.insert(4);t.insert(7);t.insert(8);t.insert(1);t.insert(9);//打印二叉树console.log(t);//前序遍历?[5,3,2,1,4,6,7,8,9]console.log(Tree.preOrder(t.root));//中序遍历[1,2,3,4,5,6,7,8,9]console.log(Tree.middleOrder(t.root));//后序遍历[1,2,4,3,9,8,7,6,5]console.log(Tree.laterOrder(t.root));//获取二叉树的最大层级：5console.log(Tree.getDeep(t.root));

构建结果

非递归版本实现中序遍历

中序遍历的两种方式

1）方式一：递归版本，如上文的middleOrder方法

2）方式二：非递归版本（回溯算法）实现中序遍历

非递归版本的好处：避免循环递归时栈溢出的情况，效率更高

非递归版本流程

1）步骤1 ：左孩子入栈 -> 直至左孩子为空的节点- 2）步骤2 ：节点出栈 -> 访问该节点- 3）步骤3 ：以右子树为目标节点，再依次执行步骤1、2、3

functionmiddleTraverse(root){constresult=[];//stack用来存储回溯算法中的节点conststack=[];letcurrent=root;while(current||stack.length>0){//找到最左侧的节点while(current){//依次将左子树节点存到栈中stack.push(current);current=current.left;}//节点出栈current=stack.pop();//存储该节点的值result.push(current.data);//获取该节点的右子树节点current=current.right;}returnresult;}//t为上文创建的二叉树console.log(middleTraverse(t.root));//打印结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，重建出该二叉树

原理

前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历- 中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历

重建二叉树流程

1）前序遍历第一个值为根结点root，然后找到根节点在中序遍历的下标

2）将中序遍历拆分为左子树中序遍历和右子树中序遍历

3）将前序遍历拆分为左子树前序遍历和右子树前序遍历

4）利用左子树中序遍历 + 左子树前序遍历，递归创建左子树节点

5）利用右子树中序遍历 + 右子树前序遍历，递归创建右子树节点

6）递归重建二叉树

//重建二叉树functionreConstruction(pre,mid){if(pre.length===0){returnnull;}//前序遍历长度为1时，该节点为叶子节点if(pre.length===1){returnnewNode(pre[0]);}//前序遍历的第一个值为根节点constvalue=pre[0];//找到根节点在中序遍历的位置constindex=mid.indexOf(value);//将中序遍历分为左子树中序遍历和右子数中序遍历constmidLeft=mid.slice(0,index);constmidRight=mid.slice(index+1);//左子树前序遍历的长度为index//将前序遍历分为左子树前序遍历和右子树前序遍历constpreLeft=pre.slice(1,index+1);constpreRight=pre.slice(index+1);//创建根节点constnode=newNode(value);//利用左子树中序遍历+左子树前序遍历，递归创建左子树节点node.left=reConstruction(preLeft,midLeft);//递归创建右子树节点node.right=reConstruction(preRight,midRight);returnnode;}classNode{constructor(data,left=null,right=null){this.data=data;this.left=left;this.right=right;}}reConstruction([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]);

重建结果

二叉树在线构建工具[3]

二叉查找树

二叉查找树（BST）是二叉树的一种，特点是所有的左节点比父节点的值小，所有的右节点比父节点的值大，并且任意左、右子树也分别为二叉查找树

二叉查找树图例

主要作用是搜索和动态排序

二叉查找树搜索某个节点

//查找一个节点functionfindNode(data,node){if(node){if(data===node.data){returnnode;}elseif(data<node.data){returnthis.findNode(data,node.left);}else{returnthis.findNode(data,node.right);}}else{returnnull;}}//查找值为6的节点//t为上文创建的二叉树console.log(findNode(6,t.root));

二叉查找树的最大值和最小值

最右侧的节点为二叉查找树的最大值- 最左侧的节点为二叉查找树的最小值

//最大值：最右侧的节点functiongetMax(root){letmax=null;letcurrent=root;while(current!==null){max=current.data;current=current.right;}returnmax;}//最小值：最左侧的节点functiongetMix(root){letmix=null;letcurrent=root;while(current!==null){mix=current.data;current=current.left;}returnmix;}console.log(getMax(t.root),"max");//9console.log(getMix(t.root),"min");//1

二叉查找树的前序遍历

给一个整数数组，判断该数组是不是某二叉查找树的前序遍历的结果- 如果是输出true，否则输出false

//判断一个整数数组，是否为某二叉查找树的前序遍历的结果functionpreOrderOfBST(list){if(list&&list.length>0){//前序遍历，第一个值为根节点varroot=list[0];//找到数组中，第一个比根节点大的节点，即为右子树的节点for(vari=0;i<list.length;i++){if(list[i]>root){break;}}//遍历右子树的节点，要求所有右子树的节点都比根节点大for(letj=i;j<list.length;j++){if(list[j]<root){returnfalse;}}varleft=true;//同理，递归判断左子树是否符合二叉搜索树的规则if(i>1){left=preOrderOfBST(list.slice(1,i+1));}varright=true;//递归判断右子树是否符合二叉搜索树的规则if(i<list.length){right=preOrderOfBST(list.slice(i,list.length));}//左、右子树都符合要求，则是一个二叉搜索树returnleft&&right;}}console.log(preOrderOfBST([5,3,2,1,4,6,7,8,9]));//true

二叉查找树的后续遍历

给一个整数数组，判断该数组是不是某二叉搜索树的后续遍历的结果- 如果是则输出true,否则输出false

//判断一个整数数组，是否为某二叉搜索树的后序遍历的结果functionlaterOrderOfBST(list){if(list&&list.length>0){//后续遍历，最后一个节点为根节点varroot=list[list.length-1];for(vari=0;i<list.length-1;i++){if(list[i]>root){break;}}for(letj=i;j<list.length-1;j++){if(list[j]<root){returnfalse;}}varleft=true;//判断左子树if(i>0){left=laterOrderOfBST(list.slice(0,i));}varright=true;//判断右子树if(i<list.length-1){right=laterOrderOfBST(list.slice(i,list.length-1));}returnleft&&right;}}console.log(laterOrderOfBST([1,2,4,3,9,8,7,6,5]));//true

找到二叉树和为某一值的路径

利用回溯算法：如果不符合要求，退回来，换一条路再试

找到和为11的所有路径：结果为[5, 3, 2, 1], [5, 6]

二叉树结构如下

/***找到和为某一值的路径*@param{object}node-二叉树*@param{number}num-和（目标值）*@param{array}stack-栈*@param{number}sum-当前路径的和*@param{array}result-存储所有的结果**/functionfindPath(node,num,stack=[],sum=0,result=[]){stack.push(node.data);sum+=node.data;//找到所有的节点路径(包含叶子节点和子节点的所有情况之和)if(sum===num){//if(!node.left&&!node.right&&sum===num){//找到所有的叶子节点路径result.push(stack.slice());}if(node.left){findPath(node.left,num,stack,sum,result);}if(node.right){findPath(node.right,num,stack,sum,result);}//回溯算法：不符合要求，退回来，换一条路再试//叶子节点直接pop；子节点中的所有的节点递归完成后再popstack.pop();returnresult;}//t为上文创建的二叉树console.log(findPath(t.root,11));//[5,3,2,1],[5,6]

堆

堆实际上是一棵完全二叉树

大顶堆：每个的节点元素值不小于其子节点

小顶堆：每个的节点元素值不大于其子节点

堆的作用

在庞大的数据中，找到最大的m个数或者最小的m个数，可以借助堆来完成这个过程，时间复杂度为nlogm

如果先排序，再取前m个数，最小时间复杂度nlogn

nlogm < nlogn，堆排序时间复杂度更优

堆节点与其叶子节点的规律

1）堆中父节点为k，它的左子节点下标为2k+1，右子节点是2k+2

2）所有序号大于length/2的结点都是叶子节点, 0 到 length/2-1 为父节点

堆的排序过程

堆排序

从一堆数中，找到前m个最小值

如图，从下面的大顶堆中，找到前4个最小值，结果为[6, 5, 2, 1]

functionheapSort(list,m){if(m>list.length){return[];}createHeap(list,m);for(leti=m;i<list.length;i++){if(list[i]<list[0]){//找到前m个数的最小值，依次将最小值放到最前面[list[i],list[0]]=[list[0],list[i]];ajustHeap(list,0,m);}}//取出前m个数returnlist.splice(0,m);}//构建大顶堆（构建的顺序是从下往上，先找到最后一个父节点，然后从最后一个父节点开始构建，然后依次往上构建，将最大值逐步替换成根节点）functioncreateHeap(arr,length){//找到堆中所有的非叶子节点（找到最后一个叶子节点，该节点之前都是非叶子节点）for(leti=Math.floor(length/2)-1;i>=0;i--){//堆中，父节点为i，则子节点为2*i+1、2*i+2；反过来，知道了子节点为length,则最后一个子节点为Math.floor(length / 2)- 1。ajustHeap(arr,i,length);//调整大顶堆，将最大值逐步替换成根节点}}//调整大顶堆（注意：调整的顺序是从上往下，将根节点替换后，先调整根节点，然后依次往下调整，对应的子节点如果发生替换，要重新调整下对应子节点，保证都满足子节点不大于父节点的条件，直到该大顶推全部调整完成）//比如，当调节根节点时，[a0,a1,a2],a2>a0,a2替换a0，则要重新调节a2这个分支上的节点，保证都满足子节点不大于父节点的条件functionajustHeap(arr,index,length){for(leti=2*index+1;i<length;i=2*i+1){//父节点为i，则子节点为2*i+1if(i+1<length&&arr[i+1]>arr[i]){//找到arr[i+1]和arr[i]中的最大值i++;}//如果子节点比父节点大，交换两者的位置，将最大值移动到顶部if(arr[index]<arr[i]){[arr[index],arr[i]]=[arr[i],arr[index]];index=i;}else{break;}}}console.log(heapSort([5,10,2,15,1,12,6],4));//[6,5,2,1]

树

JS中树结构一般类似这样

lettree=[{id:"1",title:"节点1",children:[{id:"1-1",title:"节点1-1"},{id:"1-2",title:"节点1-2"}]},{id:"2",title:"节点2",children:[{id:"2-1",title:"节点2-1"}]}];

列表转树

使用对象存储数据, 典型的空间换时间

时间复杂度为O(n)、空间复杂度为O(n)

functionlistToTree(data){//使用对象重新存储数据,空间换时间letmap={};//存储最后结果lettreeData=[];//遍历原始数据data，存到map中，id为key，值为数据for(leti=0;i<data.length;i++){map[data[i].id]=data[i];}//遍历对象for(letiinmap){//根据parentId找到的是父节点if(map[i].parentId){if(!map[map[i].parentId].children){map[map[i].parentId].children=[];}//将子节点放到父节点的children中map[map[i].parentId].children.push(map[i]);}else{//parentId找不到对应值，说明是根结点，直接插到根数组中treeData.push(map[i]);}}returntreeData;}//测试letlist=[{id:1,title:"child1",parentId:0},{id:2,title:"child2",parentId:0},{id:6,title:"child2_1",parentId:2},{id:4,title:"child1_1",parentId:1},{id:5,title:"child1_2",parentId:1},{id:3,title:"child3",parentId:0},{id:7,title:"child3_1",parentId:3}];console.log(listToTree(list));

深度优先遍历

递归实现，写法简单，时间复杂度为O(n2)

functiondeepTree(tree,arr=[]){tree.forEach(data=>{arr.push(data.id);//遍历子树data.children&&deepTree(data.children,arr);});returnarr;}lettree=[{id:"1",title:"节点1",children:[{id:"1-1",title:"节点1-1"},{id:"1-2",title:"节点1-2"}]},{id:"2",title:"节点2",children:[{id:"2-1",title:"节点2-1"}]}];console.log(deepTree(tree));//['1','1-1','1-2','2','2-1']

广度优先遍历

思路

1）维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤，直到队列为空

2）取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后

时间复杂度为O(n)、空间复杂度为O(n)

//广度优先functionrangeTree(tree,arr=[]){letnode,list=[...tree];while((node=list.shift())){arr.push(node);node.children&&list.push(...node.children);}returnarr;}lettree=[{id:"1",title:"节点1",children:[{id:"1-1",title:"节点1-1"},{id:"1-2",title:"节点1-2"}]},{id:"2",title:"节点2",children:[{id:"2-1",title:"节点2-1"}]}];console.log(rangeTree(tree));//?['1','2','1-1','1-2','2-1']

查找节点

递归实现，写法简单

functionfindTreeNode(tree,func){for(constdataoftree){//条件成立直接返回if(func(data))returndata;if(data.children){constres=findTreeNode(data.children,func);//结果存在再返回if(res)returnres;}}returnnull;}lettree=[{id:"1",title:"节点1",children:[{id:"1-1",title:"节点1-1"},{id:"1-2",title:"节点1-2"}]},{id:"2",title:"节点2",children:[{id:"2-1",title:"节点2-1"}]}];console.log(findTreeNode(tree,data=>{returndata.title==="节点1-1";}));//打印结果：{id:'1-1',title:'节点1-1'}

字符串

版本号排序

比较 a, b 两个版本大小：a为1.rc.2.1，b为1.beta.2

其中 rc > beta > alpha- 例子 1.2.3 < 1.2.4 < 1.3.0.alpha.1 < 1.3.0.alpha.2 < 1.3.0.beta.1 < 1.3.0.rc.1 < 1.3.0

要求：当 a > b 是返回 1；当 a = b 是返回 0；当 a < b 是返回 -1；

思路

1）首先先写一个映射表，建立不同版本的映射关系

2）将不同版本的英文字母，替换成对应的数字，转化为对字符串进行比较

3）字符串比较的原则：取出相同位置的数字进行递归比较

functioncompareVersion(str1,str2){//创建rcbetaalpha，对应的权重值，将版本号转化为纯数字letmap={rc:3,beta:2,alpha:1};Object.keys(map).forEach(key=>{str1=str1.replace(key,map[key]);str2=str2.replace(key,map[key]);});constarr1=str1.split(".");constarr2=str2.split(".");functionfn(arr1,arr2){leti=0;while(true){//取出相同位置的数字consts1=arr1[i];consts2=arr2[i];i++;//若s1或s2不存在，说明相同的位置已比较完成，剩余的位置比较arr1与arr2的长度，长的版本号大if(s1===undefined||s2===undefined){returnarr1.length-arr2.length;}if(s1===s2)continue;//比较相同位置的数字大小returns1-s2;}}returnfn(arr1,arr2);}//测试letstr1="1.rc.2.1";letstr2="1.beta.2";console.log(compareVersion(str1,str2));//1

第一个不重复字符的下标

输入一个字符串，找到第一个不重复字符的下标

如输入abcabcde，输出6，第一个不重复的字符为d

//方法一：//先使用Set去重//然后两层遍历，时间复杂度为O(n2)functionfindAlone(str){letarr=str.split("");//通过set去重letaloneArr=[...newSet(arr)];letval="";for(leti=0;i<=aloneArr.length-1;i++){//用原始字符串进行遍历找到唯一的值if(arr.filter(item=>item==aloneArr[i]).length==1){val=aloneArr[i];break;}}returnval?arr.indexOf(val):-1;}letstr="abcabcde";console.log(findAlone(str));//6//方法二：//思路:使用map存储每个字符出现的次数//该方法时间复杂度和空间复杂度均为O(n),从时间上来说，要比第一种方法快functionfindAlone1(str){if(!str)return-1;//使用map存储每个字符出现的次数letmap={};letarr=str.split("");arr.forEach(item=>{letval=map[item];// val为undefined时，表示未存储，map[item]= 1；否则map[item]= val + 1map[item]=val?val+1:1;});//一次遍历结果后，再遍历一遍找到出现1次的值for(leti=0;i<arr.length;i++){if(map[arr[i]]==1){returni;}}return-1;}console.log(findAlone1(str));//6

字符串所有排列组合

输入一个字符串，打印出该字符串中字符的所有排列组合

例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串，结果为：['abc', 'acb', 'bca', 'bac', 'cab', 'cba']

思路：

1）利用回溯法（将删除的元素递归后，重新添加到数据中）

2）每次递归，固定开头的字母，比如abc，先固定a，然后交换bc的位置，拿到两个结果 abc acb

3）然后交换字符串位置，比如abc递归一轮后，位置变化为 bca

4）第二轮，固定b，然后交换ca的位置，拿到两个结果 bca bac

5）同理，依次将字符串中的字符放到头部，并固定，拿到所有情况的结果

/***计算所有字符串的组合*@param{array}list-字符串列表*@param{array}result-最终的结果*@param{string}current-当前的字符串*@param{string}temp-当前固定的字符**/functionstringGroup(list=[],result=[],current="",temp=""){current+=temp;if(list.length===0){//递归的出口，将对应结果添加到list中returnresult.push(current);}for(leti=0;i<list.length;i++){//每次递归固定第一个字符temp=list.shift();stringGroup(list,result,current,temp);//将删除的temp重新添加到queue尾部，实现将数组反转的效果，如[a,b,c]反转为[c,b,a]list.push(temp);}//这里去重是解决str中有重复的字母，比如str为'aacd'return[...newSet(result)];}console.log(stringGroup("abc".split("")));//['abc','acb','bca','bac','cab','cba']

字符串是否对称

输入一个字符串，判断是否对称，对称输出ture，不对称输出false

输入 abcba; 输出 true

//方法一：将字符串切分为数组，再逆序，再连接为字符串functionisReserveSame(str){lettemp=str.split("").reverse().join("");returntemp===str;}console.log(isReserveSame("abcba"));//true//方法二：循环遍历，判断对称位置的字符是否相等functionisReserveSame1(s){letflag=true;for(leti=0;i<parseInt(s.length/2);i++){if(s.charAt(i)!==s.charAt(s.length-1-i)){flag=false;}}returnflag;}console.log(isReserveSame1("abcba"));//true

链表

链表：用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和next(下一个元素)的地址

链表是物理存储单元上非连续的、非顺序的存储结构

链表特点：查询慢，增删快

1）查询慢：链表地址不是连续的，每次查询都要从头开始

2）增删快：增加/删除一个元素，对链表的整体结构没有影响，所以增删快

链表在开发中也是会用到的数据结构，比如React的?Fiber和hook底层都用到了链表

链表图例

创建链表

//链表Node节点functionNode(data){this.data=data;this.next=null;}//创建链表classLinkedList{constructor(){this.count=0;//链表长度this.head=null;//链表开头}//添加节点push(data){letnode=newNode(data);if(!this.head){this.head=node;}else{letcurrent=this.head;while(current.next){current=current.next;}current.next=node;}this.count++;}//插入节点insert(data,index){if(index>=0&&index<=this.count){letnode=newNode(data);letcurrent=this.head;if(index==0){//插到表头this.head=node;node.next=current;}else{for(leti=0;i<index-1;i++){//找到要插入位置的前一个元素current=current.next;}letnext=current.next;//暂存next以后的节点信息current.next=node;node.next=next;}this.count++;//返回插入成功的结果returntrue;}else{returnfalse;}}//按索引值查找getIndexNode(index){if(index>=0&&index<this.count){letcurrent=this.head;for(leti=0;i<index;i++){current=current.next;}returncurrent;}else{returnnull;}}//按索引值删除节点removeNode(index){if(index>=0&&index<this.count){if(index==0){this.head=this.head.next;}else{letcurrent=this.head;constpre=this.getIndexNode(index-1);//找到要删除元素的前一个元素current=pre.next;//获取要删除的元素pre.next=current.next;}this.count--;returntrue;}else{returnfalse;}}//查找节点的位置indexOf(data){letcurrent=this.head;for(leti=0;i<this.count;i++){if(data===current.data){returni;}current=current.next;}}//链表转字符串toString(){letcurrent=this.head;letstring=`${current.data}`;//current长度大于1，取下一个节点if(this.count>1)current=current.next;for(leti=1;i<this.count;i++){string=`${string},${current.data}`;current=current.next;}returnstring;}}//测试constlink=newLinkedList();//增加5个节点for(leti=1;i<=5;i++){link.push(i);}//索引为1的位置插入节点6link.insert(6,1);//获取索引2的节点console.log(link.getIndexNode(2));//删除索引3的节点console.log(link.removeNode(3));//查找位为6的索引console.log(link.indexOf(6));//链表转字符串1,6,2,4,5console.log(link.toString());

环形链表

链表其中一个节点的next指针，指向另一个节点

创建如上图所示的链表，节点5指向节点3

constlink=newLinkedList();//增加5个节点for(leti=1;i<=5;i++){link.push(i);}//创建环形链表，找到值为5的节点，将该节点的next指向值为3的节点link.getIndexNode(4).next=link.getIndexNode(2);

查找环形链表的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null

思路

声明两个指针 P1 P2

1）判断链表是否有环：P1 P2 从头部出发，P1一次走两步，P2一次走一步，如果可以相遇，则环存在

2）从环内某个节点开始计数，再回到此节点时得到链表环的长度 length

3）P1、P2 回到head节点，让 P1 先走 length 步，当P2和P1相遇时即为链表环的节点

//查找环形链表节点functionEntryNodeOfLoop(head){if(!head||!head.next){returnnull;}letp1=head.next;//p2一次走两步letp2=head.next.next;//若p1===p2则证明该链表有环while(p1!==p2){if(p1==null||p2.next===null){returnnull;}p1=p1.next;p2=p2.next.next;}//此时p1是p1、p2重合的点lettemp=p1;letlength=1;p1=p1.next;//获取环的长度while(p1!==temp){p1=p1.next;length++;}//找公共节点//此时为什么要将p1p2重新赋值，因为p2只是重合的点，不一定是入口节点p1=p2=head;while(length-->0){p2=p2.next;}while(p1!==p2){p1=p1.next;p2=p2.next;}returnp1;}constlink=newLinkedList();//增加5个节点for(leti=1;i<=5;i++){link.push(i);}//创建环形链表，值为5的节点，next指向值为3的节点link.getIndexNode(4).next=link.getIndexNode(2);console.log(EntryNodeOfLoop(link.head));//打印节点3

环中最后的数字

0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，求出这个圆圈里剩下的最后一个数字

约瑟夫环问题

//使用链表形成一个闭环，最后一个元素的指针指向第一个元素functionfindLastNode(n,m){if(n<1||m<1)return-1;consthead={val:0};letcurrent=head;for(leti=1;i<n;i++){//生成一个链表current.next={val:i};//将next下一项赋值给currentcurrent=current.next;}//尾部指向头部，形成闭环current.next=head;while(current.next!=current){//此时current是最后一个节点for(leti=0;i<m-1;i++){//找到要删除节点的前一个节点（范围是m-1,这里是从最后一个节点开始；如果是从head开始，范围则是m-2）current=current.next;}//删除第m个节点current.next=current.next.next;}returncurrent.val;}console.log(findLastNode(5,3));//3

栈和队列

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作

栈的特点是：先进后出，从栈顶放入元素的操作叫入栈，取出元素叫出栈

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出，从一端放入元素的操作称为入队，取出元素为出队

两者区别：栈（先进后出）、队列（先进先出）

创建栈和队列

创建栈

//创建栈只能从栈尾添加和删除实现先进后出的效果classStack{constructor(){this.arr=[];}//从栈尾添加insert(data){this.arr.push(data);}//从栈尾删除del(){returnthis.arr.pop();}toString(){returnthis.arr.toString();}}letstack=newStack();stack.insert(1);stack.insert(2);stack.insert(3);stack.del();console.log(stack.toString());//1,2

创建队列

//创建队列只能从栈尾添加和头部删除实现先进先出的效果classQueue{constructor(){this.arr=[];}insert(data){this.arr.push(data);}del(){returnthis.arr.shift();}toString(){returnthis.arr.toString();}}letqueue=newQueue();queue.insert(1);queue.insert(2);queue.insert(3);queue.del();console.log(queue.toString());//2,3

栈的入栈和出栈序列

输入两个整数序列，第一个序列arr1表示栈的入栈顺序，请判断第二个序列arr2，是否可能为该栈的出栈序列

思路

1）创建一个栈，模拟入栈、出栈的过程

2）id用来记录arr1已出栈的位置

3）当stack栈顶元素和 arr2 栈顶元素相同时，stack出栈；索引id+1

4）最终stack栈为空，表示arr1全部元素已出栈

//判断两个整数序列，第一个序列为入栈顺序，第二个序列是否为出栈顺序functionisSameStack(arr,arr1){//创建一个栈，模拟入栈、出栈的过程letstack=[];//id用来记录arr1已出栈的位置letid=0;for(leti=0;i<arr.length;i++){//入栈stack.push(arr[i]);//当stack栈顶元素和 arr1 栈顶元素相同时，stack出栈；索引id+1，while(stack.length&&stack[stack.length-1]===arr1[id]){//出栈stack.pop();//下次要对比arr1[id+1]与stack栈顶元素是否相等id++;}}//最终stack栈为空，表示arr全部元素已出栈returnstack.length==0;}console.log(isSameStack([1,2,3,4,5],[2,4,5,3,1]));//true

滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口，从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口中的k个数字。滑动窗口每次只向右移动一位，求返回滑动窗口最大值

如nums = [1,3,-1,-3,5,3,6,7]， k = 3，输出结果为[3, 3, 5, 5, 6, 7]

思路

利用双端队列（队列两侧都可以剔除元素），窗口移动的过程中，始终保证window中最左侧的元素为当前窗口的最大值

functionmaxSlidingWindow(nums,k){//window存储当前窗口中数据的下标constwindow=[];//result存储窗口中的最大值constresult=[];for(leti=0;i<nums.length;i++){if(i-window[0]>k-1){//窗口不断往右移动，当最大值在窗口最左侧，但窗口的长度超出k时的情况，就要把左侧的最大值剔除，比如窗口为【3,-1,-3】，继续往右时，就要把左侧的3剔除window.shift();//剔除窗口长度超出范围时左侧的最大值}for(letj=window.length-1;j>=0;j--){//当前窗口的值依次和要插入的值做比较，如果小于要插入的值，剔除掉该值，直到window为空为止（保证window中最左侧的值为最大值）if(nums[window[j]]<=nums[i]){window.pop();}}//添加右侧新加入的值，插入新值时有两种情况：// 1、新值为最大值时，则window此时为空；// 2、新值不为最大值时，window已剔除掉比新值小的值。//始终保证window中最左侧的值为最大值window.push(i);if(i>=k-1){//窗口是从0开始移动，当移动的距离，大于等于目标范围后，以后再往后移动一次，就要写入当前窗口的最大值result.push(nums[window[0]]);}}returnresult;}console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7],3));//[3,3,5,5,6,7]

排序算法

各种排序算法的对比详情

算法的稳定性：序列相同元素排序后，先后次序不变即稳定

冒泡排序、归并排序稳定，快速排序、选择排序不稳定

冒泡排序

时间复杂度为O(n2)，稳定

functionbubbleSort(arr){constlength=arr.length;//外层循环用控制排序进行多少轮for(leti=0;i<length;i++){//内层循环用于每一轮的数据比较//注意j的长度范围length-i-1for(letj=0;j<length-i-1;j++){//相邻元素，大的放到后面if(arr[j]>arr[j+1]){//交换位置[arr[j],arr[j+1]]=[arr[j+1],arr[j]];}}}returnarr;}console.log(bubbleSort([8,7,1,4,3]));//[1,3,4,7,8]

选择排序

时间复杂度为O(n2)，不稳定

思路

从未排序序列中找到最小的元素，放到已排序序列的头部，重复上述步骤，直到所有元素排序完毕

1）外层循环控制进行多少轮- 2）内层循环进行数据比较，找到每一轮的最小值

functionselectSort(arr){//定义index存储最小值的下标letindex;//外层循环用控制排序进行多少轮for(leti=0;i<arr.length-1;i++){index=i;//内层循环用于每一轮的数据比较//注意j的起始范围是i+1for(letj=i+1;j<arr.length;j++){//寻找最小值if(arr[j]<arr[index]){//保存最小值的下标index=j;}}//如果index不是目前的头部元素，则交换两者if(index!==i){[arr[i],arr[index]]=[arr[index],arr[i]];}}returnarr;}console.log(selectSort([9,1,5,3,2,8]));//[1,2,3,5,8,9]

插入排序

时间复杂度为O(n2)，稳定

思路

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

functioninsertSort(array){//外层控制循环的次数for(leti=1;i<array.length;i++){lettarget=i;//内层循环用于每一轮的数据比较for(letj=i-1;j>=0;j--){if(array[target]<array[j]){[array[target],array[j]]=[array[j],array[target]];target=j;}else{break;}}}returnarray;}console.log(insertSort([9,1,5,3,2,8]));//[1,2,3,5,8,9]

快速排序

时间复杂度为O(nlogn)，不稳定

思路

1）以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边

2）再按此方法对这两部分数据分别进行快速排序（递归进行）

3）不能再分后退出递归，并重新将数组合并

//快速排序functionquickSort(list){//当list.length<=1时，退出递归if(list.length<=1)returnlist;//找到中间节点letmid=Math.floor(list.length/2);//以中间节点为基准点，比该节点大的值放到right数组中，否则放到left数组中letbase=list.splice(mid,1)[0];letleft=[];letright=[];list.forEach(item=>{if(item>base){right.push(item);}else{left.push(item);}});//重新组合数组returnquickSort(left).concat(base,quickSort(right));}console.log(quickSort([9,1,5,3,2,8]));

归并排序

时间复杂度为O(nlogn)，稳定

思路

1）将给定的列表分为两半（如果列表中的元素数为奇数，则使其大致相等）

2）以相同的方式继续划分子数组，直到只剩下单个元素数组

3）从单个元素数组开始，合并子数组，以便对每个合并的子数组进行排序

4）重复第 3 步单元，直到最后得到一个排好序的数组。

functionMergeSort(array){letlen=array.length;if(len<=1){returnarray;}//将给定的列表分为两半letnum=Math.floor(len/2);letleft=MergeSort(array.slice(0,num));letright=MergeSort(array.slice(num,array.length));returnmerge(left,right);functionmerge(left,right){let[l,r]=[0,0];letresult=[];while(l<left.length&&r<right.length){if(left[l]<right[r]){result.push(left[l]);l++;}else{result.push(right[r]);r++;}}result=result.concat(left.slice(l,left.length));result=result.concat(right.slice(r,right.length));returnresult;}}console.log(MergeSort([6,5,3,1,8,7,2,4]));

算法思想

常见的6种算法思想

递归

优点：使用范围广，简单容易上手

缺点：递归太深，容易发生栈溢出（比如斐波那契数列使用递归进行计算）

使用场景：比如树的遍历、快排、深拷贝、查找字符串的所有组合等

分治算法

思想：将某问题分成若干个子问题，然后解决多个子问题，将子问题的解合并得到最终结果，

比如快速排序（以中间元素为基准，将原来的数组拆分为左右两个数组，依次类推）

使用场景：快速排序、二分查找、归并排序

贪心算法

最终得到的结果并不一定是整体最优解，可能只是比较好的结果

但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的

使用场景：买卖股票

回溯算法

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去

使用场景：比如查找二叉树的路径和二叉树的回溯遍历、字符串中字符的所有排列

动态规划

动态规划也是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的

使用场景：斐波那契数列和爬楼梯问题(爬楼梯问题的解法和斐波那契数列一样)

枚举算法

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的

使用场景：长度为n的数组，随机取m个数，有多少种组合

总结

文中列出了现在市面上比较火的一些题目，同时包含了我面试中遇到的所有算法题

算法在阿里、头条、美团的面试中，几乎是必考的

特别是二叉树，我几乎每次都会遇到，为啥大厂对二叉树这么情有独钟？ 有知道的小伙伴，麻烦在评论区告诉我，感谢

如果小伙伴们看了这篇文章后有所收获，那就是我最大的满足

感谢大家

谢谢你看到最后

如果觉得文章对你有帮助，可以点个「赞」，你的「赞」是我创作的最大动力

欢迎长按图片加 ssh 为好友，我会第一时间和你分享前端行业趋势，学习途径等等。2022 陪你一起度过！
关注公众号后，在首页：

回复指南，高级****前端、算法学习路线，是我自己一路走来的实践。

回复简历，大厂****简历编写指南，是我看了上百份简历后总结的心血。

回复面经，大厂面试题，集结社区优质面经，助你攀登高峰

因为微信公众号修改规则，如果不标星或点在看，你可能会收不到我公众号文章的推送，请大家将本公众号星标，看完文章后记得点下赞或者在看，谢谢各位！

参考资料

[1]

力扣上最长上升子序列的视频讲解: https://leetcode.cn/problems/longest-increasing-subsequence/solution/shi-pin-tu-jie-zui-chang-shang-sheng-zi-xu-lie-by-/

[2]

LeetCode 19.凑零钱问题动态规划: https://www.cnblogs.com/Transkai/p/12444261.html

[3]

二叉树在线构建工具: http://www.easycode.top/binarytree.html

[4]

前端该如何准备数据结构和算法？: https://juejin.cn/post/6844903919722692621

查看原网页: mp.weixin.qq.com