从零学算法172

本文主要是介绍从零学算法172，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

172.给定一个整数 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 就表示乘的过程中有几个 10 相乘了，比如 5 的阶乘是 1x2x3x4x5 其中包含了一个 10，即 1x3x4x(2x5)，所以我们的问题就转换成了阶乘过程中有几个 5x2，但这还是有点复杂，我们再观察会发现，2 的个数绝对是远远多余 5 的个数的，即我们不需要找 5x2 有几对，我们只需要找有几个因数 5 就够了。
• 由于 25 表示 2 个 5 相乘,125 表示 3 个 5 相乘…，所以我们在统计时要把每个数分解成 n 个 5 相乘

•   public int trailingZeroes(int n) {int n5=0;for(int i=1;i<=n;i++){int temp = i;// 分解成 n 个 5while(temp%5==0){n5++;temp/=5;}}return n5;}
  

• 以上代码还能够优化，因为每 5 个数就会产生一个 5 的倍数，所以比如 1-10 中包含的 5 的个数其实就是 10/5=2，但是直到 1-25 就不一样了，因为 25 包含了两个 5，所以他等于 25/5 + (25/5/5) = 6(拆解后还剩几个 5)，1-125 同理，包含了 125/5 + (125/5/5) + (125/5/5/5) = 31…

•   public int trailingZeroes(int n) {int n5=0;while(n>=5){n5+=n/5;n/=5;}return n5;}
  

这篇关于从零学算法172的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---