leetcode172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 104
题目分析
- 问题定义：计算一个整数
n的阶乘中末尾零的个数。 - 关键概念：末尾零的个数取决于因子
5的个数。
算法介绍
- 动态规划：实际上，这个问题可以通过找出因子
5的个数来解决，因为每个10包含一个5。
算法步骤
- 初始化计数器
five为0，用于记录因子5的个数。 - 遍历从5到
n的每个数i，步长为5，因为只有当数字包含因子5时，它才会增加末尾零的个数。 - 在每个包含因子
5的数i中，将five增加1。 - 返回
five，即末尾零的个数。
算法流程
具体代码
class Solution {
public:int trailingZeroes(int n) {int five=0;for(int i=5;i<=n;i+=5){for(int x=i;x%5==0;x/=5){five++;}}return five;}
};
算法分析
- 时间复杂度：O(n/5)，因为每次循环都跳过了4个数字，所以时间复杂度接近于O(n)。
- 空间复杂度：O(1)，只需要常数级别的额外空间。
- 易错点：正确理解为什么只需要计算因子
5的个数。
相似题目
| 题目 | 链接 |
|---|---|
| 600. 不含连续1的非负整数 | LeetCode |
| 326. 3的幂 | LeetCode |
| 125. 验证回文串 | LeetCode |
