题目

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

分析

手撸高精度，没什么好说的，就按照列乘法列竖式计算的思想写就好了。

实现

class Solution {
public:
    string multiply(string &num1, string &num2) {
        string ans="0";
        int i=num2.size()-1;
        while(i>=0){
            string tmp = oneMulti(num1, num2[i]);
            if(tmp!="0"){
                for(int j=i; j<num2.size()-1; j++){
                    tmp += '0';
                }
                ans = add(ans, tmp);
            }
            i--;
        }
        return ans;
    }

private:
    string add(string &num1, string &num2){
        string ans;
        int i=num1.size()-1, j=num2.size()-1, carry=0;
        while(i>=0 && j>=0){
            int n = num1[i] - '0' + num2[j] - '0' + carry;
            carry = n / 10;
            ans += (n % 10) + '0';
            i--; j--;
        }
        while(i>=0){
            int n = num1[i] - '0' + carry;
            carry = n / 10;
            ans += (n % 10) + '0';
            i--;
        }
        while(j>=0){
            int n = num2[j] - '0' + carry;
            carry = n / 10;
            ans += (n % 10) + '0';
            j--;
        }
        if(carry>0)
            ans += carry + '0';
        reverse(ans.begin(), ans.end());
        return ans;
    }

    string oneMulti(string &num1, char num2){
        if(num2=='0') return "0";
        string ans;
        int i=num1.size()-1, carry=0;
        while(i>=0){
            int n = (num1[i] - '0') * (num2 - '0') + carry;
            carry = n / 10;
            ans += (n % 10) + '0';
            i--;
        }
        if(carry>0)
            ans += carry + '0';
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

思考

我这里用了两个子函数，但是看到别人的方法中有不用子函数的，很是好奇。发现他巧妙地将两个子函数的功能直接放在循环中完成了，贴上他的代码欣赏下。

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        string result(n1 + n2, '0');
        for (int i = n1 - 1; i >= 0; i--) {
            int carry = 0;
            for (int j = n2 - 1; j >= 0; j--) {
                int sum = result[i + j + 1] - '0';
                sum += carry + (num1[i] - '0') * (num2[j] - '0');
                result[i + j + 1] = '0' + sum % 10;
                carry = sum / 10; 
            }
            result[i] = result[i] + carry;
        }
        int start = 0;
        while (start < n1 + n2 && result[start] == '0') start++;
        return start == n1 + n2 ? "0" : result.substr(start);
    }
};