【第07题】给定 n，求 1 × 2 × 3 × … × n 的乘积 | 两种解法
- 主要知识点
- 习题
- 1. Leetcode 面试题 16.05. 阶乘尾数
- 题目描述
- 初见
- 思路
- 代码
- 2. Leetcode 793. 阶乘函数后 K 个零
- 题目描述
- 初见
- 思路
- 代码
- 总结
说到阶乘的计算，必然是迭代与递归啦，直接进入习题~
习题 1. Leetcode 面试题 16.05. 阶乘尾数 题目描述初见设计一个算法，算出 n 阶乘有多少个尾随零。
说明: 你算法的时间复杂度应为 O(log n) 。
由于乘法中 0 的个数只能由
2
∗
5
2 * 5
2∗5 得到（
x
∗
10
x*10
x∗10 也可以分解为
2
∗
5
2*5
2∗5），且阶乘计算中每出现
1
1
1 个
5
5
5 则必然出现至少
1
1
1 个
2
2
2，因此计算阶乘中末尾
0
0
0 的个数相当于_计算
n
!
n!
n! 中有多少个
5
5
5_。
撇开说明，我们直接有：
int trailingZeroes(int n) {
int result(0);
for (int i = n; i >= 0; i--) {
int find = i;
while (find > 4 && find % 5 == 0) {
find /= 5;
result++;
}
}
return result;
}
然后，我们超时了…当然，对每个数进行搜索出现超时也是理所当然的。那么我们更换一种处理方式，计算因子 5 5 5 在 n ! n! n! 中提供的 0 0 0 的个数。
思路- 每个 5 5 5 提供了 1 1 1 个 0 0 0， n ! n! n! 中因子 5 5 5 提供了 n / 5 n/5 n/5 个 0 0 0;
- 每个 25 25 25 提供了 2 2 2 个 0 0 0，但其中有一个在步骤 1 中已经计算在内，因此 n ! n! n! 中因子 25 25 25 提供了 n / 25 n/25 n/25 个 0 0 0：
- 重复上述步骤直至 5 k > n ! 5^k > n! 5k>n!
int trailingZeroes(int n) {
int result(0);
unsigned long long a = 5;
while (n >= a) {
result += n / a;
a *= 5;
}
return result;
}
上述代码时间复杂度为 O ( N ) O(N) O(N)，说明中现实该题时间复杂度可以降为 O ( l o g N ) O(logN) O(logN)，那么还有哪里可以优化呢？没错我们不需要每次都用 n / 5 k n/5^k n/5k，而是可以用第 k k k 次计算得到的结果 n / 5 k − 1 n/5^{k-1} n/5k−1 除以 5 5 5 得到相应的结果：
int trailingZeroes(int n) {
int result(0);
while (n >= 5) {
n /= 5; // 计算包含 5^i 的个数
result += n; // 累加
}
return result;
}
2. Leetcode 793. 阶乘函数后 K 个零
题目描述
初见f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * … * x，且 0! = 1 。
例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
提示： 0 < = k < = 109 0 <= k <= 109 0<=k<=109
受到上一题影响，顺势开始推导公式，寄了…
思路打开解析，二分查找，关闭解析。既然说到了二分查找，那么就让我们掏出之前的二分查找模板（这里）。基于上一个习题，我们搜索时，判断中间值计算阶乘的结果尾数有多少个 0 0 0，若小于要求的 k k k，则令 l = m i d + 1 l=mid+1 l=mid+1，若大于要求的 k k k，则令 r = m i d − 1 r = mid-1 r=mid−1。
代码int getK(unsigned int n) { // 用于判断 n！ 尾数 0 的个数
int result(0);
while (n > 0) {
result += n / 5;
n /= 5;
}
return result;
}
int preimageSizeFZF(int k) {
unsigned int l(k), r(UINT_MAX);
unsigned int curK(0);
while (l <= r) { // 二分查找 [l, r]
int mid = l + ((r - l) >> 1);
curK = getK(mid);
if (curK < k) {
if (mid == INT_MAX) {
return 0;
}
l = mid + 1;
} else if (curK > k){
r = mid - 1;
} else {
return 5; // 1
}
}
return 0;
}
- 若找到一个 mid 满足 f(n) = k，则由阶乘性质，必有 5 个数满足 f(x) = k
- 能用算法解决的问题就可以绕过数学问题~不是所有算法都是建立在特定问题的数学基础上
