JS设计一个算法,计算出n阶乘中尾部零的个数

2019-12-21  本文已影响0人  年轻人不喝鸡汤

好久没有写日记了,最近在整理思路,话不多说进入正题。
上班的时候闲来无事,装备搞一搞lintCode


QQ截图20191221093931.png

这个看上去挺简单的,写起来却一点不简单,想了好久才写出来
题目挑战要求我们需要实现O(logN)的时间复杂度。如果按照我们之前的思路肯定要用到循环遍历,如果这样就肯定不是O(logN)的时间复杂度了。
第一步:我们来研究一下这个阶乘后面的0是怎么出来的。
发现除了偶数与5相乘或者10和10相乘可以得到0,好像其他的不能得到0,
其实10也是5和偶数相乘得到的。我们就可以发现末尾出现的0是5自身或与偶数相乘之后的产生的。
得到一句话:n的阶乘末尾的0的个数取决于n中有几个5

第二步:分析了好了,可以开始写代码了(JavaScript写的)

const   trailingZeros = function(n) {
    let num = 0
    while( n > 0){
       // 对了这里要取整
        n = parseInt(n / 5)
        num += n
  }
}

想了好久,我好菜啊

上一篇 下一篇

猜你喜欢

热点阅读