怎么做网站截图,外贸网络营销公司,深圳网站设计多少钱,企业建设网站的空间有哪些问题#xff1a;设计一个算法#xff0c;计算出n阶乘中尾部零的个数 例如: 11! 39916800#xff0c;因此应该返回 2 挑战#xff1a;O(logN)的时间复杂度
想法1#xff1a; 找出1–n中每个数字能够被5或者10整除的次数#xff0c;加在一起就是答案。但是时间复杂度是…问题设计一个算法计算出n阶乘中尾部零的个数 例如: 11! 39916800因此应该返回 2 挑战O(logN)的时间复杂度
想法1 找出1–n中每个数字能够被5或者10整除的次数加在一起就是答案。但是时间复杂度是O(N2).代码如下public static long trailingZeros(long n) { // write your code here long five0; long count0; for(long i1;in;i){ if(i%100){ long ji; while(j1 j%100){ j/10; count; } if(j%50){ while(j1 j%50){ j/5; count; } } }else if(i%50){ long ki; while(k1 k%50){ k/5; count; } } }return count;
}想法2.统计1—n 能被5整除的次数累加求和代码类似上边
想法3对想法2进行优化只对1—n之中能够被5整除的数进行统计。代码如下 public static long trailingZeros(long n) { // write your code here long five0; long count0; if(n5){ return 0; }else if(n5){ return 1; } for(long i5;in;i5){ if(i%50){ long ji; while(j0 j%50){ j/5; count; } } } return count; } 《编程之美》上的想法3 公式Z [N/5] [N/52] [N/53] …不用担心这会是一个无穷的运算因为总存在一个K使得5K N[N/5K]0。 5的倍数贡献一个55的平方贡献两个5~~~. 代码如下 int num 0, i; for(i5; in; i*5) { num n/i; } return num; 又简洁执行效率又高与君共勉之。
