43. Multiply Strings字符串相乘

佚名 6年前 (2019-04-09) 随笔 1877人围观抢沙发百度已收录

网址：https://leetcode.com/problems/multiply-strings/submissions/

参考：https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

把乘法分解为最最基础的加法，从后往前循环。

class Solution {
public:
    string multiply(string num1, string num2) {
        int siz1 = num1.size(), siz2 = num2.size();
        if(num1 == "0" || num2 == "0")
            return "0";
        vector<int> sums(siz1+siz2, 0);
        int mul = 0;
        int p1, p2;
        int sum;
        string ans = "";
        for(int i = siz1-1; i>=0; i--)
        {
            for(int j = siz2-1; j>=0; j--)
            {
                mul = (int)(num1[i]-'0') * (int)(num2[j]-'0');
                p1 = i+j;
                p2 = i+j+1;
                sum = sums[p2] + mul;
                sums[p1] += sum / 10;
                sums[p2] = sum % 10;
            }
        }
        for(auto i : sums)
        {
            ans.append(to_string(i));
        }
        if(ans[0] == '0')
            ans = ans.substr(1, ans.size()-1);
        return ans;
    }
};