【LeetCode】43. 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.
题目链接：leetCode

我的思路

• 两个数相乘的时候，最后得到的积位数绝对不会超过这两个数的位数和

• 假设A数有m位，B数有n位，两数相乘得到C的位数为m+n，那么使用m+n的int数组存放每一位相乘的结果，当然数组中的每一位都不一定是个位数，所以最后用一个循环把这个数组中的数字循环一边，逐个进位，最后得到结果

• 如果采用这种思路的话，自己就需要手动处理一些首位为0的情况

代码

代码是C++的：

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

        int num1_size = num1.size();
        int num2_size = num2.size();
        //注意，这个并不是一定就是两个相加这么长的位数
        int result_size = num1_size + num2_size;
        int result[result_size] = {0};
        int num1_array[num1_size] = {0};
        int num2_array[num2_size] = {0};
        for( int i=0; i<num1_size; i++)
        {
            num1_array[i] = num1[i] - '0';
        }
        for( int i=0; i<num2_size; i++)
        {
            num2_array[i] = num2[i] - '0';
        }
        for(int i=0; i<num1_size; i++)
        {
            for(int j=0; j<num2_size; j++)
            {
                result[i+j+1] = result[i+j+1] + num1_array[i]*num2_array[j];
            }
        }
        for(int i=result_size-1; i>=0; i--)
        {
            int temp1 = result[i]%10;
            int temp2 = (result[i]-temp1)/10;
            result[i-1] = result[i-1] + temp2;
            result[i] = temp1;
        }
        bool flag = true;
        string s = "";
        for(int i=0; i<result_size; i++)
        {
            if(flag && result[i]==0 && i!=result_size-1)
            {
                continue;
            }
            else
            {
                flag = false;
            }
            char temp_char = '0' + result[i];
            s.append(1,temp_char);
        }
        return s;
    }
};

运算效率结果截图