当前等级

题目

Write a program that will calculate the number of trailing zeros in a factorial of a given number. N! = 1 2 3 … N Be careful 1000! has 2568 digits… 写一个程序来计算一个给定数的阶乘中的尾随零的个数。 N！= 1 2 3 … N 注意 1000！有2568个数字。。。

例子

zeros(6) = 1

6! = 1 2 3 4 5 * 6 = 720 —> 1 trailing zero

zeros(12) = 2

12! = 479001600 —> 2 trailing zeros

原题链接

分析

直接求这个数的阶乘再判断有几个0并不合适，应该用其他的方式去判断最后的结果有几个0。我们注意到判断结尾有几个0其实就等价于判断这个数是5、55 、55*5 …的几倍，将他们加起来就是结尾0的个数了。

我的解法

  1. public class Solution {
  2.   public static int zeros(int n) {
  3.     int zeros = 0;
  4.     int i = 5;
  5.     while (n/i > 0){
  6.         zeros += n/i;
  7.         i = i*5;
  8.     }
  9.     return zeros;
  10.   }
  11. }

参考解法

  1. public class Solution {
  2.   public static int zeros(int n) {
  3.     int res = 0;
  4.     for (int i = 5; i <= n; i *= 5) {
  5.       res += n / i;
  6.     }
  7.     return res;
  8.   }
  9. }
  1. public class Solution {
  2.   public static int zeros(int n) {
  3.       if(n/5 == 0)
  4.         return 0;
  5.       return n/5 + zeros(n/5);
  6.   }
  7. }

提升

  1. 抓住问题的关键点，求0的个数，所以并不需要求阶乘
  2. 容易忽视 5 —>1个0、 25 —>2个0
  3. 用递归写法更优雅，更容易理解，但时间和空间的消耗比较大，自行取舍吧