43字符串相乘.md

43字符串相乘

题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

方法一：暴力法

多次反转，消耗较大。

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0"||num2 == "0") return "0";
        vector<string> nums;
        string res;
        for(int i = num1.size()-1; i >=0; --i){
            string curNum;
            int carry = 0;
            int n1 = num1[i] - '0';
            for(int j = num2.size()-1; j >=0; --j){
                int n2 = num2[j] - '0';
                int tmp = n1*n2+carry;
                carry = tmp / 10;
                tmp = tmp % 10;
                curNum.append(to_string(tmp));
            }
            if(carry != 0){
                curNum.append(to_string(carry));
            }
            reverse(curNum.begin(),curNum.end());
            curNum.append(num1.size()-1-i,'0');
            res = addStr(res, curNum);
        }
        return res;
    }
private:
    string addStr(const string &s1, const string &s2){
        string res;
        int carry = 0;
        for(int i = s1.size()-1, j = s2.size()-1; i>=0 || j>=0 || carry!=0; --i,--j){
            int x = i<0 ? 0:s1[i]-'0';
            int y = j<0 ? 0:s2[j]-'0';
            int tmp = x+y+carry;
            carry = tmp / 10;
            tmp = tmp % 10;
            res.append(to_string(tmp));
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

方法二：位置对应

• 乘数 num1 位数为 MM，被乘数 num2 位数为 NN， num1 x num2 结果 res 最大总位数为 M+N
• num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

class Solution
{
public:
    string multiply(string &num1, string &num2)
    {
        if (num1 == "0" || num2 == "0")
            return "0";

        int len1 = num1.length();
        int len2 = num2.length();
        vector<int> ans(len1 + len2, 0);
        for (int i = 0, ci = len2 - 1; ci >= 0; ci--, i++)
            for (int j = 0, cj = len1 - 1; cj >= 0; cj--, j++)
                ans[i + j] += (num2[ci] - '0') * (num1[cj] - '0');
        int carry = 0;
        // ans的左边是低位
        // 逐位处理
        for (int i = 0; i < ans.size(); i++)
        {
            int temp = ans[i] + carry;
            carry = temp / 10;
            ans[i] = temp % 10;
        }

        string res = "";
        if (carry > 0)
            res += (carry + '0');

        // 去掉ans数组开头多余的0
        int index = ans.size() - 1;
        while (index >= 0 && ans[index] == 0)
            index--;

        for (; index >= 0; index--)
            res += (ans[index] + '0');
        return res;
    }
};