LeetCode题解172.factorial-trailing-zeroes

题目地址

https://leetcode.com/problems/factorial-trailing-zeroes/description/

题目描述

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.

思路

我们需要求解这n个数字相乘的结果末尾有多少个0,由于题目要求log的复杂度,因此暴力求解是不行的。

通过观察,我们发现如果想要结果末尾是0,必须是分解质因数之后,2 和 5 相乘才行,同时因数分解之后发现5的个数远小于2,
因此我们只需要求解这n数字分解质因数之后一共有多少个5即可.

LeetCode题解172.factorial-trailing-zeroes

如图如果n为30,那么结果应该是图中红色5的个数,即7。

LeetCode题解172.factorial-trailing-zeroes

我们的结果并不是直接f(n) = n / 5, 比如n为30, 25中是有两个5的。
类似,n为150,会有7个这样的数字,通过观察我们发现规律f(n) = n/5 + n/5^2 + n/5^3 + n/5^4 + n/5^5+..

LeetCode题解172.factorial-trailing-zeroes

如果可以发现上面的规律,用递归还是循环实现这个算式就看你的了。

关键点解析

  • 数论

代码

  • 语言支持:JS,Python

Javascript Code:

/*
 * @lc app=leetcode id=172 lang=javascript
 *
 * [172] Factorial Trailing Zeroes
 */
/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
  // tag: 数论

  // if (n === 0) return n;

  // 递归: f(n) = n / 5 + f(n / 5)
  // return Math.floor(n / 5)  + trailingZeroes(Math.floor(n / 5));
  let count = 0;
  while (n >= 5) {
    count += Math.floor(n / 5);
    n = Math.floor(n / 5);
  }
  return count;
};

Python Code:

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n >= 5:
            n = n // 5
            count += n
        return count


# 递归
class Solution:
    def trailingZeroes(self, n: int) -> int:
        if n == 0: return 0
        return n // 5 + self.trailingZeroes(n // 5)
LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…

LeetCode题解砝码的最小数量

假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…

LeetCode题解93. 复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…

LeetCode题解886. 可能的二分法

给定一组 N 人(编号为 1, 2, ..., N), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 a 和 b 的人归入同一组。当可以用这种方法将每个人分进两组时,返回 true;否则返回 false。 示例 1:输入:N = 4, disl…