43. 字符串相乘
自己做
解1：矩陣計數
class Solution {
public:string multiply(string num1, string num2) {int len1 = num1.size();int len2 = num2.size();if (num1[0] == '0' || num2[0] == '0') //結果為0的情況return "0";//存儲計算過程的矩陣vector<vector<int>> calculation(len1, vector<int>(len1 + len2, 0));string string_res; //存放結果//計算for (int i = len1 - 1; i >= 0; i--) {int add = 0; //進位 for (int j = len2 - 1; j >= 0; j--) {int res = (num1[i] - 48) * (num2[j] - 48) + add; //當前結果//cout << res << " ";calculation[len1 - 1 - i][i + j + 1] = res % 10; //余位add = res / 10; //進位}if(add > 0) //進位有多calculation[len1 - 1 - i][i] = add; //cout << endl;}//// 輸出二維向量//cout << "calculation = [" << endl;//for (int i = 0; i < calculation.size(); ++i) {// cout << " [";// for (int j = 0; j < calculation[i].size(); ++j) {// cout << calculation[i][j];// if (j != calculation[i].size() - 1) {// cout << ", ";// }// }// cout << "]" << (i == calculation.size() - 1 ? "" : ",") << endl;//}//cout << "]" << endl;//累加矩陣所有元素int add = 0; //累加的進位for (int i = len1 + len2 - 1; i >= 0; i--) {int res = 0; //這一輪累加的結果for (int j = 0; j < len1; j++) res += calculation[j][i];res += add; //加上進位string_res.insert(string_res.begin(), res % 10 + 48); //余位存放進結果add = res / 10; //進位更新}if (add > 0)string_res.insert(string_res.begin(), add + 48); //余位存放進結果//消除前面的零while (string_res[0] == '0')string_res.erase(string_res.begin());return string_res;}
};
解2：優化解1
class Solution {
public:string multiply(string num1, string num2) {int len1 = num1.size();int len2 = num2.size();if (num1[0] == '0' || num2[0] == '0') //結果為0的情況return "0";string string_res(len1 + len2, '0'); //存放結果，結果最長也只是兩者長度的和，不可能更長//計算for (int i = len1 - 1; i >= 0; i--) {int add = 0; //進位 for (int j = len2 - 1; j >= 0; j--) {int int_res = (num1[i] - 48) * (num2[j] - 48) + (string_res[i + j + 1] - 48) + add; //當前結果string_res[i + j + 1] = int_res % 10 + 48; //余位存放進結果add = int_res / 10; //進位}if (add > 0) //進位有多string_res[i] = add + 48;}//消除前面的零while (string_res[0] == '0')string_res.erase(string_res.begin());return string_res;}
};
)
