- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

101算法javaScript描述【3】

Ustinian_2022 发表于 2022/08/06 20:53:20 2022/08/06

【摘要】数学在做算法时，可能需要运用一些数学知识。数学也是计算机的基础，这部分章节的内容相对于后面的章节比较轻松。在实际的面试中，用到的数学知识大纲为初中，极少可能超纲到高中，所以大家不用过于担心。本章节分为 3 个部分：Part 1罗马数字转整数Fizz Buzz计数质数Part 23的幂Excel表序列号快乐数阶乘后的零Part 3Pow(x, n)两数相除分数到小数x的平方根罗马数字转整数、...

数学

在做算法时，可能需要运用一些数学知识。数学也是计算机的基础，这部分章节的内容相对于后面的章节比较轻松。在实际的面试中，用到的数学知识大纲为初中，极少可能超纲到高中，所以大家不用过于担心。

本章节分为 3 个部分：

Part 1
- 罗马数字转整数
- Fizz Buzz
- 计数质数
Part 2
- 3的幂
- Excel表序列号
- 快乐数
- 阶乘后的零
Part 3
- Pow(x, n)
- 两数相除
- 分数到小数
- x的平方根

罗马数字转整数、Fizz Buzz和计数质数

罗马数字转整数

罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。

分别对应的数值为：1 ，5，10，50，100，500，1000 。

例如，罗马数字 3 写做 III，即为三个并列的 1。12 写做 XII，即为 X+II。 26 写做 XXVII, 即为 XX+V+I。

通常情况下，不能出现超过连续三个相同的罗马数字并且罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V(5) 和 X(10) 的左边，来表示 4 和 9。
X 可以放在 L(50) 和 C(100) 的左边，来表示 40 和90。
C 可以放在 D(500) 和 M(1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例

输入:"III"
输出:3

输入:"IV"
输出:4

输入:"LVIII"
输出:58

输入:"MCMXCIV"
输出:1994

方法一遍历

思路

先遍历特殊值，如果有特殊值，先累加特殊值，然后用正则去掉特殊值，再遍历剩余的数字。

代码

const romanToIntOne = function (num) {
  const roman = {
    IV: 4,
    IX: 9,
    XL: 40,
    XC: 90,
    CD: 400,
    CM: 900
  };
  const list = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000
  };
  let result = 0;
  // 先遍历特殊值
  for (const key in roman) {
    // 检测输入值是否含有特殊值
    if (num.includes(key)) {
      // 用正则去掉特殊值
      const reg = new RegExp(key);
      num = num.replace(reg, '');
      result += roman[key];
    }
  }
  for (const i of num) {
    // 累加正常罗马数
    result += list[i];
  }
  return result;
};

复杂度分析

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

上述解法中，每个数字都被遍历了一次，时间复杂度跟数字的个数 nnn 线性相关，因此为 O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)

方法二 switch + includes 法

思路

先遍历所有罗马数字进行累加，对于特殊数字的循环，比如：5+1=6，而实际是 4，相差 2，所以需要在结果上减去 2，以此类推。

代码

const romanToIntTwo = function (num) {
  let result = 0;
  for (const c of num) {
    switch (c) {
      case 'I':
        result += 1;
        break;
      case 'V':
        result += 5;
        break;
      case 'X':
        result += 10;
        break;
      case 'L':
        result += 50;
        break;
      case 'C':
        result += 100;
        break;
      case 'D':
        result += 500;
        break;
      case 'M':
        result += 1000;
        break;
    }
  }
  // 减去特殊组合
  if (num.includes('IV') || num.includes('IX')) result -= 2;
  if (num.includes('XL') || num.includes('XC')) result -= 20;
  if (num.includes('CD') || num.includes('CM')) result -= 200;
  return result;
};

复杂度分析

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1)

Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

如果 n 是 3 的倍数，输出“Fizz”；
如果 n 是 5 的倍数，输出“Buzz”；
如果 n 同时是 3 和 5 的倍数，输出 “FizzBuzz”。

示例

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

方法一遍历

思路

很简单，只需要判断 1 - n 的每个数字是否能被 3、5、15 整除，输出对应的字符串即可。

详解

