1. 题目

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

The numbers can be arbitrarily large and are non-negative.Converting the input string to integer is NOT allowed.You should NOT use internal library such as BigInteger.

2. 思路

模拟手算的过程，按位相乘并累加。

方便处理中间结果，每次保存的都是逆序的，然后反转。也可以每次都保持逆序结果，到最后的时候再反转过来。

3. 代码

耗时：26ms

class Solution {public:    // 模拟乘法手算过程实现    string multiply(string num1, string num2) {        string sum;        sum.reserve(num1.length() * num2.length() + 2);        string prefix;        // 从低到高位逐个字符相乘，然后加入到总和中去。        for (int i = num2.length() - 1; i >= 0; i--) {            char c2 = num2[i];            string c_sum = multiply(num1, c2) + prefix;            sum = plus(sum, c_sum);            prefix += '0';        }        // 去掉前导0多余的0，至少保留一位        int i = 0;        while (sum[i] == '0' && i < sum.length() - 1) {i++;}        return sum.substr(i);    }        string multiply(string& n, char c) {        string r;        r.reserve(n.length() + 2);        int jingwei = 0;        for (int i = n.length() - 1; i>= 0; i--) {            int m = multiply(n[i], c);            m += jingwei;            r += m % 10 + '0';            jingwei = m / 10;        }        if (jingwei != 0) {            char ch = '0' + jingwei;            r += ch;        }        reverse(r.begin(), r.end());        return r;    }        int multiply(char c1, char c2) {        return (c1 - '0') * (c2 - '0');    }        string plus(string& n1, string& n2) {        string n3;        int l1 = n1.length();        int l2 = n2.length();        int min_v = min(l1, l2);        int max_v = max(l1, l2);        n3.reserve(max_v + 2);        char jingwei = '0';        for (int i = 1; i <= min_v; i++) {            char c1 = n1[l1 - i];            char c2 = n2[l2 - i];            int c_sum = plus(c1, c2, jingwei);            n3 += c_sum % 10 + '0';            jingwei = c_sum / 10 + '0';        }        string& big = n1;        if (l2 > l1) { big = n2; }        for (int i = min_v + 1; i <= max_v; i++) {            int c_sum = plus(big[max_v - i], jingwei);            jingwei = c_sum / 10 + '0';            n3 += c_sum % 10 + '0';        }        if (jingwei != '0') {            n3 += jingwei;        }        reverse(n3.begin(), n3.end());        return n3;    }    int plus(char c1, char c2) {        return c1 + c2 - 2 * '0';    }    int plus(char c1, char c2, char c3) {        return c1 + c2 + c3 - 3 * '0';    }};