|
题目描述： 设计一个算法，计算出n阶乘中尾部零的个数 您在真实的面试中是否遇到过这个题？Yes 样例 11! = 39916800，因此应该返回 2 写在前面 之前在工作中遇到的问题,一般使用一些逻辑,外加一些"野路子"就可以解决.随着遇到的问题的难度的增加,发现自己需要系统学习和实践一些算法了.于是先找到一个题开始进行刷题.以下是我分析和解决的过程,中间不乏一些野路子,但是过程值得进行参考. 常规想法1: 可以写一个方法,先计算出阶乘的结果,然后再对其取余,直到取余结果不为0,就可以统计出结果.代码很快就写出来,但是当输入参数稍大一些,,结果就出错了.原因是阶乘出的结果比较大,超出了long类型的数据范围. 升级想法一:既然在计算阶乘得到的结果比较大,能不能在做阶乘乘法的时候,边取余(同时除以10)计算结果呢? 结果:计算性能有一点提升.但是只能够通过部分数据测试.经过分析发现阶乘计算结果后,除以10,剩下的数据依旧很大,毕竟阶乘中有那么多质数,质数乘以质数一定不能被10整除哈. 升级想法二:如果多次整除10计算出依旧很大,而且是质数乘以质数的结果,那么对要求的结果没有什么意义,我们以把它们清空变成1,继续做乘法. 等等,我如何才能计算出它们是质数和质数的结果呢?反过来一想,什么样的数能够计算出10呢?是不是只有质数2*5才能计算出来呢?那我只需要统计质因数2和5就可以喽. 于是书写代码,将每个进行乘法的数据中的2和5的次数都计算出来.那么我返回那个次数呢?那个小就返回哪个呗.于是加了一个判断.然后自己心里运行了一下,发现好像5的次数一定会小于2的,于是直接返回5的次数就OK了. 结果如下,到目前为止,算法应该是没有问题了,但是在提交测试的时候,发现计算超时了. public class Solution {
public long trailingZeros(long input) {
long result = Method(input);
return result;
}
// 计算阶乘计算中每个数据包含质因数 5的次数
public static long divideFiveTimes = 0;
public static long Method(long n) {
long i = 1;
for (i = 1; i <= n; i++) {
//中间计算变量,用于计算除以5后能不能继续被5除掉
long tempDivideValue = i;
for (long j = 1; j < tempDivideValue; j++) {
if (tempDivideValue % 5 == 0) {
divideFiveTimes++;
tempDivideValue = tempDivideValue / 5;
}
}
}
return divideFiveTimes;
}
}
升级想法三:说实话,到此为止,我有点心急了,因为这个题属于简单的类型,但是自己搞了挺长时间还没有算出来,有点不服,于是决定使用”野路子”找规律来完成这个题目.根据升级想法二:我计算出几个特殊值(5的n次幂)时的结果,然后就发现一定的规律了,发现结果和输入条件的关系是result = (n-1)/4;但是还有一个问题,如果阶乘不是不是这几个特殊数据呢?自己观察了一下,直接发现需要可以拆分成其他几个特殊值的和. 输入条件 | 输出结果 | 关系 | 25(5的2次方) | 6 | *4+1 | 125(5的3次方) | 31 | *4+1 | 625(5的4次方) | 156 | *4+1 | 3125(5的5次方) | 781 | *4+1 | 15625(5的6次方) | 3906 | *4+1 | 15650 | 3912 | 15625结果+25的结果 |
比如我们输入15650,它不是5的整数幂.但是结果可以分解成5的6次方和5的2次方结果的和.于是调整了一下就通过了测试. public class Solution {
public long trailingZeros(long input) {
long result = newMethod(input);
return result;
}
// 全局变量,统计结果
public static long methodTotalResult = 0;
public static long newMethod(long n) {
// 当小于25时,可以直接进行计算
if (n < 25) {
methodTotalResult = methodTotalResult + n / 5;
return methodTotalResult;
}
// 和5的n次方进行比较
long tempNumberCompare = 1;
for (long i = 1;; i++) {
tempNumberCompare *= 5;
if (tempNumberCompare > n) {
// 输入条件减1,除以4
methodTotalResult += (tempNumberCompare / 5 - 1) / 4;
//将剩下的数据进行递归进行运算
newMethod(n - tempNumberCompare / 5);
break;
}
}
return methodTotalResult;
}
}
终于成功了,后来上网搜索了一下,发现一个更好的解决方法,先拷贝下来,以后研究,不过根据测试发现和我上面运行的效率差不多 long count = 0;
long temp = n/5;
while (temp!=0) {
count+=temp;
temp/=5;
}
return count;
| 
转播
