当前位置: 首页> 文旅> 旅游 > leetcode 43. 字符串相乘

leetcode 43. 字符串相乘

时间:2025/7/9 6:04:23来源:https://blog.csdn.net/smallplum123/article/details/139578611 浏览次数:0次

题目

给定两个以字符串形式表示的非负整数 num1num2,返回 num1num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

原题链接:https://leetcode.cn/problems/multiply-strings/description/

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”

思路

把乘法的过程,进行拆解。
如 123 x 456,拆成 123 x 6 x 10 ^0 + 123 x 5 x 10^1 + 123 x 4 x 10^2。
这里除了处理乘法项的相乘过程之外,还要处理每一个乘法项的相加过程。
即包括 相乘过程相加过程
为了避免溢出,这里每一个过程都得处理成字符串的形式。

  • 复杂度分析
    • 时间复杂度 O(mn)。乘法部分两个for循环是 m * n。
    • 空间复杂度 O(m+n)。空间复杂度取决于两个数字的长度。

代码

class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") return "0";string result = "0";int n = num2.size(), m = num1.size();for (int i = n - 1; i >= 0; i--) {string cur;int add = 0;int y = num2[i] - '0';for (int j = m - 1; j >= 0; j--) {int x = num1[j] - '0';int res = x * y + add;char temp = res % 10 + '0';cur = temp + cur;add = res / 10;}if (add > 0) {char temp = add + '0';cur = temp + cur;}for (int k = n - i - 1; k > 0; k--) {cur = cur + '0';}result = add_string(result, cur);}return result;}string add_string(string& num1, string& num2) {int i = num1.size() - 1;int j = num2. size() - 1;int add = 0;string result = "";while (i >= 0 || j >= 0 || add > 0) {int x = i >= 0 ? num1[i] - '0' : 0;int y = j >= 0 ? num2[j] - '0' : 0;int res = x + y + add;char temp = res % 10 + '0';result = temp + result;add = res / 10;i--;j--;}return result;}
};
关键字:leetcode 43. 字符串相乘

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: