尾部的0和小老鼠喝药

数据结构和算法 评论

1.尾部的0

来源: lintcode-尾部的0

问题描述

描述

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

样例

11! = 39916800，因此应该返回 2

挑战

O(logN)的时间复杂度

解决思路

  1. 首先排除计算结果然后数末尾的0，一来太low了，二来开销太大并不符合题目中O(logN)的时间复杂度要求。

  2. 分析出现0的原因，直接原因就是与10，100等相乘，同时也有类似于52或者54这样的。而10，100等都可以使用5乘以偶数得到。
    因此得出结论：产生0的成因是：5 * 偶数。

  3. 5的倍数都包含5，5的数列：

    1
    5,10,15,20...

    偶数数列：

    1
    2,4,6,8...

    可见，偶数出现的频率远大于5及其倍数，因此可以默认为：出现一个5，末尾则会出现一个0.

  4. 5的平方，立方等含有更多的5，应多次计算。

因此就有解法1：
1.对每个数字依次除以5，如果余数为0则+1，如果得到的商除以5余数仍为0则再加一，直到余数不为0再继续下一数字。
实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
求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；

实现代码

java版本

1
2
3
4
5
6
7
8
public long trailingZeros(long n) {
       long result = 0L;
      while(n != 0){
          n = n/5;
          result += n;
      }
      return result;
   }

shell版本

1
2
3
4
5
6
7
8
9
10
#! /bin/bash
num=$1
echo $num
result=0
while (( $num!=0 ))
do
  num=`expr $num / 5`
  result=`expr $result + $num`
done
echo $result

2.小老鼠喝药药

来源：网络

这道题其实不算算法题，因为没有必要写代码实现，但是解决的思路却是应用了一些算法知识，而鉴于见到这道题太多次了，所以在此记录一下。

问题描述

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

解题思路

  1. 看到1000和10其实就应该反映过来了，2的10次方为1024，覆盖1000.

  2. 所以此题与8瓶水三只老鼠的解题思路完全一样，因此下面基于8瓶水喝3只老鼠。

  3. 3位的二进制刚好可以表示十进制的8，因此只需要将每瓶毒药按照二进制的1和0来确定某只老鼠喝不喝，一星期后，以老鼠的死亡排列，既可以得出是第几瓶有毒。

  4. 此题误区：
    (1). 死亡的并不一定只有一只老鼠
    (2). 并不是只有死亡的老鼠才对结果有用。

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进制，即为毒药编号。





ChangeLog

2018-09-15 添加尾部的0&喝药药的小老鼠

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。