华为43.字符串相乘——大数相乘

题目描述

传送门-力扣

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

思路

对于两个较大的数相乘，由于其可能导致溢出，因此需要进行判断并处理，比较麻烦，因此直接操作字符串的每一位，用数组保存结果进行过度，对数组进行处理后再转换为字符串输出，从而避免溢出问题。

1. 观察两数相乘的过程可以知道，对于两个数num1、num2相乘，其结果的位数是num1的位数与num2的位数之和或者两者之和减1，同时，两个数字中某位置i和j相乘的结果在最后结果中的位置可以由i和j计算出来。
2. 因此，采用一个vector数组，其大小为两个数组的长度和，分别计算两个数字中对应位置相乘的积累加到vector对应的位置中。
3. 然后对vector进行处理，将后一个位置对10整除得到的结果表示进位，加到前一个位置中，而后一个位置对10取余得到后一个位置实际的值。
4. 最后，判断vector容器的第0个位置是否为0，将vector输出到string中。

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.length(), len2 = num2.length();
        if(num1 == "0" || num2 == "0") return "0";
        //计算vector的每个位置初始累加值
        vector<int> arr(len1 + len2, 0);
        for(int i = len1 - 1; i >= 0; i--)
            for(int j = len2 - 1; j >= 0; j--)
                arr[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
        //计算vector的每个位置实际值
        for(int i = len1 + len2 - 1; i >= 0; i--)
        {
            if(i > 0) arr[i - 1] += arr[i] / 10;
            arr[i] = arr[i] % 10;
        }
        //转换为string输出
        int index = arr[0] == 0? 1 : 0;
        string res;
        while(index < len1 + len2)
            res.push_back(arr[index++] + '0');

        return res;
    }
};