广州优秀网站设计,瑞安网站建设优化推广,微商城运营的主要工作,怎么用电脑做网站服务器吗这是悦乐书的第183次更新#xff0c;第185篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第42题#xff08;顺位题号是172#xff09;。给定一个整数n#xff0c;返回n#xff01;中的尾随零数。例如#xff1a; 输入#xff1a;3 输出#xff1a;0 说明…这是悦乐书的第183次更新第185篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第42题顺位题号是172。给定一个整数n返回n中的尾随零数。例如 输入3 输出0 说明3 6没有尾随零。 输入5 输出1 说明5 120一个尾随零。 本次解题使用的开发工具是eclipsejdk使用的版本是1.8环境是win7 64位系统使用Java语言编写和测试。 02 第一种解法 特殊情况当n小于等于0的时候直接返回0。 先把n的阶乘算出来再转为字符串接着从字符串的最后一位往前遍历找0出现的次数没有碰到0就就结束循环。为了避免计算阶乘溢出使用BigInteger来做计算借助其multiply方法。 public int trailingZeroes(int n) {int result 0;if (n 0) {return result;}BigInteger num new BigInteger(1);for (long i1; i n; i) {num num.multiply(new BigInteger(i));}String str num ;if (str.lastIndexOf(0) ! -1) {for (int j str.length(); j 0; j--) {if (0.equals(str.substring(j-1, j))) {result;} else {break;}}}return result;
} 此解法是一种思路但是不推荐这么做时间复杂度是O(n)空间复杂度是0(n)。 03 第二种解法 要判断n做完阶乘后的整数带几个0可以反过来思考尾数0可以由那些数相乘得到0可以由10的倍数来得到但是n的阶乘我们不能单独判断10出现的次数还要继续分解10是2乘以5的结果任意一个正整数的阶乘2出现的次数肯定多于5出现的次数那就计算5出现的次数到此是否就完了还没有因为有些数字自身就是带5的比如25,125之类的最后可以归纳成f(n)n/5 f(n/5)可以使用递归也可以使用循环结构。 这是递归的解法。 public int trailingZeroes2(int n) {if (n5) return 0;if (n10) return 1;return n/5 trailingZeroes2(n/5);
} 这是使用循环结构的解法。 public int trailingZeroes3(int n) {int result 0;while (n0) {result n/5;n / 5;}return result;
} 还有更加疯狂的一行代码搞定。 public int trailingZeroes4(int n) {return n 0 ? 0 : n/5 trailingZeroes4(n/5);
} 04 小结 算法专题目前已连续日更超过一个月算法题文章42篇公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词获取系列文章合集。 以上就是全部内容如果大家有什么好的解法思路、建议或者其他问题可以下方留言交流点赞、留言、转发就是对我最大的回报和支持 转载于:https://www.cnblogs.com/xiaochuan94/p/10018410.html
