数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++字符串乘法
我们有两个由整数组成的字符串，长度最多为200。这两个字符串都不包含任何前导0，但数字本身可以是0。我们需要对整数字符串进行乘法运算，因此需要找到一个解决方案。让我们看看如何更轻松地解决这个问题。
假设我们有两个表示数字的字符串。我们需要将它们相乘并返回结果，结果也以字符串形式表示。例如，如果数字是“26”和“12”，则结果将是“312”。以下是几种在C++中进行字符串乘法的方法。
- 使用内置的`stoll()`方法
- 逐位字符串乘法算法
- 使用Karatsuba乘法算法
使用`stoll()`方法
在本节中，我们将学习如何使用内置方法在C++中将两个字符串相乘。虽然这不是一种高效的方法，因为大型整数可能导致潜在的溢出，但我们仍然介绍这种方法，以便全面了解此方法。
以下是使用`stoll()`在C++中将两个字符串相乘的代码
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string multiply(string num1, string num2) {
long long n1 = stoll(num1);
long long n2 = stoll(num2);
long long res = n1 * n2;
return to_string(res);
}
};
int main() {
Solution sol;
cout << sol.multiply("123", "456") << endl; // Output: 56088
return 0;
}
时间复杂度：O(1)
空间复杂度：O(1)
解释
在这个解决方案中，给定两个字符串num1和num2，我们需要将它们转换为整数。为此，初始化两个long类型的变量n1和n2，分别为它们赋值字符串num1和num2的整数值。然后，将n1和n2的乘法结果存储在一个名为res的long long类型的变量中，并以字符串的形式返回它。
注意：此方法不适用于大型输入
通过相乘每一位
为了解决这个问题，我们将遵循以下步骤
- 初始化结果字符串ans，其长度为m+n，其中m是第一个给定字符串的长度，n是第二个给定字符串的长度，并将值设置为'0'。
- 从右到左遍历num1和num2字符串。对于每个num1数字，将其乘以每个num2数字。
- 将上一步的乘法结果添加到ans的适当位置。
- 调整进位，如果存在进位，则将其添加到字符串中下一个较高的位置。
- 如果存在前导零，则删除字符串中的前导零。
- 最后返回ans字符串。如果ans字符串只包含0，则返回“0”。
下面是一个示例代码，用于解决C++中将两个字符串相乘的问题
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string multiply(string num1, string num2);
};
string Solution::multiply(string nums1, string nums2) {
int n = nums1.size();
int m = nums2.size();
string ans(n + m, '0');
for(int i = n - 1; i >= 0; i--) {
for(int j = m - 1; j >= 0; j--) {
int p = (nums1[i] - '0') * (nums2[j] - '0') + (ans[i + j + 1] - '0');
ans[i+j+1] = p % 10 + '0';
ans[i+j] += p / 10;
}
}
for(int i = 0; i < m + n; i++) {
if(ans[i] !='0') return ans.substr(i);
}
return "0";
}
int main() {
Solution ob;
cout << ob.multiply("28", "25");
return 0;
}
时间复杂度：O(n * m)
空间复杂度：O(n + m)
解释
在这个示例代码中，我们从右到左遍历num1和num2字符串，并将两个字符串的最后一位数字相乘，并将结果存储在ans中，并将进位保存在ans的下一个位置，并将其添加到下一个数字的乘积中。最后，我们返回ans。
Karatsuba乘法算法
为了解决这个问题，我们将遵循以下步骤
- 将给定的数字分成两半。对于
x和y，让x分成x1和x0，y分成y1和y0。 - 使用递归计算三个乘积
A = multiply(x1, y1)B = multiply(x0, y0)C = multiply(x1 + x0, y1 + y0) - A - B
- 使用以下公式组合结果
result = A * 10^2m + C * 10^m + B
- 最后，返回组合的结果。
以下是一个示例 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string multiply(string x, string y);
private:
string karatsuba(string x, string y);
string add(string a, string b);
string sub(string a, string b);
string mulSingle(char x, char y);
};
string Solution::multiply(string x, string y) {
return karatsuba(x, y);
}
string Solution::karatsuba(string x, string y) {
int n = max(x.size(), y.size());
if (n == 0) return "0";
if (n == 1) return mulSingle(x[0], y[0]);
// Ensure both numbers have the same length
while (x.size() < n) x = '0' + x;
while (y.size() < n) y = '0' + y;
int half = n / 2;
string x1 = x.substr(0, half);
string x0 = x.substr(half);
string y1 = y.substr(0, half);
string y0 = y.substr(half);
string A = karatsuba(x1, y1);
string B = karatsuba(x0, y0);
string C = karatsuba(add(x1, x0), add(y1, y0));
C = sub(C, add(A, B));
return add(add(A + string(2 * (n - half), '0'), C + string(n - half, '0')), B);
}
string Solution::add(string a, string b) {
int carry = 0;
string res = "";
int i = a.size() - 1, j = b.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
carry = sum / 10;
res += (sum % 10) + '0';
}
reverse(res.begin(), res.end());
return res;
}
string Solution::sub(string a, string b) {
// Assumes a >= b
int borrow = 0;
string res = "";
int i = a.size() - 1, j = b.size() - 1;
while (i >= 0 || j >= 0 || borrow) {
int diff = (i >= 0 ? a[i--] - '0' : 0) - (j >= 0 ? b[j--] - '0' : 0) - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
res += diff + '0';
}
reverse(res.begin(), res.end());
return res;
}
string Solution::mulSingle(char x, char y) {
return to_string((x - '0') * (y - '0'));
}
int main() {
Solution ob;
cout << ob.multiply("1234", "5678");
}
时间复杂度：O(n^1.585)
空间复杂度：O(1)
解释
在这个示例代码中，我们将每个数字分成两半，然后使用递归计算三个乘积：A、B和C。然后，我们使用提供的公式组合这些乘积以获得最终结果。这种方法通过将乘法分解成更小的子问题来降低乘法的复杂度，对于大数而言，这种方法效率更高。
7K+ 次浏览
