43. Multiply Strings

题目

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. 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) {
        int len1 = num1.size();
        int len2 = num2.size();
        if(len1==0||len2==0) return "0";
        if(num1=="0"||num2=="0") return "0";
        vector<int> v(len1+len2,0);
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                v[i+j] =v[i+j] +(num1[len1-i-1]-'0') * (num2[len2-j-1]-'0');
            }
        }
      	// 不管进位的把数存到相应的位置.
        int carry = 0;
        for(int i=0;i<v.size();i++)
        {
            int num = v[i] + carry;
            v[i] = num % 10;
            carry = num / 10;
        }
      	// 处理进位,因为vector足够大,所以最前面的进位也可以直接取,不用特殊处理
        string s = "";
        int  slen =v.size()-1;
        while(v[slen]==0) slen--;
      	// 去掉最前面多余的0
        for( ; slen >= 0; slen--)
            s += v[slen] + '0';
        return s;
    }       
};

思路

简单来说,

假设两个整数的长度分别为了l1和l2，则其最后结果长度为l1+l2（最后有进位）或者l1+l2-1（最后没有有进位）。

因此，可以先用长度为l1+l2的数组记录结果，最后再转成字符串。

进行乘法的时候，先把各个位的相乘结果对应累加起来，即第1个整数的第i位（低位到高位）和第2个整数的第j位（低位到高位）相乘的结果应该存放在数组的i+j位。

其次,首先不管进位,直接把得到的值存在相应的位置上,就像

然后再一次性处理进位.

接着把前面多余的零去掉,然后加到字符串中即可.