2

算法 | 数学规律专题

 1 year ago
source link: https://jianengli.github.io/2021/02/03/algorithm_summerization/math/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Jianeng

算法 | 数学规律专题

Created2021-02-03|Updated2021-02-05|算法专题
Word count:353|Reading time:1min|Post View:6

1. lc 172 - 阶乘后的零

  • 题目来源
  • 给定一个整数 n,返回 n! 结果尾数中零的数量。
  • 难度:简单

1.1 解题思路

分析: 首先末尾有多少个 0 ,只需要给当前数乘以一个 10 就可以加一个 0。

再具体对于 5!,也就是 5 * 4 * 3 * 2 * 1 = 120,我们发现结果会有一个 0,原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话,其实也只有 2 * 5 可以构成,所以我们只需要找有多少对 2/5。

含有 2 的因子每两个出现一次,含有 5 的因子每 5 个出现一次,所有 2 出现的个数远远多于 5,换言之找到一个 5,一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的,我们只需要判断每个累乘的数有多少个 5 的因子即可[1]。

总结: 有多少个5就有多少个0。

1.2 复杂度分析

  • 时间复杂度:O(logn)。在这种方法中,我们遍历了5的每个幂直到 n。
  • 空间复杂度:O(1)。

1.3 代码

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

[1] windliang. 详细通俗的思路分析. https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK