精华内容
下载资源
问答
  • 阶乘后的0

    2020-03-31 11:31:50
    题目: 给定一个整数 n,返回 n! 结果尾数中零数量。 示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。...要计算出位数有多少0,直接计算出5是那些数因子。 package edu.LeetCode.二; /** * ...

    题目:
    给定一个整数 n,返回 n! 结果尾数中零的数量。

    示例 1:

    输入: 3
    输出: 0
    解释: 3! = 6, 尾数中没有零。
    示例 2:

    输入: 5
    输出: 1
    解释: 5! = 120, 尾数中有 1 个零.
    说明: 你算法的时间复杂度应为 O(log n) 。

    思路:
    要计算出位数有多少0,直接计算出5是那些数的因子。

    package edu.LeetCode.;
    
    /**
     * 给定一个整数n,返回n!结果位数中0的数量
     */
    public class 阶乘后的0 {
        public static int trailingZeroes(int n){
            int count = 0;
            while(n / 5 > 0) {
                count += n/5;
                n /= 5;
            }
            return count;
        }
    
        public static void main(String[] args) {
            int n = 100;
            System.out.println(trailingZeroes(n));
        }
    }
    
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    展开全文
  • 阶乘后的0个数

    2020-03-13 21:40:11
    阶乘后的0个数题目描述题目解析代码实现时间复杂度 题目描述 假设自然数n,n的阶乘结果(n!)结尾0的个数,例如:3! = 3 * 2 * 1 = 6;末尾0个数等于0,5! = 5 * 4 * 3 * 2 * 1 = 120,末尾0个数等于1. 题目解析 第...

    题目描述

    假设自然数n,n的阶乘结果(n!)结尾0的个数,例如:3! = 3 * 2 * 1 = 6;末尾0个数等于0,5! = 5 * 4 * 3 * 2 * 1 = 120,末尾0个数等于1.

    题目解析

    第一种暴力解法,把结果值算出来之后不断除余10,计数每次等于0的个数。
    该方法计算量主要在阶乘,时间复杂度为O(n)。
    第二种解法,因为末尾是0的值只有25的拆分结果值,所以该结果的计算主要是看能拆分成多少个25,例如:11! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 = 1 * 3 * (2 * 5) * 2 * (2 * 5) * 2 * 6 * 7 * (2 * 2* 2) * 9 * 11;
    可以看出2的个数肯定是5多的,具体证明过程就不证明了,相信大家都可以证出来的。

    代码实现

    public static int count = 0;
    
        public static void solution(int n){
    
            if (n % 5 == 0) {
                count++;
                solution(n / 5);
            }
            return;
    
        }
    
    

    时间复杂度

    典型的递归算法:
    设计算次数为x,由于5^x = n;所以

    x=log5n x = log_5n
    复杂度比n降低了很多。

    展开全文
  • 阶乘后的0

    2020-10-22 16:16:44
    题目:给定一个整数 n,返回 n! 结果尾数中零数量。示例 1:输入: 3输出: 0解释: 3! = 6, 尾数中没有零。示例 2:输入: 5输出: 1解释: 5...3.所以要找出5出现次数,5出现次数比2少,有几个5就有几个0。 代码: ...

    题目:给定一个整数 n,返回 n! 结果尾数中零的数量。示例 1:输入: 3输出: 0解释: 3! = 6, 尾数中没有零。示例 2:输入: 5输出: 1解释: 5! = 120, 尾数中有 1 个零.说明: 你算法的时间复杂度应为 O(log n) 。
    思路:
    1.什么情况下会产生0 25=10
    6!=1
    23456=720
    2.找出有2/5的个数 4=2*2 没有0
    3.所以要找出5出现的次数,5出现的次数比2少,有几个5就有几个0。
    代码:
    #include <stdio.h>
    void main()
    {
    int n,i,t,five=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
    t=i;
    while (t%5==0)
    {
    five++;
    t/=5;
    }
    }
    printf("%d\n",five);
    }

    展开全文
  • n阶乘后的 0 个数 题目描述 首先我们看一下题目的描述 给定一个整数 n,返回 n! 结果尾数中零的数量。 示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。 示例 2: 输入: 5 输出: 1 解释: 5! = 120, 尾数中...

    Leetcode历程 – 172. n阶乘后的 0 个数

    题目描述

    首先我们看一下题目的描述
    给定一个整数 n,返回 n! 结果尾数中零的数量。

    示例 1:

    • 输入: 3
    • 输出: 0
    • 解释: 3! = 6, 尾数中没有零。

    示例 2:

    • 输入: 5
    • 输出: 1
    • 解释: 5! = 120, 尾数中有 1 个零.
    • 说明: 你算法的时间复杂度应为 O(log n) 。

    如果不考虑题目末尾的时间复杂度为O(log n),则我们的思考过程是怎么样的呢?

    题解

    1. 算出阶乘 n! , 然后求一下结果中的0的个数。代码如下:

        /**
    	 *  	采用先求阶乘后算0 的方式
    	 */  
        public static int trailingZeroes(int n) {
            int countZero = 0;
    		
    		for(int i = 1; i <= n; i++) {
    			countZero += countFive(i);
    		}  
    		return countZero;
        }
    
    	private static int factorial(int n) {
    		if(n == 0 || n == 1)
    			return 1;
    		else
    			return factorial(n -1) * n;
    	} 
    

    但是考虑到阶乘的 O(x^N) 的指数级复杂度,此法不可行。

    2. 那我们再考虑下题目描述,求阶乘后的 0 的个数,末尾的 0 是由什么产生的呢?

    由 2 * 5 = 10 , 我们可以将阶乘中的每个数是否包含因子 2 和 5 ,包含几个 2 和 5 求出来。以此来求出结果中包含几个 0 ,且由于数字增加的过程可知,当增长到含 5 时, 2 的个数明显是多余 5 的。故而,只需要判断每一个因子是否包含 5 即可。

    可编写代码如下:

        public static int trailingZeroes(int n) {
    		int countZero = 0;
    		
    		for(int i = 1; i <= n; i++) {
    			countZero += countFive(i);
    		}  
    		return countZero;
    	}
    
    	private static int countFive(int i) {
    		int countFive = 0;
    		
    		while(i % 5 == 0) { 
    				countFive ++;
    				i /= 5; 
    		}
    		return countFive;
    	}
    

    我们对此种算法的时间复杂度进行分析:
    在trailingZeroes方法,可以知道,我们对 n 进行了遍历,算法的复杂度为 O(n) , 在方法countFive中,时间复杂度为 ***O(log n)***, 因此,此种算法的时间复杂度为 ***O(nlog n)***。 在test cases 中通过的情况为500/502 , 还有两个测试用例超出了时间限制,所以我们继续优化算法。

    3. 考虑到每两个包含 5 的因子中间的数都是不包含 5 的,所以可以将增加的步长变为 5。

    代码如下:

    public static int trailingZeroes(int n) {
    		int countZero = 0;
    	int spare = n % 5;
    
    	for(int i = 5; i <= (n - spare); i = i+5) {
    		countZero += countFive(i);
    	}  
    	return countZero;
    } 
    
    private static int countFive(int i) { 
    	int countFive = 0;
    		
    	while(i % 5 == 0) { 
    		countFive ++;
    		i /= 5; 
    	}	
    	return countFive;
    }
    

    同样地,我们对算法的时间复杂度进行分析:
    在trailingZeroes()方法,可以知道,我们对 n 进行了遍历,算法的复杂度为 O(n)/5 , 在方法countFive()中,时间复杂度为 ***O(log n)***, 因此,此种算法的时间复杂度为 ***O(nlog n)***。

    但是,相对于上面一种方法,在trailingZeroes() 中我们将时间复杂度变为原来的 1/5.

    但是,我们仍然未能达到题目中的时间复杂度***O(log n)***的要求.在测试中,test cases 通过的情况为 501/502 ,通过查看结果,只有Integer.MAX_VALUE 未通过测试。所以,我们继续优化我们的算法.

    4. 将解法的时间复杂度压缩在 O(log n)

    求出最接近 n 的5的 n 次方的数是多少;即为 log n / log 5 ,然后计算然后依次计算n中包含多少个51、52……5^c,累加即可。

    int count = (int)Math.log(n)/Math.log(5);

    代码如下:

    public int trailingZeroes(int n) {
        int c = (int)(Math.log(n) / Math.log(5));
        int ans = 0;
        for (int i = 1; i <= c; i++) {
            int d = (int)(Math.pow(5,i));
            ans += n / d;
        };
            return ans;
    }  
    

    6. 可简化如下为 n/5 + n /25 + n/125 + …

    编码如下:

    public int trailingZeroes(int n){
        int total = 0;
        while (n >= 5) {
             n = (int)Math.floor(n / 5);
            total += n;
        }
        return total;
    }
    

    到此,此题解决。

    总结

    在做这个题的过程中,我对题目的理解逐渐加深。在算法的时间复杂度上,一步步优化,最终达到题目的要求。虽然是一个 simple 类的题目,但在解题的过程中,逐渐地打通思路。慢慢梳理数字的特征,使我受益良多也体会到了解题的愉悦。

    在前行路上继续加油吧!

    kejin–2019/12/6

    展开全文
  • LeetCode172:阶乘后的0

    2020-02-14 11:28:59
    对于这道题,很容易想到一个思路就是,先求成n的阶乘,然后取模看看有多少个0。这样子做对n比较小时候是可行,但是当n足够大时,就会有溢出风险。而且这样做时间复杂度是O(N),而题目要求时间复杂度是O...
  • LeetCode172.阶乘后的0

    2019-04-07 16:59:02
    原题链接 最终结果的0要根据2和5的数量来确定,而2的数量一定会比5多,所以看5的数量即可 26 / 5 = 5 说明了有5个数贡献了1个5 26 / 25 = 1 说明有1个数贡献了1... 所以26阶乘的0一共有6个0; 26 25 24 23 2...
  • 题目:给定一个整数 n,返回 n! 结果尾数中零的数量。 示例 1: 输入: 3 ...题目很好理解,数阶乘后的数字末尾有多少个零。 最简单粗暴的方法就是先乘完再说,然后一个一个数。 事实上,你在使用暴...
  • 属小于等于n数中包含5个数, O(nlog5(n))O(nlog_5(n))O(nlog5​(n)) 注:25 = 5 × 5,是两个5 class Solution { public: bool zhengchu(int num) { if(num % 5 == 0) return true; return false; } int ...
  • LeetCode: 172.阶乘后的0

    2019-11-29 20:14:00
    一个数n,他的阶乘n! 尾数里面有多少0. 0的出现就是2和5组成。也就是看1-n这n个数字中,各有多少个2和5配对。考虑到2数字肯定比5多,所以只用考虑有多少个5即可。 比如31这个数字,31没有5组合,但是30有...
  • 172. 阶乘后的零 - 力扣(LeetCode) 要求时间复杂度为O(logn), n < 5: 阶乘结尾没有0 n == 5的时候,120会出现一个0 考虑阶乘的性质,要想阶乘末尾的0个数增加,只会在5的整数倍的时候。 更具体的说,当碰到2和...
  • n的阶乘后面有多少个0? 6的阶乘 = 1*2*3*4*5*6 = 720,720后面有1个0。 Input 一个数N(1 ^9) Output 输出0的数量 Input示例 5 Output示例 1这道题关键是分析0是由谁提供,经过分析我们可以知道,2X5=10...
  • LeetCode-172.阶乘后的0

    2020-05-14 19:58:11
    题目: 代码:(只用计算5次数) class Solution { public: int trailingZeroes(int n) { int ans=0; while(n>=5){ ans+=(n/5); n/=5; } return ans; } };
  • 题目描述: 方法:不断除以 5, 是因为每间隔 5 个数有一个数可以被 5 整除, 然后在这些... 直到结果为 0, 表示没有能继续被 5 整除数了 class Solution: def trailingZeroes(self, n: int) -> int: ...
  • LeetCode--172--阶乘后的0

    2018-09-15 10:48:00
    输出: 0 解释:3! = 6, 尾数中没有零。 示例2: 输入: 5 输出: 1 解释:5! = 120, 尾数中有 1 个零. 说明: 你算法时间复杂度应为O(logn)。 times out:时间复杂度O(nlogn),显然不行 1 class Solution...
  • 输出: 0 解释: 3! = 6, 尾数中没有零。 示例 2: 输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes 著作权归领扣网络所...
  • 结果尾数中零数量。 示例 1: 输入: 3 输出: 0 解释:3! = 6, 尾数中没有零。 示例2: 输入: 5 输出: 1 解释:5! = 120, 尾数中有 1 个零. int trailingZeroes(int n) { int num = 0; if(n < 5) { ...
  • 题目:原地址 Given an integer n, return the number of trailing zeroes in n!...思路:只有2和5相乘才会出现0,其中整十也可以看做是2和5相乘结果,所以,可以在n之前看看有多少个2以及多少个5就行了。
  • 声明: 今天是第40道题。给定一个整数 n,返回 n! 结果尾数中零数量。以下所有代码经过楼主验证都能在LeetCode上执行成功,代码也是借鉴别人,在文末会附上参考博客链接,...输出: 0 解释: 3! = 6, 尾数...
  • 题目描述 给定一个整数 n,返回 n! 结果尾数中零数量。 示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。...出现0的时候,因子里面一定会含有2和5,2出现次数非常多,所以决定出现几个0的关键...
  • 链接:... 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld ...这个问题很简单,就是问你n的阶乘末尾有几个0? 输入描述: 输入第一...
  • 思路:这道题有点挑战,开始只知道因子2比...随后发现题解中一个通俗易懂帖子,借以参考: int trailingZeroes(int n) { int res = 0; while (n > 0) { res += n / 5; n /= 5; } return res; } ...
  • 给定由若干 0 和 1 组成数组 A。我们定义 N_i:从 A[0] 到 A[i] 第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。 返回布尔值列表 answer,只有当 N_i 可以被 5 整除时,答案 answer[i] 为 ...
  • 阶乘后面0的数量

    2019-08-02 15:45:20
    1003 阶乘后面0的数量 n的阶乘后面有多少个0? 6的阶乘 = 1*2*3*4*5*6 = 720,720后面有1个0。 收起 输入 一个数N(1 <= N <= 10^9) 输出 输出0的数量 输入样例 5 输出样例 1 有思路了,这个题...
  • 阶乘后的

    2020-10-25 20:24:15
    题目: 给定一个整数 n,返回 n!...* 题目:阶乘后的0 * 算法:1、首先用递归算出n的阶乘 * 2、让n!对10取余,就能得到个位上的数字,然后判断 * 3、n!对10取模,舍弃个位的数 */ int factorial(int n) {

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,291
精华内容 516
关键字:

阶乘后的0