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.

这道题就是模拟乘法思维了，还需要模拟加法思维，每一位乘以一个数都要和前面的结果加起来。

注意：

1 要把这两个操作过程分清楚，不能混饶了，否则会结果不正确的。

2 乘法有进位，和前面的结果加起来也有加法进位，一定要分清楚。

3 每一次一个新数位与被乘数相乘之前，都一定要把两个进位加在结果上。

4 同时需要把两个进位值都清零。

整体思路：

这道题的要求是计算大数乘法。其中大数是以字符串的形式表示，任意大，非负，返回结果以字符串形式。

这道题其实就是模拟整数乘法。

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

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

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

然后再统一处理进位。

最后再将数组转成字符串前，需要跳过前面的零。如果结果只有0，则只返回0。

时间复杂度：O(l1l2)（l1和l2分别为两个整数长度）

空间复杂度：O(l1+l2)

class Solution {

public:

    string multiply(string num1, string num2) {

        int n1 = num1.length();

        int n2 = num2.length();

        if(n1 ==  || n2 == ) return "";

        int upto = ;

        int sumupto = ;

        string sum;

        int s = ;

        sum.resize(n1+n2, '');

        int i, j;

        for (i = n1-; i >= ; i--)

        {

            int a = num1[i] - '';

            //注意：每次新开始upto进位值都要清零

            for (j = n2-, upto = ; j >= ; j--)

            {

                int b = num2[j] - '';

                s = b * a + upto;

                upto = s / ;

                //注意：要系统分析，先计算出乘法，处理好，之后再处理加法。

                int rmd = s%;

                int sij1 = sum[i+j+] - '';

                int rs = rmd + sij1 + sumupto;

                sumupto = rs/;

                rs %= ;

                sum[i+j+] = rs + '';

            }

            //注意：把最后一次的进位值加上!

            //注意：要把加法进位和乘法进位都加上

            sum[i+j+] += (upto+sumupto);

            //注意：加法进位一定需要清零

            sumupto = ;

        }

        while (sum.length() >  && sum[] == '') sum.erase(sum.begin());

        return sum;

    }

};

上面是网上的答案，各种进位好凌乱，其实不需要这么复杂，对于每一位，把相乘的结果加上上一次的进位结果加上原来这个位置就有的数，然后统一计算下一次的进位。这样做，简洁的多了，也好理解多了，代码如下：

（面试腾讯实习生的时候遇到这道题，所以又重做了一遍，我在编译器中用的是strNum1, strNum2，所以在leetcode中直接赋值了）

class Solution {

public:

    string multiply(string num1, string num2) {

    string strNum1, strNum2;

    strNum1=num1;

    strNum2=num2;

    int strLen1 = strNum1.size();

    int strLen2 = strNum2.size();

    if (strLen1 <=  || strLen2 <= )

        return “”;

    string res(strLen1 + strLen2, '');

    int carryM = ;

    int carryP = ;

    int i, j;

    for ( i = strLen1 - ; i >= ; i--)

    {

        int sNum1 = strNum1[i] - '';

        for ( j = strLen2 - ; j >= ; j--)

        {

            int sNum2 = strNum2[j] - '';

            int sum = sNum1*(strNum2[j] - '') + carryP + (res[i + j + ] - '');

            carryP = sum / ;

            int num = sum % ;

            res[i + j + ] = num + '';

        }

        res[i + j + ] = carryP+'';

        carryP = ;

    }

    while (res.length() >  && res[] == '') res.erase(res.begin());

    return res;

    }

};