首页 > 代码库 > 【LeetCode】Multiply Strings

【LeetCode】Multiply Strings

Multiply Strings

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.

 

我借鉴了JackBauer的一些思想,将乘积逆序存放在int数组result中。

记num1当前为第ind1位(个位为0),num2当前为ind2位,则乘积存放在result[ind1+ind2]中。

细节见代码与注释。

class Solution {public:    string multiply(string num1, string num2) {        int m = num1.size();        int n = num2.size();        //record each digit of result in reverse order        vector<int> result(m+n, 0);         //num index, the rightmost denotes as 0        int ind1 = 0;           int ind2 = 0;        for(int i = m-1; i >= 0; i --)        {            int carrier = 0;            int n1 = num1[i]-0;            //for every digit in num1, the num2 start with the rightmost digit            ind2 = 0;               for(int j = n-1; j >= 0; j --)            {                int n2 = num2[j]-0;                int product = n1*n2 + result[ind1+ind2] + carrier;                carrier = product/10;                result[ind1+ind2] = product%10;                ind2 ++;            }            //all digits in num2 finished multiplication with num1[i]            //the remaining carrier added in the right position            result[ind1+ind2] += carrier;            ind1 ++;        }                //skip 0s in the right of result        while(result.size() > 0 && result[result.size()-1] == 0)            result.pop_back();        if(result.empty())            return "0";        else        {            string s;            int i = result.size();            while(i --)                s += (0+result[i]);            return s;        }    }};

【LeetCode】Multiply Strings