设计一个算法,计算出n阶乘中尾部零的个数
11! = 39916800,因此应该返回 2
O(logN)的时间复杂度
因此就有解法1: 1.对每个数字依次除以5,如果余数为0则+1,如果得到的商除以5余数仍为0则再加一,直到余数不为0再继续下一数字。 实例:
求30!
解:
1/5 = 0 余 1;pass
2/5 = 0 余 2;pass
...
5/5 = 1 余 0;+ 1;1/5 = 0 余 1;pass
...
10/5 = 2 余 0;+1;2/5 = 0 余 2;pass
...
...
25/5 = 5 余 0; +1;5/5 = 1 余 0; + 1;1/5 = 0 余 1;pass
..
..
这个方法可以实现结果,但是时间复杂度至少是O(N),因为需要遍历一遍数字,所以不做实现。
解法2 1.对所求数字除以5,得到的商即为该数字之下的数字包含多少5(未考虑5的幂),对拿到的商再次除以5,即为该数字之下包含多少个5的平方(25,因为除了2次5) ,对拿到的商再除以5,即为包含多少5的立方,直到商为0;
public long trailingZeros(long n) {
long result = 0L;
while(n != 0){
n = n/5;
result += n;
}
return result;
}
#! /bin/bash
num=$1
echo $num
result=0
while (( $num!=0 ))
do
num=`expr $num / 5`
result=`expr $result + $num`
done
echo $result
这道题其实不算算法题,因为没有必要写代码实现,但是解决的思路却是应用了一些算法知识,而鉴于见到这道题太多次了,所以在此记录一下。
有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
5.
1号 | 2号 | 3号 | 水的编号 |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 2 |
0 | 1 | 1 | 3 |
1 | 0 | 0 | 4 |
1 | 0 | 1 | 5 |
1 | 1 | 0 | 6 |
1 | 1 | 1 | 7 |
将水按照从0到7编号,将三只小老鼠固定位置且编号。 (1).0为不喝,1为喝,因此编号为0的水,所有老鼠都不喝。 (2).编号为1的水只有3号喝… (3).编号为5的水1号和3号喝 (4).编号为7的水所有老鼠都喝。 (5).当一周后,将死亡的老鼠置为1,没死亡的置为0,根据排列算出10进制,即为毒药编号。
2018-09-15 添加尾部的0&喝药药的小老鼠
以上皆为个人所思所得,如有错误欢迎评论区指正。
欢迎转载,烦请署名并保留原文链接。
联系邮箱:huyanshi2580@gmail.com