LeetCode 刷题【43. 字符串相乘】

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