Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc647f98

Browse files
committed
添加LeetCode第 172 号问题：阶乘后的零
1 parentdd61e03 commitc647f98

File tree

2 files changed

+116
-35
lines changed

2 files changed

+116
-35
lines changed

‎Readme.md‎

Lines changed: 38 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -15,58 +15,61 @@
1515
| 序号| 题目&题解|
1616
| ----| ------------------------------------------------------------|
1717
| 0|[十大经典排序算法动画与解析，看我就够了！（配代码完全版）](https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg)|
18-
| 1|[两数之和](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第1号问题：两数之和.md)|
19-
| 2|[两数相加](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第2号问题：两数相加.md)|
18+
| 1|[两数之和](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第1号问题：两数之和.md)|
19+
| 2|[两数相加](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第2号问题：两数相加.md)|
2020
| 3|[无重复字符的最长子串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第3号问题：无重复字符的最长子串.md)|
21-
| 15|[三数之和](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第15号问题：三数之和.md)|
21+
| 15|[三数之和](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第15号问题：三数之和.md)|
2222
| 19|[删除链表的倒数第 N 个节点](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第19号问题：删除链表的倒数第N个节点.md)|
23-
| 20|[有效的括号](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第20号问题：有效的括号.md)|
24-
| 21|[合并两个有序链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第21号问题：合并两个有序链表.md)|
23+
| 20|[有效的括号](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第20号问题：有效的括号.md)|
24+
| 21|[合并两个有序链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第21号问题：合并两个有序链表.md)|
2525
| 23|[合并 K 个排序链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第23号问题：合并K个排序链表.md)|
2626
| 24|[两两交换链表中的节点](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第24号问题：两两交换链表中的节点.md)|
2727
| 26|[删除排序数组中的重复项](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第26号问题：删除排序数组中的重复项.md)|
28-
| 75|[颜色分类](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第75号问题：颜色分类.md)|
29-
| 86|[分割链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第86号问题：分割链表.md)|
30-
| 92|[反转链表 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第92号问题：反转链表II.md)|
31-
| 94|[二叉树的中序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第94号问题：二叉树的中序遍历.md)|
32-
| 101|[对称二叉树](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第101号问题：对称二叉树.md)|
28+
| 75|[颜色分类](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第75号问题：颜色分类.md)|
29+
| 86|[分割链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第86号问题：分割链表.md)|
30+
| 92|[反转链表 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第92号问题：反转链表II.md)|
31+
| 94|[二叉树的中序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第94号问题：二叉树的中序遍历.md)|
32+
| 101|[对称二叉树](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第101号问题：对称二叉树.md)|
3333
| 102|[二叉树的层序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第102号问题：二叉树的层序遍历.md)|
3434
| 103|[二叉树的锯齿形层次遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第103号问题：二叉树的锯齿形层次遍历.md)|
3535
| 107|[二叉树的层次遍历 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第107号问题：二叉树的层次遍历II.md)|
36-
| 110|[平衡二叉树](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第110号问题：平衡二叉树.md)|
37-
| 125|[验证回文串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第125号问题：验证回文串.md)|
38-
| 131|[分割回文串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第131号问题：分割回文串.md)|
36+
| 110|[平衡二叉树](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第110号问题：平衡二叉树.md)|
37+
| 125|[验证回文串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第125号问题：验证回文串.md)|
38+
| 131|[分割回文串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第131号问题：分割回文串.md)|
3939
| 136|[只出现一次的数字](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第136号问题：只出现一次的数字.md)|
40-
| 138|[复制带随机指针](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第138号问题：复制带随机指针.md)|
41-
| 139|[单词拆分](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第139号问题：单词拆分.md)|
40+
| 138|[复制带随机指针](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第138号问题：复制带随机指针.md)|
41+
| 139|[单词拆分](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第139号问题：单词拆分.md)|
4242
| 144|[二叉树的前序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第144号问题：二叉树的前序遍历.md)|
4343
| 145|[二叉树的后序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第145号问题：二叉树的后序遍历.md)|
44-
| 146|[LRU缓存机制](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第146号问题：LRU缓存机制.md)|
44+
| 146|[LRU缓存机制](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第146号问题：LRU缓存机制.md)|
4545
| 150|[逆波兰表达式求值](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第150号问题：逆波兰表达式求值.md)|
4646
| 167|[两数之和 II - 输入有序数组](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第167号问题：两数之和II-输入有序数组.md)|
47-
| 187|[重复的 DNA 序列](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第187号问题：重复的DNA序列.md)|
48-
| 199|[二叉树的右视图](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第199号问题：二叉树的右视图.md)|
49-
| 203|[移除链表元素](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第203号问题：移除链表元素.md)|
50-
| 206|[反转链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第206号问题：反转链表.md)|
47+
| 172|[阶乘后的零](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第172号问题：阶乘后的零.md)|
48+
| 187|[重复的 DNA 序列](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第187号问题：重复的DNA序列.md)|
49+
| 199|[二叉树的右视图](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第199号问题：二叉树的右视图.md)|
50+
| 203|[移除链表元素](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第203号问题：移除链表元素.md)|
51+
| 206|[反转链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第206号问题：反转链表.md)|
5152
| 209|[长度最小的子数组](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第209号问题：长度最小的子数组.md)|
52-
| 219|[存在重复元素 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第219号问题：存在重复元素II.md)|
53+
| 219|[存在重复元素 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第219号问题：存在重复元素II.md)|
5354
| 237|[删除链表中的节点](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第237号问题：删除链表中的节点.md)|
54-
| 239|[滑动窗口最大值](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第239号问题：滑动窗口最大值.md)|
55-
| 279|[完全平方数](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第279号问题：完全平方数.md)|
56-
| 283|[移动零](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第283号问题：移动零.md)|
57-
| 295|[数据流的中位数](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第295号问题：数据流的中位数.md)|
58-
| 301|[删除无效的括号](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第301号问题：删除无效的括号.md)|
59-
| 326|[3 的幂](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第326号问题：3的幂.md)|
60-
| 328|[奇偶链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第328号问题：奇偶链表.md)|
61-
| 344|[反转字符串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第344号问题：反转字符串.md)|
62-
| 349|[两个数组的交集](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第349号问题：两个数组的交集.md)|
55+
| 239|[滑动窗口最大值](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第239号问题：滑动窗口最大值.md)|
56+
| 279|[完全平方数](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第279号问题：完全平方数.md)|
57+
| 283|[移动零](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第283号问题：移动零.md)|
58+
| 295|[数据流的中位数](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第295号问题：数据流的中位数.md)|
59+
| 301|[删除无效的括号](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第301号问题：删除无效的括号.md)|
60+
| 326|[3 的幂](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第326号问题：3的幂.md)|
61+
| 328|[奇偶链表](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第328号问题：奇偶链表.md)|
62+
| 344|[反转字符串](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第344号问题：反转字符串.md)|
63+
| 349|[两个数组的交集](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第349号问题：两个数组的交集.md)|
6364
| 350|[两个数组的交集 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第350号问题：两个数组的交集II.md)|
64-
| 445|[两数相加 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第445号问题：两数相加II.md)|
65-
| 447|[回旋镖的数量](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第447号问题：回旋镖的数量.md)|
66-
| 454|[四数相加 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第454号问题：四数相加II.md)|
65+
| 445|[两数相加 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第445号问题：两数相加II.md)|
66+
| 447|[回旋镖的数量](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第447号问题：回旋镖的数量.md)|
67+
| 454|[四数相加 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第454号问题：四数相加II.md)|
6768
| 642|[设计一个搜索自动完成系统](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第642号问题：设计一个搜索自动完成系统.md)|
68-
| 690|[员工的重要性](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第690号问题：员工的重要性.md)|
69-
| 877|[石子游戏](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第877号问题：石子游戏.md)|
69+
| 690|[员工的重要性](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第690号问题：员工的重要性.md)|
70+
| 877|[石子游戏](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第877号问题：石子游戏.md)|
71+
72+
7073

