一、问题描述在实际编程中我们经常会遇到需要处理大整数的情况。由于编程语言中内置整数类型如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数组将每一位的进位加到下一位。去除前导零由于结果数组可能存在前导零我们需要将其去除。转换为字符串将处理好的结果数组转换为字符串。三、代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include string#include algorithmclassSolution {public:string multiply(string num1, string num2){// 先判断是否有一个为0if(num1 0|| num2 0)return0;// 反转两个字符串方便操作reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());// 结果位数不超过两个字符串之和intsize num1.size() num2.size();// 创建存储结果的数组并初始化为0int* ret newint[size]();// 字符串相乘不考虑进位for(inti 0; i num1.size(); i){for(intj 0; j num2.size(); j){ret[i j] (num1[i] -0) * (num2[j] -0);}}// 处理进位for(inti 0; i size - 1; i){ret[i 1] ret[i] / 10;ret[i] ret[i] % 10;}// 去除前导零inti size - 1;while( (ret[i] 0) (size 1) ){--size;--i;}// 转字符串string s ;s.reserve(size);for(inti size - 1; i 0; --i){s (0 ret[i]);}// 释放动态分配的内存delete[] ret;returns;}};四、代码详细分析1. 特殊情况处理12if(num1 0|| num2 0)return0;如果num1或num2为0则它们的乘积一定为0直接返回即可。2. 反转字符串12reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());使用std::reverse函数将num1和num2反转这样在后续计算中可以从低位字符串的起始位置开始处理。3. 初始化结果数组12intsize num1.size() num2.size();int* ret newint[size]();建一个长度为num1.size() num2.size()的整数数组ret并使用()进行值初始化将数组元素都初始化为 0。4. 逐位相乘1234567for(inti 0; i num1.size(); i){for(intj 0; j num2.size(); j){ret[i j] (num1[i] -0) * (num2[j] -0);}}使用两层嵌套循环将num1的每一位与num2的每一位相乘并将结果累加到ret数组的相应位置。(num1[i] - 0)和(num2[j] - 0)是将字符转换为对应的数字。5. 处理进位12345for(inti 0; i size - 1; i){ret[i 1] ret[i] / 10;ret[i] ret[i] % 10;}遍历ret数组将每一位的进位ret[i] / 10加到下一位同时将当前位取模 10 得到该位的最终结果。6. 去除前导零123456inti size - 1;while( (ret[i] 0) (size 1) ){--size;--i;}从结果数组的最高位开始检查如果该位为 0 且结果长度大于 1则将长度减 1继续检查前一位。7. 转换为字符串123456string s ;s.reserve(size);for(inti size - 1; i 0; --i){s (0 ret[i]);}创建一个空字符串s并使用reserve方法预先分配足够的空间。然后从结果数组的最高位开始将每一位转换为字符并添加到字符串s中。8. 释放内存1delete[] ret;由于ret是动态分配的数组使用完后需要使用delete[]释放内存避免内存泄漏。五、复杂度分析时间复杂度O ( m ∗ n )其中 m mm 和 n nn 分别是num1和num2的长度。主要时间开销在于两层嵌套的循环进行逐位相乘。空间复杂度O ( m n )主要空间开销在于存储中间结果的数组ret。