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

算法练习6-大数乘法（高精度乘法）

news 2025/7/13 13:44:12

大数乘法

1. 题目描述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

数据范围：读入的数字大小满足 0≤n≤1010000≤n≤101000

要求：空间复杂度 O(m)O(m)，时间复杂度 O(m2)O(m2)（假设m是n的长度）

示例：
输入: "11", "99"
输出: "1089"输入: "1", "0"
输出: "0"

2. 解题思路

根据列竖式运算的过程模拟即可。具体步骤如下：

1. 反转字符串：将输入的两个字符串反转，以便从低位到高位进行逐位相乘。
2. 无进位相乘相加：创建一个数组 tmp 来存储每一位相乘的结果。对于每个字符，将其转换为对应的整数值，并进行相乘操作，结果存入 tmp 数组中对应的位置。
3. 处理进位：遍历 tmp 数组，处理每一位的进位，确保每一位的值在 0 到 9 之间。
4. 构建结果字符串：将处理后的 tmp 数组中的值依次添加到 StringBuilder 中，形成最终的结果字符串。
5. 删除前导零：检查并删除结果字符串中的前导零，如果结果为空，则返回 "0"。

3. 代码实现


import java.util.*;public class Solution {public String solve(String ss, String tt) {// 将输入字符串 ss 和 tt 反转，并转换为字符数组 sArray 和 tArray。// 这样做的目的是为了方便从低位到高位进行逐位相乘。char[] sArray = new StringBuilder(ss).reverse().toString().toCharArray();char[] tArray = new StringBuilder(tt).reverse().toString().toCharArray();// m 和 n 分别是两个输入字符串的长度。int m = sArray.length, n = tArray.length;// tmp 数组用于存储每一位相乘的结果。它的大小是 m + n，// 因为两个数相乘的最大长度不会超过它们各自长度之和。int[] tmp = new int[m + n];// 1. 无进位相乘相加：// 对于 sArray 中的每一个字符和 tArray 中的每一个字符，// 计算它们对应的数字（通过减去 '0' 的ASCII值），并将它们的乘积累加到 tmp 数组中的相应位置。for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {tmp[i + j] += (sArray[i] - '0') * (tArray[j] - '0');}}// 2. 处理进位：// 遍历 tmp 数组，处理每一位的进位问题。// sum 表示当前位的值加上前一位的进位值，然后更新当前位的值为 sum % 10，// 并将新的进位值 c 更新为 sum / 10。int c = 0;for (int i = 0; i < tmp.length; i++) {int sum = tmp[i] + c;tmp[i] = sum % 10;c = sum / 10;}// 将结果添加到 StringBuilder 中：// 创建一个 StringBuilder 对象 ret，用于构建最终的结果字符串。// 注意这里避免了添加不必要的前导零。StringBuilder ret = new StringBuilder();for (int x : tmp) {if (!(ret.length() == 0 && x == 0)) { // 避免添加前导零ret.append(x);}}// 如果在上一步之后仍有未处理的进位，则继续添加到结果中。while (c > 0) { // 处理最后的进位ret.append(c % 10);c /= 10;}// 3. 处理前导零：// 删除结果字符串中的前导零。如果删除后结果为空，则返回 "0"。while (ret.length() > 0 && ret.charAt(0) == '0') {ret.deleteCharAt(0);}// 返回反转后的结果字符串。因为我们在开始时反转了输入字符串，// 所以现在需要再次反转来获得正确的顺序。return ret.length() == 0 ? "0" : ret.reverse().toString();}
}