【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;
    }
};

运算服从功效截图

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!