衡阳市网站建设_网站建设公司_VPS_seo优化

题目概述

LeetCode 172. Factorial Trailing Zeroes：给定一个整数 n，返回 n! 中尾随零（结尾连续的 0）的个数。leetcode​

注意：

• n! = n × (n − 1) × … × 2 × 1
• 0 ≤ n ≤ 10^4
• Follow up：是否可以在对数时间复杂度内求解。leetcode​

初始直观思路与问题

一开始容易想到的思路：

1. 从 n 遍历到 1，依次把每个数乘起来，或者分解每个数的因子。
2. 对于是 10 的倍数的数字，持续除以 10，统计能除多少次，对应贡献多少个尾 0。
3. 再额外统计因子 2、5 的个数，用 min(2 的个数, 5 的个数) 作为 0 的个数。

这个思路有两个主要问题：

1. 时间复杂度不达标：从 n 遍历到 1，是 O(n) 的复杂度，无法满足题目要求的对数时间复杂度。leetcode​
2. 统计不完整：只关注 10 的倍数，会漏掉像 5、25、125 这些仅包含 5 但不包含 2 的数，它们仍然会和其他数里的 2 组合成 10，从而贡献尾 0。leetcode​

经典反例：

• 当 n = 25 时：5, 10, 15, 20, 25 这些数都至少贡献一个 5，其中 25 = 5 × 5，其实贡献两个 5。
• 正确答案是 6 个尾 0，而只简单"按 5 的步长遍历"的次数只有 5，会少算一个。leetcode​

正确数学结论

要理解这个题，有两个关键事实：

1. 每一个尾 0 来自一个因子对 2 × 5。
2. 在 n! 中，因子 2 的数量远远多于因子 5 的数量，因为每个偶数都会贡献 2，而只有 5 的倍数才会贡献 5。leetcode​

因此：

• 尾 0 的个数 = n! 中因子 5 的总个数。
• 不需要显式统计因子 2，只要准确统计所有 5 的个数即可。leetcode​

更细一点地看因子 5：

• 每个 5 的倍数（5, 10, 15, 20, …）至少贡献一个 5。
• 每个 25 的倍数（25, 50, 75, …）会额外多贡献一个 5，因为 25 = 5 × 5。
• 每个 125 的倍数又会额外多贡献一个 5，以此类推。leetcode​

所以总的因子 5 个数 =

• ⌊n / 5⌋（所有含至少一个 5 的数）
• ⌊n / 25⌋（再补上每个 25 里多出来的那一个 5）
• ⌊n / 125⌋
• … 直到除出来变成 0 为止。leetcode​

对数时间的实现思路

按上面的数学结论，可以用一个简单的循环完成统计：

1. 初始化 count = 0。
2. 当 n ≥ 5 时：
   • 把 n 除以 5，累加到 count 上。
   • 再把 n 更新为 n / 5，继续下一轮。

伪代码：

while (n >= 5): count += n / 5 n /= 5

这个循环每次都把 n 缩小 5 倍，因此循环次数大约是 log_5(n)，即对数级别，满足题目的 follow up 要求。leetcode​

直观理解：

• 第一次循环：统计所有含至少一个 5 的数（5 的倍数）。
• 第二次循环：在已经是 5 的倍数的这些数中，再找出那些还能再分出一个 5（25 的倍数）。
• 第三次循环：统计 125 的倍数多出的 5，等等。

代码实现（C 语言示例）

下面是在 LeetCode 上通过、同时满足对数时间复杂度的 C 语言解法：leetcode​

inttrailingZeroes(intn){intcount=0;// Count factors of 5, 25, 125, ...while(n>=5){count+=n/5;n/=5;}returncount;}

• 时间复杂度：O(log n)，每次循环 n 都除以 5。
• 空间复杂度：O(1)。

面试思路与常见追问

在面试中，可以从"错误但直观"的想法，逐步走到最终解法：

1. 先说直觉：尾 0 来源于 2 × 5，n! 里 2 很多，关键是统计 5。
2. 面试官可能会问：
   • “如果只遍历 5 的倍数，为什么会错？”
   • “25、125 这种包含多个 5 的数如何处理？”
   • “你提到的算法时间复杂度是多少？如何优化到对数？”
3. 然后引出：
   • 用 ⌊n / 5⌋ + ⌊n / 25⌋ + ⌊n / 125⌋ + … 来统计所有 5 的个数。
   • 对应代码就是不断 n /= 5 并累加 n。

这样一套讲下来，不仅能 AC 这道题，还能很好展示对数学本质和时间复杂度的理解，非常适合写在博客或者当作面试笔记。

https://leetcode.com/problems/factorial-trailing-zeroes/submissions/1877712958/?envType=study-plan-v2&envId=top-interview-150

https://leetcode.com/problems/factorial-trailing-zeroes/description/?envType=study-plan-v2&envId=top-interview-150