尾部的0和小老鼠喝药

Posted1 by 呼延十 on September 15, 2018 Hot:

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的数列:
    5,10,15,20...
    

    偶数数列:

    2,4,6,8...
    

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

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

因此就有解法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;

实现代码

java版本

public long trailingZeros(long n) {
       long result = 0L;
      while(n != 0){
          n = n/5;
          result += n;
      }
      return result;
   }

shell版本

#! /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). 并不是只有死亡的老鼠才对结果有用。

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





ChangeLog

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

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

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

联系邮箱:huyanshi2580@gmail.com

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