7174
##补充
7275
该仓库保持随时更新。
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#LeetCode第 172 号问题：阶乘后的零
2+
3+
>本文首发于公众号「五分钟学算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
>个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 172 号问题：阶乘后的零。题目难度为 Easy，目前通过率为 38.0% 。
8+
9+
###题目描述
10+
11+
给定一个整数*n*，返回*n*! 结果尾数中零的数量。
12+
13+
**示例 1:**
14+
15+
```
16+
输入: 3
17+
输出: 0
18+
解释: 3! = 6, 尾数中没有零。
19+
```
20+
21+
**示例 2:**
22+
23+
```
24+
输入: 5
25+
输出: 1
26+
解释: 5! = 120, 尾数中有 1 个零.
27+
```
28+
29+
**说明:** 你算法的时间复杂度应为*O*(log*n*) 。
30+
31+
###题目解析
32+
33+
题目很好理解，数阶乘后的数字末尾有多少个零。
34+
35+
最简单粗暴的方法就是先乘完再说，然后一个一个数。
36+
37+
事实上，你在使用暴力破解法的过程中就能发现规律：**这 9 个数字中只有 2（它的倍数） 与 5 （它的倍数）相乘才有 0 出现**。
38+
39+
所以，现在问题就变成了这个阶乘数中能配**多少对 2 与 5**。
40+
41+
举个复杂点的例子：
42+
43+
` 10！ = 【 2 *（ 2 * 2 ）* 5 *（ 2 * 3 ）*（ 2 * 2 * 2 ）*（ 2 * 5）】`
44+
45+
在 10！这个阶乘数中可以匹配两对 2 * 5 ，所以10！末尾有 2 个 0。
46+
47+
可以发现，一个数字进行拆分后 2 的个数肯定是大于 5 的个数的，所以能匹配多少对取决于 5 的个数。（好比现在男女比例悬殊，最多能有多少对异性情侣取决于女生的多少）。
48+
49+
那么问题又变成了**统计阶乘数里有多少个 5 这个因子**。
50+
51+
需要注意的是，像 25，125 这样的不只含有一个 5 的数字的情况需要考虑进去。
52+
53+
比如`n = 15`。那么在`15!` 中 有`3` 个`5` (来自其中的`5`,`10`,`15`)， 所以计算`n/5` 就可以 。
54+
55+
但是比如`n=25`，依旧计算`n/5` ，可以得到`5` 个`5`，分别来自其中的`5, 10, 15, 20, 25`，但是在`25` 中其实是包含`2`个`5` 的，这一点需要注意。
56+
57+
所以除了计算`n/5` ， 还要计算`n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5`直到商为0，然后求和即可。
58+
59+
###代码实现
60+
61+
```java
62+
publicclassSolution {
63+
publicinttrailingZeroes(intn) {
64+
return n==0?0: n/5+ trailingZeroes(n/5);
65+
}
66+
}
67+
```
68+
69+
70+
71+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)
72+
73+
74+
75+
76+
77+
78+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp