leetcode
leetcode 1851 ~ 1900
一个区间内所有数乘积的缩写

一个区间内所有数乘积的缩写

难度:

标签:

题目描述

代码结果

运行时间: 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并保持数值在一个较小的范围内(使用MOD进行取模)。这是为了精确地计算出后缀的5位数字和0的数量。第二次遍历则是为了获取足够大的前缀数字,尽可能保持高位的信息以便于截取前5位。虽然理论上可以在一次遍历中同时更新前缀和后缀,但这样做可能需要在每一步都进行复杂的判断和调整,以保持数字大小适中并同时保留必要的高位和低位信息,这可能会增加算法的复杂性和执行时间。因此,采用两次遍历的方法可以更清晰地分别处理并优化这两部分的精度和性能。
🦆
在移除乘积中的后缀0时,你是如何确保计算精度的?是否有可能在去除大量0后,结果的低位出现错误?
在移除乘积中的后缀0时,每当乘积可以被10整除,即末尾为0时,通过除以10来移除这个0,并记录0的数量。这种方法确保了每次操作都是精确的,因为整数除法在这里是精确的操作,不会引入任何浮点数运算的误差。去除0的操作只影响数值的尾部,不会改变其它位的值,因此不会在去除大量0后使结果的低位出现错误。只要正确记录了0的数量,并保持其它位的正确计算,就能确保整体计算的精度。
🦆
题解中提到使用了MOD来防止溢出,MOD的大小选择为10^16有何依据,是否有可能因为MOD选取不合适而导致计算错误?
在这种情况下,MOD的大小选择为10^16主要是基于两个考虑:一是确保在计算过程中的数字大小可控,避免因整数溢出导致计算错误;二是保证足够的数字精度来获取必要的前5位和后5位。选择10^16是因为它足够大,可以在绝大多数情况下保持计算的精确性,同时又不至于过大导致处理速度过慢。如果MOD设置得太小,可能无法保留足够的数字位数,导致计算结果不精确;设置得太大,则可能导致数字处理过程中的性能问题。因此,10^16是一个在保证性能和精度之间权衡的合适选择。不过,确实存在极端情况下可能因MOD选取不当导致计算错误,这需要根据具体问题的数据范围和需求来调整MOD的大小。

相关问题