【leetcode】43. Multiply Strings 大数乘法

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

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!