一个区间内所有数乘积的缩写
难度:
标签:
题目描述
代码结果
运行时间: 435 ms, 内存: 16.0 MB
/*
* 题目思路:
* 1. 使用 Java Stream 计算乘积。
* 2. 统计乘积末尾的 0 的个数,并将这些 0 移除。
* 3. 如果移除 0 后的数字长度超过 10,则只保留前5位和后5位。
* 4. 返回格式为 "<pre>...<suf>eC",其中 C 是末尾 0 的个数。
*/
import java.util.stream.IntStream;
public class ProductAbbreviationStream {
public String abbreviateProduct(int left, int right) {
long[] product = new long[]{1};
int[] zeroCount = new int[]{0};
boolean[] hasExceeded = new boolean[]{false};
long mod = (long)1e10;
long[] firstFive = new long[]{1};
long[] lastFive = new long[]{1};
IntStream.rangeClosed(left, right).forEach(i -> {
product[0] *= i;
while (product[0] % 10 == 0) {
product[0] /= 10;
zeroCount[0]++;
}
if (product[0] >= mod) {
hasExceeded[0] = true;
firstFive[0] = product[0];
product[0] %= mod;
lastFive[0] = product[0];
}
});
String result = hasExceeded[0] ? firstFive[0] + "..." + lastFive[0] : String.valueOf(product[0]);
result += "e" + zeroCount[0];
return result;
}
}
解释
方法:
本题解思路主要分为两部分:首先,计算区间 [left, right] 内所有整数的乘积,并移除乘积中的所有后缀0,同时计算这些0的数量。其次,根据乘积的大小来决定如何缩写这个数字。如果乘积的有效位数(不含后缀0)超过10位,则只显示前5位和后5位,并用省略号连接;如果不超过10位,则直接显示。最终输出字符串格式为 '
...eC'。为了防止在乘积计算过程中发生溢出,使用了模运算来保持数字在可控范围内。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择两次遍历区间 [left, right] 来分别计算前缀和后缀,一次遍历是否能同时完成这两个计算?
▷🦆
在移除乘积中的后缀0时,你是如何确保计算精度的?是否有可能在去除大量0后,结果的低位出现错误?
▷🦆
题解中提到使用了MOD来防止溢出,MOD的大小选择为10^16有何依据,是否有可能因为MOD选取不合适而导致计算错误?
▷