找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1366|回复: 2
收起左侧

[讨论] 分享下32题的解法

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 3-23-2015 08:50 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 timeforce 于 3-23-2015 08:52 AM 编辑

这题话了不少时间,看了下AC率不是那么高,分享下我的解法。首先这题得用数学思想先处理下,我是参考了这里prob 2的解题思想:http://www.ganitcharcha.com/view ... on-Factorial-and-it

1. 先通过上面链接的corollary 1求出k的上下限
2. 通过M = 5 ^ k, 得倒M的上下限(左右闭区间)
3. 通过binary search的方法在M的上下限中找trailing zero等于N的数,特殊情况是,假如不存在这样的M, 则直接返回此时的上限。例如N = 5, 我们可以知道最小的至少有5个trailing zero的M是25 (它有6个trailing zero)
  1. class Solution {
  2.         public long findM(long n) {
  3.                 long leftBound = (long) Math.floor(Math.log((double) (n * 4 + 1)) / Math.log(5));
  4.                 long rightBound = (long) Math.ceil(Math.log((double) (n * 4 + 1)) / Math.log(5));
  5.                 long start = (long)Math.pow(5, leftBound);
  6.                 long end = (long)Math.pow(5, rightBound);
  7.                
  8.                 long res = 0;
  9.                 while(start <= end){
  10.                         long mid = start + (end - start) / 2;
  11.                         if(trailingZeroes(mid) == n){
  12.                                 if(mid == start || (mid > start && trailingZeroes(mid-1) < n)){
  13.                                         return mid;
  14.                                 }else{
  15.                                         end = mid - 1;
  16.                                 }
  17.                         }else if(trailingZeroes(mid) < n){
  18.                                 start = mid + 1;
  19.                         }else{
  20.                                 end = mid - 1;
  21.                         }
  22.                 }
  23.                 return start;
  24.         }
  25.         private long trailingZeroes(long n){
  26.                 long sum = 0;
  27.                 while(n / 5 > 0){
  28.                             sum += n / 5;
  29.                             n = n / 5;
  30.                 }
  31.                 return sum;
  32.         }
  33. }
复制代码



781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 3-23-2015 02:08 PM | 显示全部楼层
thanks for your sharing! it's difficult
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

10

主题

0

精华

132

积分

资深会员

Rank: 2

积分
132
发表于 3-29-2015 05:38 PM | 显示全部楼层
多谢楼主分享
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表