题解 | #大数乘法#

模拟大法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        while(s.length() > 1 && s[0] == '0') s.erase(0, 1);
        while(t.length() > 1 && t[0] == '0') t.erase(0, 1);
        if(s == "0" || t == "0") return "0";
        int m = s.length(), n = t.length();
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        vector<string> vec;

        for(int i = 0; i < m; i ++){
            string str;
            int cnt = 0;
            while(cnt < i) str += '0', cnt ++;
            int carry = 0;
            for(int j = 0; j < n; j ++){
                int x = (s[i] - '0') * (t[j] - '0') + carry;
                carry = x / 10;
                str += x % 10 + '0';
            }
            if(carry > 0) str += carry + '0';
            //cout << str << " ";
            vec.push_back(str);
        }
        queue<string> q;
        for(string s:vec) q.push(s);
        while(q.size() > 1){
            string s1 = q.front(); q.pop();
            string s2 = q.front(); q.pop();
            string str = addStr(s1, s2);
            q.push(str);
        }
        string res = q.front(); q.pop();
        reverse(res.begin(), res.end());
        return res;
    }
    string addStr(string s1, string s2){
        int m = s1.length(), n = s2.length();
        int carry = 0;
        int i = 0, j = 0;
        string res;
        while(i < m && j < n){
            int x = s1[i] - '0' + s2[j] - '0' + carry;
            carry = x / 10;
            res += x % 10 + '0';
            i ++;
            j ++;
        }
        while(i < m){
            int x = s1[i] - '0' + carry;
            carry = x / 10;
            res += x % 10 + '0';
            i ++;
        }
        while(j < n){
            int x = s2[j] - '0' + carry;
            carry = x / 10;
            res += x % 10 + '0';
            j ++;
        }
        if(carry > 0) res += carry + '0';
        return res;
    }
};