当前位置：首页 > ops >正文

力扣经典算法篇-46-阶乘后的零(正向步长遍历，逆向步长遍历）

ops 2025/8/13 19:58:18

1、题干

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：
输入：n = 0
输出：0

提示：
0 <= n <= 10^4

2、解题

题目要求对n的阶乘结果，校验末尾0的个数。
首先题目给定了n的范围在0-10000之间。我们一定不能上来计算阶乘和，因为在Java中int的最大值是2147483647即2的31次方-1，最多能计算12的阶乘；long的范围是9223372036854775807（2^63-1），最大只能计算到20的阶乘，很显然求阶乘和的方式不可取。

只能根据数字的特征去求解
第一种情况，如果末尾是0，那就末尾0的个数就加1，但是要注意100这种末尾有2个0，1000有3个0的情况。
第二种情况，如果能被5整除，那么必然也能早晨末尾为0的情况；但是也要注意25这种55的情况，因为254*2=200,末尾会产生2个0；同理125的这种，末尾会产生3个0。

方法一：（逆向遍历）

从n开始向1进行遍历，在满足条件的情况下计算结果。

代码示例：

public class Test52 {public static int trailingZeroes(int n) {int result = 0;if (n == 0) {return result;}while (n > 4) {   // 至少为5才可能在末尾产生0int temp = n;    boolean flag = false;    // 记录当前元素是否为5或10，这样可以使用5的步长递减，减速遍历，提高效率while (temp % 10 == 0) {   // 要使用while，防止100的情况result++;temp = temp / 10;flag = true;}while (temp % 5 == 0) {      // 使用while防止25会造成末尾2个0的情况result++;temp = temp / 5;flag = true;}if (flag) {   // 本次为10或者5，指定5的步长递减n = n - 5;} else {n--;}}return result;}public static void main(String[] args) {int n = 30;System.out.println(trailingZeroes(n));}
}

方法一：（正向遍历）

从5到n正向遍历，在满足不超过n的条件下计算结果。

代码示例：

public int trailingZeroes(int n) {int ans = 0;for (int i = 5; i <= n; i += 5) {       // 指定初始5开始，每次增加5，且计算值不能超过nfor (int x = i; x % 5 == 0; x /= 5) {    // 防止100或25这种情况++ans;}}return ans;}