第一步，申请一个数组 arr，用于存放每个数字转换后字符串。
第二步，循环遍历 1−n1-n1−n 的每个数字。如果该数字能被15整除（即取余为0），则该数字对应的字符串为 “FizzBuzz”；如果能被3整除，则为 “Fizz”；如果能被5整除，则为 “Buzz”；否则，为该数字即可。

代码

/**
 * @param {number} n
 * @return {string[]}
 */
const fizzBuzz = (n) => {
  const arr = [];
  for (let i = 1; i <= n; i += 1) {
    if (i % 15 === 0) { // 被15整除
      arr.push('FizzBuzz');
    } else if (i % 3 === 0) { // 被3整除
      arr.push('Fizz');
    } else if (i % 5 === 0) { // 被5整除
      arr.push('Buzz');
    } else {
      arr.push(i.toString());
    }
  }
  return arr;
};

复杂度分析

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

上述解法中，每个数字都被遍历了一次，时间复杂度跟数字的个数 nnn 线性相关，因此为 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)

上述解法中，申请了大小为 nnn 的数组空间，空间复杂度跟数字的个数 n 线性相关，因此为 O(n)O(n)O(n)。

方法二：字符串累加

思路

这种方法也很简单，因为 15 的倍数输出 FizzBuzz，正好是 3 的倍数输出的 Fizz 拼接上 5 的倍数输出的 Buzz，所以只需要单独写 2 个 if 判断，将字符串拼接即可。

详解

第一步，申请一个数组 arr，用于存放每个数字转换后字符串。
第二步，循环遍历 1−n1-n1−n 的每个数字。定义一个空字符串 str，用于临时存放字符串拼接的结果。如果能被3整除，则 str 追加字符串 “Fizz”；如果能被5整除，则 str 追加字符串 “Buzz”；同时能被3和5整除的话，str 的值就为 “FizzBuzz” 了；否则，为该数字即可。

代码

/**
 * @param {number} n
 * @return {string[]}
 */
const fizzBuzz = (n) => {
  const arr = [];
  for (let i = 1; i <= n; i += 1) {
    let str = '';
    if (i % 3 === 0) {
      str += 'Fizz';
    }
    if (i % 5 === 0) {
      str += 'Buzz';
    }
    if (i % 3 !== 0 && i % 5 !== 0) {
      str += i;
    }
    arr.push(str);
  }
  return arr;
};

复杂度分析

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

上述解法中，每个数字都被遍历了一次，时间复杂度跟数字的个数 nnn 线性相关，因此为 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)

上述解法中，申请了大小为 nnn 的数组空间，空间复杂度跟数字的个数 nnn 线性相关，因此为 O(n)O(n)O(n)。

计数质数

统计所有小于非负整数 n 的质数的数量。

示例

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

方法一暴力法

思路

首先回顾质数的定义，质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。所以，我们可以根据定义直接从 2 开始直到 n 根据定义判断每一个数字是否为质数。

详解

首先我们定义一个方法 isPrime 用于判断一个自然数是否为质数，根据乘法交换律，判断其是否有因子的边界为 n 的平方根即可。
循环从 2 到 n 判断是否为质数，将数量存入 count 计数器中。

代码

function isPrime (n) {
  // 判断是否为质数
  if (n === 2 || n === 3) {
    return true;
  }
  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }
  const sqrtN = Math.sqrt(n); // 根据乘法交换律，判断边界为平方根即可
  for (let i = 3; i <= sqrtN; i += 2) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

function countPrimes (n) { // 返回质数数量
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime(i)) { // 循环判断
      count++;
    }
  }
  return count;
}

复杂度分析

时间复杂度： O(n∗√n)O(n*√n)O(n∗√n) 外层需要判断 nnn 个数是否质数，判断为质数是需要进行 √n√n√n 次计算
空间复杂度：O(1)O(1)O(1) 使用了常数个变量，即为 O(1)O(1)O(1)。

方法二埃拉托斯特尼筛法

思路

给出要筛选数值的范围 n，找出 √𝑛 以内的素数 p1, p2…, p𝑘。先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个素数，也就是 3 筛，把 3 留下，把 3 的倍数剔除掉；接下去用下一个素数 5 筛，把 5 留下，把 5 的倍数剔除掉；不断重复下去……不断的剔除不需要比对的元素；每计算一个数，都要把它的倍数去掉。到了n，数一下留下了几个数。

