前端中常见的算法题

[Leo-lin214]

本文主要总结一下常见的算法题，注重积累，所谓厚积薄发啦。🤔

找出数组中重复次数最多的元素

栗子：

[1, 2, 3, 1, 5, 6] 重复次数最的元素为 1

中心思路：

新创建一个对象，开始遍历数组，每次都判断当前遍历的元素是否在对象中，有就将对象相应的元素值 +1，若不存在则初始化其值为1，另外需要两个变量分别保存当前出现最多的次数值和出现次数最多的元素，一旦在遍历过程中大于该保存次数，则直接把该次数重新赋予在变量中以及属性变量中。

水仙花数

先简单说明一下什么是水仙花数，其实就是一个数字有 N 位数，那么这个数字每一位数字的 N 次方和就等于本身。

栗子：

153 = 1^3 + 5^3 + 3^3

370 = 3^3 + 7^3 + 0^3

1634 = 14^4 + 64^4 + 34^4 + 44^4

判断一个数是否为水仙花数思路：

直接将一个数 A 转化为字符串 B，拿出它的长度 L，遍历字符串 B，每个元素的 L 次方相加，直接判断总和是否和 A 相等，若是则为水仙花数，若不是则不是水仙花数。

给出 n，找到所有的 n 位十进制水仙花数思路：

先确定要搜索的范围，10 ** (n-1) ~ 10 ** n，接着从最小值到最大值之间的数进行遍历，判断每一个是否为水仙花数，拿出来。

反转一个3位整数

栗子

123 反转后为 321

900 反转后为 9

数组操作

+[number.toString()].reverse().join('')

相当于

parseInt([number.toString()].reverse().join(''))

爬楼梯

栗子

一个小孩爬一个 n 层台阶的楼梯，他每次可以跳 1 步、2 步或者 3 步，那么 n 层楼梯有多少种不同的爬法？

类似斐波那契数列处理，递归思想

1层楼梯，1中方案

2层楼梯，2种方案

3层楼梯，4中方案

4层楼梯，7种方案

5层楼梯，13种方案

好明显，n层楼梯有F(n-1) + F(n-2) + F(n-3)种方案。

丑数

栗子

设计一个算法，找出只含素因子 2，3，5的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ...

需要说明的是，符合条件的数基本都是素因子的倍数，除了 1 之外。

处理思路

通过三个变量分别保存2，3，5三个值的初始索引，遍历n次，每次都将2，3，5乘以各自变量，然后取最小值push进一个新的数组中，相应的最小值索引加1，以此类推。

// [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
const nthUglyNumber = function(n) {
  let arr = [1];
  let min,
    nex2,
    nex3,
    nex5,
    i2 = i3 = i5 = 0;
  for (let i = 1; i < n; i++) {
    // 除了第一个数，每个数都是2、3、5的倍数，把它们的倍数找出来，数字较小添加进去
    nex2 = arr[i2] * 2;
    nex3 = arr[i3] * 3;
    nex5 = arr[i5] * 5;
    min = Math.min(nex2, nex3, nex5);
    // 增加他们的倍数 为下次计算做准备
    if (min === nex2) i2++;
    if (min == nex3) i3++;
    if (min == nex5) i5++;
    arr.push(min);
  }
  return arr[arr.length - 1];
  // return arr
}