LeetCode: 43. Multiply Strings

题目描述

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.

大意就是让写一个大数乘法的函数。

解题思路

模拟乘法计算的过程。为了方便起见，将字符串翻转。

AC 代码

class Solution {
public:
    string multiply(string num1, string num2) {
        string ans;

        if(num1 == "0" || num2 == "0") return "0";

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        int carryNum = 0;

        for(int i = 0; i < num1.size(); ++i)
        {
            for(int j = 0; j < num2.size(); ++j)
            {
               if(i+j >= ans.size()) ans.resize(i+j+1, 0);
               ans[i+j] += (num1[i]-'0')*(num2[j]-'0') + carryNum;
               carryNum = ans[i+j]/10;
               ans[i+j] %= 10;
            }

            for(int j = num2.size(); carryNum != 0; ++j)
            {
               if(i+j >= ans.size()) ans.resize(i+j+1, 0);
               ans[i+j] += carryNum;
               carryNum = ans[i+j]/10;
               ans[i+j] %= 10;
            }
        }

        for(int i = 0; i < ans.size(); ++i)
        {
            ans[i] += '0';
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};