資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
