leetcode-172. 阶乘后的零
2022/8/28 23:27:54
本文主要是介绍leetcode-172. 阶乘后的零,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
172. 阶乘后的零
图床:blogimg/刷题记录/leetcode/172/
刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html
题目
思路
n!
中有几个0
与[1,n]
中出现多少个5的因数有关。例如7! = 1×2×3×4×5×6×7
出现了1次5,故最后末尾会出现1个0。26!
中出现了5,10,15,20,25
其中5的个数为1+1+1+1+2=6
,故最后末尾会出现6个0。
解法
class Solution { public: int cal(int k){ if(k==0) return 0; else if(k%5==0){ return cal(k/5)+1; } return 0; } int trailingZeroes(int n) { int count = 0; for (int i = 0;i<n+1;i+=5){ count += cal(i); } return count; } };
- 时间复杂度:\(O(n)\),其中\(n\)为数组\(nums\)的长度,需要遍历一遍数组
- 空间复杂度:\(O(1)\),仅使用常量空间
补充
所以可知:
\(ans = n/5+n/5^2+n/5^3+\cdots\)
class Solution { public: int trailingZeroes(int n) { int ans = 0; while (n) { n /= 5; ans += n; } return ans; } };
复杂度:
- 时间复杂度:\(O(log\,n)\)
- 空间复杂度:\(O(1)\)
这篇关于leetcode-172. 阶乘后的零的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享