面试题-----大数相乘问题

傷城~ 2022-05-20 09:50 160阅读 0赞

在计算机中存储数据的大小是有限的，当我们需要表示一个很大的数的时候应该很自然就能想到用字符串。字符串相乘问题在笔试面试中也比较常见，直接上思想：

我们可以借助于可动态调整大小的数据结构（vector,string,deque）模拟实现数字的乘法操作。对于普通的乘法，我们知道m位数和n位数相乘，最后的结果位数在区间\[m+n-1,m+n\]内。  
举个例子：25\*23  
![这里写图片描述][70]

就是标准的手动乘法运算，只不过通常是用第一个数字去乘第二个数字中的每一位，然后将结果相加。就是左边这种情况，而右边这种情况实际上就是**23\*25** 。我们使用两个嵌套的for循环，从每个输入数字的末尾开始。利用一个预先分配好空间的string保存部分结果。然后每次将部分部分结果进行累加。需要注意的一个特殊情况是，在最后需要去除掉结果最开始多余的0

class Solution {
    public:
        string multiply(string num1, string num2) {
            int size1 = num1.size();
            int size2 = num2.size();
            if(size1 == 0 || size2 == 0) 
                return num1;
            if(num1 == "0"||num2 == "0")  //判断如果其中一个字符串为0，直接返回0
                return "0";
            //因为两个数字相乘结果的位数不会超过size1+size2，所以开辟这么大的空间
            string s(size1 + size2, '0');
            for(int i = size1 - 1; i >= 0; i--)
            {
                int mul = 0;//保存进位
                for(int j = size2 - 1; j >= 0; j--)
                {
                    //计算两个数字中某一位的相乘结果并加上进位和之前保存的结果
                    int tmp = (s[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + mul; 
                    s[i + j + 1] = tmp - mul * 10;//先保存不考虑进位时候的结果
                    mul = tmp / 10;//更新进位
                }
                s[i] += mul;  //保存一轮计算完的最后一个进位
            }
            if(s[0] == '0')//去除结果开头的0
                s = s.substr(1, s.size());
            return s;
        }
    };

还是不太理解的，举个例子调试一把就懂！！！

[70]: /images/20220520/8c9dcb35c2dd415bb7b0489e2e6c9b38.png