详解

1.Uint8Array 数组类型表示一个8位无符号整型数组，创建时内容被初始化为 0。创建完后，可以以对象的方式或使用数组下标索引的方式引用数组中的元素；

2.arr 用来记录“已经找过的数的倍数”。内层循环中，一次把找过数的倍数，对应的 arr 下标元素设置为 true，这样外循环时不会计数；

3.外层循环用来计数，如果 arr 数组对应值是 false，即表示为质数，则计数器 count 加一，最终获取所有质数数量。

代码

const countPrimes = function (n) {
  let count = 0;
  const arr = new Uint8Array(n);
  for (let i = 2; i < n; i++) {
    if (!arr[i - 1]) {
      count++;
      for (let j = i * i; j <= n; j += i) {
        arr[j - 1] = true;
      }
    }
  }
  return count;
};

复杂度分析

时间复杂度： O(nloglogn)O(nloglogn)O(nloglogn)

对每一个iii,要划掉n/i n/in/i 个数, 要进行 n/in/in/i 次运算，全部加起来，就是 nnn (从 1 到 √𝑛 之间的 1/i 之和)*，*简单讲就是 (从 1 到 nnn 之间的 1/i1/i 1/i之和) 约等于 logloglog (对所有 k 从 1 到 n 之间的 1/k 之和)，后者是logn log nlogn，所以前者就是 loglognloglog nloglogn；最外层需要判断 nnn 次；所以最终时间复杂度为O(nloglogn)O(n loglog n)O(nloglogn)。
空间复杂度：O(n)O(n)O(n)

上述解法中，申请了大小为 nnn 的数组空间，空间复杂度跟数字的个数 nnn 线性相关，因此为 O(n)O(n)O(n)。

3的幂、Excel表列序号、快乐数和阶乘后的零

3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

进阶： 你能不使用循环或者递归来完成本题吗？

示例 1：

输入: 27
输出: true

示例 2：

输入: 0
输出: false

示例 3：

输入: 9
输出: true

示例 4：

输入: 45
输出: false

题目分析

3 的幂，顾名思义，需要判断当前数字是否可以一直被 3 整除
特殊情况：如果 n === 1，即 3 的 0 次幂的情况，应输出 true

方法一循环求解

思路

基本想法，可以利用循环解决。排除特殊情况后，用待确定的数字 n，循环除以 3，看是否能被 3 整除。

详解

1、判断特殊情况，若待定值 n 小于 1 则直接返回 false

2、循环判断待定值 n 是否可以被 3 整除

3、若不可以被 3 整除则返回 false，若可以则将该数字除以 3，直至循环结束

4、其余情况则返回 true

代码

/**
 * @param {number} n
 * @return {boolean}
 */
const isPowerOfThree = function (n) {
  if (n < 1) {
    return false;
  }
  while (n > 1) {
    // 如果该数字不能被 3 整除，则直接输出 false
    if (n % 3 !== 0) {
      return false;
    } else {
      n = n / 3;
    }
  }
  return true;
};

复杂度分析

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

该解法中， while 循环耗时 O(n)O(n)O(n)，其余为 O(1)O(1)O(1)，因此总时间复杂度为 O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)

该解法中，未申请额外的空间，因此空间复杂度为 O(1)O(1)O(1)。

解法二递归求解

思路

或许，我们可以考虑使用递归的方法实现。递归的思路类似于循环，只不过将循环体改为方法的递归调用。

详解

1、判断特殊情况 n === 1 时，直接返回 true

2、判断特殊情况 n <= 0 时，直接返回 false

3、若待定值 n 可以被 3 整除，则开始递归

4、若不满足上述条件，则返回 false

代码

/**
 * @param {number} n
 * @return {boolean}
 */
const isPowerOfThree = function (n) {
  // n === 1，即 3 的 0 次幂，返回 true
  if (n === 1) {
    return true;
  }
  if (n <= 0) {
    return false;
  }
  if (n % 3 === 0) {
    // 递归调用 isPowerOfThree 方法
    return isPowerOfThree(n / 3);
  }
  return false;
};

复杂度分析

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

该解法中，递归耗时 O(n)O(n)O(n) ，普通条件判断耗时 O(1)O(1)O(1) ，整个算法时间复杂度为 O(n)O(n)O(n)
空间复杂度：O(n)O(n)O(n)

该解法中，由于递归依赖于栈，因此其空间复杂度为 O(n)O(n)O(n)。

方法三神奇的解法

思路

进阶！既无循环又无递归。

既然要判断输入值是否为 3 的幂，我们可以巧妙的依赖它是否能被 3 的幂的极大值整除来作为判断依据。因此首先要找到 3 的最大次幂。

计算机中最大的整数是 2147483647，转换成 16 进制为 0x7fffffff。Math.log(x) / Math.log(y) 方法可以求出以 y 为底，x 的对数，即 y 的多少次幂的值是 x，我们称之为 maxPow。由于该值不能被整除，此处 maxPow 只需取整数部分。最后，我们可以利用 Math.pow 求出 3 的幂的极大值 maxValue，并检查该值是否能整除待确定的输入值。

详解

1、判断特殊情况 n <= 0 时，直接返回 false

2、求计算机允许情况下 3 的最大次幂，记为 maxPow

3、求 3 的 maxPow 次幂值

4、判断 3 的 maxPow 次幂值是否能整除待定值 n

代码

/**
 * @param {number} n
 * @return {boolean}
 */
const isPowerOfThree = function (n) {
  if (n <= 0) {
    return false;
  }
  // 求 3 的最大次幂
  const maxPow = parseInt((Math.log(0x7fffffff) / Math.log(3)));
  // 求 3 的 maxPow 次幂值
  const maxValue = Math.pow(3, maxPow);
  // 判断该值是否能整除待定值 n
  return (maxValue % n === 0);
};

复杂度分析

时间复杂度：O(1)O(1)O(1)

一般情况下， Math.pow 的时间复杂度为 O(1)O(1)O(1)，取整和除法的复杂度也为 O(1)O(1)O(1)，因此该解法的时间复杂度为 O(1)O(1)O(1)。
空间复杂度：O(1)O(1)O(1)

该解法中，仅申请了 2 个常量级的额外空间，因此空间复杂度为 O(1)O(1)O(1)。

Excel表列序号

给定一个Excel表格中的列名称，返回其相应的列序号。

示例

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
输入: "A",
输出: 1
输入: "AB",
输出: 28

方法一

思路

从末尾开始取得每一个字符对应的数 cur = c.charCodeAt() - 64（因为 A 的caarCode为 64）因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位数字总和 sum += 当前数 进制位数进制位数 = 26，初始化进制位数 carry = 1

详解

创建临时变量 sum 和始化进制位数 carry
循环数组
数字总和 sum += 当前数 * 进制位数
进制位数 *= 26

/**
 * @param {string} s
 * @return {number}
 */
const titleToNumber = function (s) {
  let sum = 0;
  let i = s.length - 1;
  let carry = 1;
  while (i >= 0) {
    const cur = s[i].charCodeAt() - 64;
    sum += cur * carry;
    carry *= 26;
    i--;
  }
  return sum;
};

复杂度分析

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

对于每个元素，通过一次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) O(n)的时间。
空间复杂度：O(1)O(1)O(1)

由于算法中临时变量得个数与循环次数无关，所以空间复杂度为 O(1)O(1)O(1)

方法二

思路

因为有26个字母，相当于 26 进制转 10 进制

详解

26 进制转化 10 进制公式，ans = ans * 26 + num
比如：AB = 12* 6 +2 = 28，ZY=26 * 26+25 = 701

/**
 * @param {string} s
 * @return {number}
 */
const titleToNumber = function (s) {
  const arr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
  const len = s.length;
  let sum = 0;
  for (let i = 0; i < len; i++) {
    sum = (arr.indexOf(s[i]) + 1) * Math.pow(26, len - 1 - i) + sum;
  }
  return sum;
};

复杂度分析

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

对于每个元素，通过一次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n)O(n) 的时间。
空间复杂度：O(1)O(1)O(1)

由于算法中临时变量得个数与循环次数无关，所以空间复杂度为 O(1)O(1)O(1)

快乐数

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例

输入: 19
输出: true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

方法一尾递归

思路

根据示例来看，函数的执行过程是一个可递归的过程，首先，我们先写一个递归函数来模拟这个执行过程，然后按照示例输入 19 来验证编写函数正确性，然后输入任意数字（比方说 99999），这时，会发现报内存溢出的错误，那这道题就变成了如何解决堆栈溢出的问题：首先，我们要考虑的是，为什么会内存溢出？从题目中，我们可以看到"也可能是无限循环但始终变不到 1"，是"无限循环"导致内存溢出，那我们就应该想一个方式去终结这个"死循环"。首先我们要找到这个循环的规律，怎么找？把递归内容打印（console.log）出来。这时，你会发现一个有规律的死循环。那么，我们只要用一个变量（once）记录已经输入过的值，一旦出现第二次相同输入，就终止递归，并返回"非快乐数"的结果（false）。

详解

申请一个变量来存放已经执行过函数的"输入",如果出现重复输入，则说明进入了死循环，从"示例"来看：{19:true,82:true,100:true}
将输入 19 转化为数组（[1,9]）
将[1,9]进行平方和运算（12+92=821^2 + 9^2 = 8212+92=82）
判断平方和的结果是不是等于 1，若果是，则为"快乐数",否，则继续执行 fn 函数
直到平方和等于 1 或者判定为死循环。

const fn = function (n, once) {
  if (once[n]) {
    return false;
  }
  const list = n.toString().split('');
  let result = 0;
  once[n] = true;
  list.forEach(val => {
    result += Math.pow(parseInt(val, 10), 2);
  });
  if (result === 1) {
    return true;
  } else {
    return fn(result, once);
  }
};

/**
 *
 * @param {number} n
 * @return {boolean}
 */
const isHappy = function (n) {
  const once = {};
  return fn(n, once);
};

复杂度分析

时间复杂度：O(log(n))O(log(n))O(log(n))
空间复杂度：O(1)O(1)O(1)

方法二尾递归

思路

其实和方法一类似，只不过终止循环的条件有所不同，输入 99，观察"函数一"执行时的输出可得，如果函数执行过程中出现 4,16,37,58,89,145,42,20 就不是快乐数，为了稍微提高一下函数执行效率，你也可以简单的枚举以下特殊的快乐数，比方说：1，10，100。

// 函数一
const isHappy = function (n) {
  console.log('n = ', n);
  let result = 0;
  const list = n.toString().split('');
  list.forEach(val => {
    result += Math.pow(parseInt(val, 10), 2);
  });
  if (result === 1) {
    return true;
  } else {
    return isHappy(result);
  }
};

详解

已知非快乐数[4,16,37,58,89,145,42,20]
已知快乐数：1
将输入（19）转化为数组（[1,9]）
将[1,9]进行平方和运算（12+92=821^2 + 9^2 = 8212+92=82）
判断平方和的结果是不是等于 1，若果是，则为"快乐数",否，则继续执行 fn 函数
直到平方和等于 1 或者判定为非快乐数。

const isHappy = function (n) {
  const unHappy = [4, 16, 37, 58, 89, 145, 42, 20];
  if (n === 1) {
    return true;
  }
  if (unHappy.indexOf(n) > -1) {
    return false;
  }
  let result = 0;
  const list = n.toString().split('');
  list.forEach(val => {
    result += Math.pow(parseInt(val, 10), 2);
  });
  if (result === 1) {
    return true;
  } else {
    return isHappy(result);
  }
};

判断优化

可以从 unHappy 取任意一个数作为判断条件，可以减少 indexOf 函数带来的时间消耗。

const isHappy = function (n) {
  if (n === 1) {
    return true;
  }
  if (n === 4) {
    return false;
  }
  let result = 0;
  const list = n.toString().split('');
  list.forEach(val => {
    result += Math.pow(parseInt(val, 10), 2);
  });
  if (result === 1) {
    return true;
  } else {
    return isHappy(result);
  }
};

复杂度分析

时间复杂度：O(log(n))O(log(n))O(log(n))
空间复杂度：O(1)O(1)O(1)

事先通过规律已经找到了所有非快乐数，unHappy 的内存空间的开辟是固定的，所以空间复杂度是 O(1)O(1)O(1)。

阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例1

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例2

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

方法一暴力法

思路

尾数中有 0 必定是是 10 的倍数
尾数中有多少个 0 就就是整个数能有多少个因子 10
因子 10 又可以拆成 2∗52* 52∗5 *，*因此就是找整个数字可以拆分成多少了 2∗52 * 52∗5
因为在因子中 2 的数量一定比 5 多，所以实际上我们只要找到因子 5 的个数就可以找到尾数中 0 的个数了，所以这个问题就可以转换成找因子 5 的个数。

详解

循环 1 ~ n，找出能被 5 整除的数字
找到能被 5 整除的数字，找该数字能被拆分成多少个因子 5
所有的个数相加就是尾数 0 的个数

const trailingZeroes = function(n) {
  let count = 0;
  for(let i = 1; i <= n; i++) {
    let num = i;
    if (num % 5 === 0) {
      while(num % 5===0 && num !== 0) {
       count += 1;
       num = parseInt(num / 5);
      }
    }
  }
  return count;
}

复杂度分析

时间复杂度为: O(n2)O(n^2)O(n2)

因为要进行两次循环，所以时间复杂度为O(n2)O(n^2)O(n2)，当数字比较大的时候有性能问题
空间复杂度：O(1)O(1)O(1)

没有申请额外空间，所以空间复杂度为O(1)O(1)O(1)

方法二

思路

整体思路和方法一基本一致，都是找因子5的个数，只是方法二是在找因子5的个数时做文章，用耗时更少的方法来找5的个数

详解

n! 这些乘数中，每隔 5 个数，肯定会有一个数至少能拆出一个 5 因子。所以 n / 5 = 至少会出现的 5 的个数。
因为 n / 5 并不能完全算出 5 因子的个数，比如若某个数 25 = 5 * 5，分解后得到的 5 也算一个，所以能被 25 因式分解相当于会出现 2 个 5 因子，而第一步中除以 5 算个数的时候已经算了一个了，所以相当于比之前会多一个 5 因子
依此类推，能被 25 5 = 125 因式分解的相当于比之前按 25 因式分解的时候又多出一个 5 因子。能被 125 5 = 625 因式分解的相当于比按 125 因式分解时又多出一个 5 因子。还有 625 * 5 ……

所以n! 的结果可以拆分为多少个 5 因子呢：

n/5 + n/25 + n /125 + n/625 + …

function trailingZeroes(n) {
  let count = 0;
  while (n > 0) {
      n = parseInt(n / 5);
      count += n;
  }
  return count;
}

复杂度分析：

时间复杂度：O(log(n))O(log(n))O(log(n))，

遍历次数为 n/5x=1n / 5^x = 1n/5x=1；即 x=log⁡5(n)x = \log_5(n)x=log5(n)，所以时间复杂度为 O(log(n))O(log(n))O(log(n))
空间复杂度：O(1)O(1)O(1)

没有申请额外空间，所以空间复杂度为O(1)O(1)O(1)

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

101算法javaScript描述【3】

数学

罗马数字转整数

方法一遍历

方法二 switch + includes 法

Fizz Buzz

方法一遍历

方法二：字符串累加

计数质数

方法一暴力法

方法二埃拉托斯特尼筛法

3的幂

题目分析

方法一循环求解

解法二递归求解

思路

Excel表列序号

方法一

方法二

快乐数

方法一尾递归

思路

详解

复杂度分析

方法二尾递归

阶乘后的零

方法一暴力法

方法二

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

101算法javaScript描述【3】

数学

罗马数字转整数

方法一 遍历

方法二 switch + includes 法

Fizz Buzz

方法一 遍历

方法二：字符串累加

计数质数

方法一 暴力法

方法二 埃拉托斯特尼筛法

3的幂

题目分析

方法一 循环求解

解法二 递归求解

思路

Excel表列序号

方法一

方法二

快乐数

方法一 尾递归

思路

详解

复杂度分析

方法二 尾递归

阶乘后的零

方法一 暴力法

方法二

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品

方法一遍历

方法一遍历

方法一暴力法

方法二埃拉托斯特尼筛法

方法一循环求解

解法二递归求解

方法一尾递归

方法二尾递归

方法一暴力法