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

这个看上去挺简单的,写起来却一点不简单,想了好久才写出来
题目挑战要求我们需要实现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
}
}
想了好久,我好菜啊
网友评论