当前位置：首页 > article >正文

前端常用算法集合

article 2024/12/25 16:06:53

使用前介绍

不借助临时变量，交换整数
加减乘除法
注意：如果是浮点数，对于加减乘除法需要注意浮点数的精度丢失问题。

对象法

数组法

数组去重
方法1（filter，推荐使用）

方法2（新数组法）

方法3（hash表法）

方法4

方法5（同时排序）

方法6（set + Array.from）

方法7（set + …扩展运算符）

实现数组的扁平化
将多维数组变成一位数组：如[1, [2, 3, [4, 5]]] => [1, 2, 3, 4, 5]
toString
局限性：使用 toString() 方法后，所有的元素类型都变成了字符串，再使用Number还原，假设原数组中存在类型不一的元素，则不能还原类型

flat

reduce
遍历每一项，如果值为数组，则递归遍历

递归

数组中含所有不定类型值的去重
普通法

map法

取数组中的最大最小值
排序法

apply方法

数组排序

参考：segmentfault【wscats】十大经典排序算法

冒泡排序

比较相邻的元素，如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
实际排序时，由后往前完成排序动作。

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

快速排序

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

二路归并排序
将两个按值有序序列合并成一个按值有序序列

希尔排序

其他排序应用
数字、英文排序

中文姓名排序

数组乱序
遍历法
取随机位的值与当前的互换

sort法
随机数大于0.5的概率为1/2，然后选择顺序或倒序即可

Number数组中最大差值

打印九九乘法表

求数组交集和差级
ES7方法：

字符串翻转
转换成array

反向遍历

生成随机字符串

判断回文

统计出现最多的元素
最常见的思路是先使用object统计出元素和个数，再循环取最大的，但这样无疑会增加复杂度。所以需要在第一次遍历的时候就缓存好最大的元素。
统计字符串中最多的字母和出现的次数

统计数组中出现最多次数的元素和次数

阶乘
1x2x3x4x5…
递归

非递归

生成斐波那契数列
斐波那契数列（黄金分割数列）: 0、1、1、2、3、5、8、13、21、34，考察递归
递归

非递归

二分查找
查找某个值是否在有序数组中，有则返回索引，数组必须是有序的
注意：
还有一种不传起始和终止下标参数，通过在函数体内使用slice取到新的arr，整体没有这种方法好。
递归

非递归

找出数组当中的质数
质数：也称素数，>1, 有无限个。除1和它自身之外不能被其他数整除，如2、3、5、7等，否则称为合数。

js求1! + 2! + 3! + 4! + 5!(阶乘)
思路：s
转换成 1! + (2 * 1!) + (3 * 2!) + (4 * 3!) + (5 * 4!)

两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例

解答

无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例
示例 1:

示例 2:

示例 3:

解答

整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例
示例 1:

示例 2:

示例 3:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [2^31, 2^31 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解答

走楼梯
10个台阶，每次只能上1个、2个或3个，一共有多少种走法？
拆分：
如果上10个台阶，可以分解以下情况：

上9个台阶，最后上1个台阶，假设这种前面9个的走法是 m 种。
上8个台阶，最后上2个台阶，假设这种前面8个的走法是 n 种。
上7个台阶，最后上3个台阶，假设这种前面7个的走法是 l 种。
所以上10个台阶的方法其实就是 m + n + l 种

同理：
1 中的上9个台阶也可以分为：

上8个台阶，最后上1个台阶，假设这种前面8个的走法是 m 种。
上7个台阶，最后上2个台阶，假设这种前面7个的走法是 n 种。
上6个台阶，最后上3个台阶，假设这种前面6个的走法是 l 种。
所以上9个台阶的方法其实就是 x + y + z 种

可以递归为：
f(n) = f(n - 1) + f(n - 2) + f(n - 3)

今日头条算法推导题
假设在今日头条里面，有很多工作人员检查新闻是不是属于虚假新闻，所有新闻真实率到达了98%，工作人员在检验一个真实的新闻把它检验为一个虚假的新闻的概率为2%，而一个虚假的新闻被检验为真实的新闻的概率为5%. 那么，一个被检验为真实的新闻确实是真实的新闻的概率是多大
A.0.9991
B.0.9989
C.0.9855
D.0.96
答案:B
分析条件得到：
真的新闻：98%
假的新闻：2%
真的->假的：2%
假的->真的：5%
分析要求：被检验为真实的新闻确实是真实的新闻
首先要明确被检验为真实的新闻包括了（本来是真的和本来是假的）所以分子为（真->真），分母为（真->真 + 假->真）
结果为：（真->真）/（真->真 + 假->真） = (98%(1-2%)) / (98%(1-2%) + 2%*5%) = 0.9604/0.9614 = 0.9989…
求排列组合
[a] 得到 [a]
[a, b] 得到 [a, b, ab]
[a, b, c] 得到 [a, b, ab, c, ac, bc, abc]
[a, b, c, d] 得到 [a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd, abcd]
分析：

[a]的结果为[a]，数量为1
从[a]到[a, b]，结果其实是[a]的结果加上b元素，然后再将[a]结果中的每一个元素和b进行组合，得到[a, b, ab]，总数为 1+1+1=3
从[a, b]到[a, b, c]，结果其实是[a, b]的结果加上c元素，然后将[a, b]结果中的每一个元素和c进行组合，得到[a, b, ab, c, ac, bc, abc]，总数为3+1+3 = 7

所以，n个元素的排列组合为：fn = f(n-1) + 1 + f(n-1)
要实现多个元素的排列组合，可以从1个元素开始算，随着遍历往后移动，将前一个的结算结果与新元素拼接，然后进行组合，完成之后再覆盖临时变量
实现：