【C++经典例题】基于字符串实现大数相乘问题
.💓 博客主页：倔强的石头的ZEEKLOG主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《C++指南》
期待您的关注
文章目录
一、问题描述
在实际编程中，我们经常会遇到需要处理大整数的情况。由于编程语言中内置整数类型（如 int、long 等）有其表示范围的限制，当需要处理的整数超出这些范围时，就不能直接使用内置类型进行计算。
一般的解决方式是以两个以字符串形式表示的非负整数 num1 和 num2 的乘法，并将结果也以字符串形式返回。
输入限制
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
二、解题思路
要解决这个问题，我们可以模拟手工乘法的过程。在手工乘法中，我们将一个数的每一位与另一个数的每一位相乘，然后将结果相加，并处理进位。具体步骤如下：
- 特殊情况处理：如果
num1或num2为"0"，则直接返回"0"。 - 反转字符串：为了方便从低位到高位进行计算，我们将
num1和num2反转。 - 初始化结果数组：创建一个长度为
num1.size() + num2.size()的数组ret，用于存储中间结果。因为两个数相乘的结果位数不会超过这两个数的位数之和。 - 逐位相乘：使用两层循环，将
num1的每一位与num2的每一位相乘，并将结果累加到ret数组的相应位置。 - 处理进位：遍历
ret数组，将每一位的进位加到下一位。 - 去除前导零：由于结果数组可能存在前导零，我们需要将其去除。
- 转换为字符串：将处理好的结果数组转换为字符串。
三、代码实现
#include<string>#include<algorithm>classSolution{public: string multiply(string num1, string num2){// 先判断是否有一个为0if(num1 =="0"|| num2 =="0")return"0";// 反转两个字符串方便操作reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());// 结果位数不超过两个字符串之和int size = num1.size()+ num2.size();// 创建存储结果的数组并初始化为0int* ret =newint[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 =newint[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 ) O(m * n) O(m∗n)，其中 m m m 和 n n n 分别是
num1和num2的长度。主要时间开销在于两层嵌套的循环进行逐位相乘。 - 空间复杂度： O ( m + n ) O(m + n) O(m+n)，主要空间开销在于存储中间结果的数组
ret。
通过以上步骤，我们就可以实现两个大整数的乘法，并将结果以字符串形式返回。这种方法模拟了手工乘法的过程，避免了使用内置的大整数库和直接将输入转换为整数，适用于处理超出内置整数类型表示范围的大整数乘法问题。
