C++基于字符串实现大数相乘问题的代码详解

一、问题描述

在实际编程中，我们经常会遇到需要处理大整数的情况。由于编程语言中内置整数类型（如int、long等）有其表示范围的限制，当需要处理的整数超出这些范围时，就不能直接使用内置类型进行计算。
一般的解决方式是以两个以字符串形式表示的非负整数num1和num2的乘法，并将结果也以字符串形式返回。

输入限制

• 1 <= num1.length, num2.length <= 200
• num1和num2只能由数字组成。
• num1和num2都不包含任何前导零，除了数字0本身。

二、解题思路

要解决这个问题，我们可以模拟手工乘法的过程。在手工乘法中，我们将一个数的每一位与另一个数的每一位相乘，然后将结果相加，并处理进位。具体步骤如下：

1. 特殊情况处理：如果num1或num2为"0"，则直接返回"0"。
2. 反转字符串：为了方便从低位到高位进行计算，我们将num1和num2反转。
3. 初始化结果数组：创建一个长度为num1.size() + num2.size()的数组ret，用于存储中间结果。因为两个数相乘的结果位数不会超过这两个数的位数之和。
4. 逐位相乘：使用两层循环，将num1的每一位与num2的每一位相乘，并将结果累加到ret数组的相应位置。
5. 处理进位：遍历ret数组，将每一位的进位加到下一位。
6. 去除前导零：由于结果数组可能存在前导零，我们需要将其去除。
7. 转换为字符串：将处理好的结果数组转换为字符串。

三、代码实现

#include <string>
#include <algorithm>
class Solution {
public:
string multiply(string num1, string num2)
{
// 先判断是否有一个为0
if(num1 == "0" || num2 == "0")
return "0";
// 反转两个字符串方便操作
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// 结果位数不超过两个字符串之和
int size = num1.size() + num2.size();
// 创建存储结果的数组并初始化为0
int* ret = new int[size]();
// 字符串相乘，不考虑进位
for(int i = 0; i < num1.size(); ++i)
{
for(int j = 0; j < num2.size(); ++j)
{
ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}
// 处理进位
for(int i = 0; i < size - 1; ++i)
{
ret[i + 1] += ret[i] / 10;
ret[i] = ret[i] % 10;
}
// 去除前导零
int i = size - 1;
while( (ret[i] == 0) && (size > 1) )
{
--size;
--i;
}
// 转字符串
string s = "";
s.reserve(size);
for(int i = size - 1; i >= 0; --i)
{
s += ('0' + ret[i]);
}
// 释放动态分配的内存
delete[] ret;
return s;
}
};

四、代码详细分析

1. 特殊情况处理

if(num1 == "0" || num2 == "0")
return "0";

如果num1或num2为"0"，则它们的乘积一定为"0"，直接返回即可。

2. 反转字符串

reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());

使用std::reverse函数将num1和num2反转，这样在后续计算中可以从低位（字符串的起始位置）开始处理。

3. 初始化结果数组

int size = num1.size() + num2.size();
int* ret = new int[size]();

建一个长度为num1.size() + num2.size()的整数数组ret，并使用()进行值初始化，将数组元素都初始化为 0。

4. 逐位相乘

for(int i = 0; i < num1.size(); ++i)
{
for(int j = 0; j < num2.size(); ++j)
{
ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}

使用两层嵌套循环，将num1的每一位与num2的每一位相乘，并将结果累加到ret数组的相应位置。(num1[i] - '0')和(num2[j] - '0')是将字符转换为对应的数字。

5. 处理进位

for(int i = 0; i < size - 1; ++i)
{
ret[i + 1] += ret[i] / 10;
ret[i] = ret[i] % 10;
}

遍历ret数组，将每一位的进位（ret[i] / 10）加到下一位，同时将当前位取模 10 得到该位的最终结果。

6. 去除前导零

int i = size - 1;
while( (ret[i] == 0) && (size > 1) )
{
--size;
--i;
}

从结果数组的最高位开始检查，如果该位为 0 且结果长度大于 1，则将长度减 1，继续检查前一位。

7. 转换为字符串

string s = "";
s.reserve(size);
for(int i = size - 1; i >= 0; --i)
{
s += ('0' + ret[i]);
}

创建一个空字符串s，并使用reserve方法预先分配足够的空间。然后从结果数组的最高位开始，将每一位转换为字符并添加到字符串s中。

8. 释放内存

delete[] ret;

由于ret是动态分配的数组，使用完后需要使用delete[]释放内存，避免内存泄漏。

五、复杂度分析

• 时间复杂度：O ( m ∗ n )，其中m mm和n nn分别是num1和num2的长度。主要时间开销在于两层嵌套的循环进行逐位相乘。
• 空间复杂度：O ( m + n )，主要空间开销在于存储中间结果的数组ret。

通过以上步骤，我们就可以实现两个大整数的乘法，并将结果以字符串形式返回。这种方法模拟了手工乘法的过程，避免了使用内置的大整数库和直接将输入转换为整数，适用于处理超出内置整数类型表示范围的大整数乘法问题。

以上就是C++基于字符串实现大数相乘问题的代码详解的详细内容，更多关于C++字符串实现大数相乘的资料请关注本站其它相关文章！