43. 字符串相乘

43. 字符串相乘

字符串加法模拟出字符串乘法

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.size() > num2.size())
            swap(num1, num2);
        string ret = "";
        for(int i = num1.size() - 1; i >= 0; --i)
        {
            int c = 0;
            int x = num1[i] - '0';
            string tmp;
            for(int b = num2.size() - 1; b >= 0; --b)
            {
                int t = (num2[b] - '0') * x + c;
                tmp += char(t % 10 + '0');
                c = t / 10;
            }
            if(c != 0)
                tmp += char(c + '0');
            while(tmp.size() > 1 && tmp.back() == '0')
                tmp.pop_back();
            reverse(tmp.begin(), tmp.end());
            num2 += '0';
            ret = add(ret, tmp);
        }
        return ret;
    }
private:
    string add(string& num1, string& num2)
    {
        int c = 0;
        int a = num1.size() - 1, b = num2.size() - 1;
        string ret;
        while (a >= 0 || b >= 0 || c)
        {
            int i = 0;
            if(a >= 0)
                i += num1[a--] - '0';
            if(b >= 0)
                i += num2[b--] - '0';
            i += c;
            c = i / 10;
            i %= 10;
            ret += char(i + '0');
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

转成数组存储每一位的计算结果，最后把数组转成字符串

c++中字符串可以直接当作数组

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") // 如果有0，返回0
            return "0";
        int m = num1.size(), n = num2.size();
        string ret(m + n, '0'); // 乘积大小不会大于m+n位，具体看题解的证明
        for(int i = m - 1; i >= 0; --i)
            for(int j = n - 1; j >= 0; --j)
            {
                int tmp = (num1[i] - '0') * (num2[j] - '0') + ret[i + j + 1] - '0';
                ret[i + j + 1] = tmp % 10 + '0'; // 第i位和第j位的两个字符串乘法结果到第i+j+1位上
                ret[i + j] = (ret[i + j] - '0' + tmp / 10) + '0'; // 进位存在前一位，由于是从大到小处理，所以不用担心溢出，后续会处理。
            }
        // 去掉开头0
        for(int i = 0; i < m + n; ++i)
            if(ret[i] != '0') 
                return ret.substr(i, m + n - i);
        return "0";
    }
};