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;}
};
