Leetcode43. 字符串相乘

2021年9月9日 106点热度 2人点赞 0条评论

题目描述

给定两个以字符串形式表示的非负整数 num1num2,返回 num1num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

  1. num1num2 的长度小于110。
  2. num1num2 只包含数字 0-9
  3. num1num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)直接将输入转换为整数来处理

解题思路

方法一 列竖式计算法

算法详述

这道题最常见的解法就是模拟列竖式计算的方法进行计算两个字符串的值。

如上图所示,当nums1nums2均不为0的时候,将nums1nums2分别视为被乘数和乘数,从右往左遍历乘数,将乘数的每一位与被乘数相乘得到相应的结果,然后将每次得到的结果累加得到最终的答案。

如果nums1nums2至少有一个为0,那么直接返回0即可。

示例代码

string addString(string& nums1, string& nums2){
    int i = nums1.size() - 1;
    int j = nums2.size() - 1;
    int add = 0;
    string ans;

    while(i >= 0 || j >= 0 || add != 0){
        int x = i >= 0 ? nums1[i] - '0' : 0;
        int y = j >= 0 ? nums2[j] - '0' : 0;
        int res = x + y + add;

        ans.push_back(res % 10 + '0');
        add = res / 10;

        i--;
        j--;
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

string multiply(string& nums1, string& nums2){
    if(nums1 == "0" || nums2 == "0"){
        return "0";
    }

    string ans = "0";
    int m = nums1.size();
    int n = nums2.size();
    for(int i = n - 1; i >= 0; --i){
        string tmp;
        int add = 0;
        for(int j = n - 1; j > i; --j){
            tmp.push_back(0 + '0');
        }

        int y = nums2[i] - '0';
        for(int j = m - 1; j >= 0; --j){
            int x = nums1[j] - '0';
            int res = x * y + add;
            tmp.push_back(res % 10 + '0');
            add = res / 10;
        }
        while(add != 0 ){
            tmp.push_back(add % 10 + '0');
            add /= 10;
        }

        reverse(tmp.begin(), tmp.end()); 
        ans = addString(ans, tmp);  
    }
    return ans;
}

复杂度分析

时间复杂度为:$O(mn+n^2)$,其中 $m$ 和 $n$分别是 nums1nums2的长度

空间复杂度为:$O(m+n)$,其中 $m$ 和 $n$分别是 nums1nums2的长度

方法二 优化后的列竖式计算法

算法详述

一般列竖式计算的做法是从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加。在相加的过程中,相加的字符串的长度分别为$m,m+1, \cdots,m+n$,因而相加的平均字符串长度为$\frac{n(2m+n)}{2}$,而相加的次数一共为$n$次,两者相乘后可以得到总体的时间复杂度为$O(mn+n^2)$,太过耗时。而且观察得知,主要在于相加的过程耗时。所以我们可以从这方面下手进行优化。

如果将被乘数和乘数的每一位分别进行相乘,并且将相乘的结果使用数组代替字符串存储结果,那么可以简化为至多两位数加法运算,减少了对字符串的操作。

令 $m$ 和 $n$ 分别表示 nums1nums2的长度,并且它们均不为 0,则nums1nums2的乘积的长度为$ m+n-1$ 或 $m+n$。

上述结论的简单证明如下:

  • 如果nums1nums2都取最小值,则$nums1 = 10^{m-1},num2 = 10^{n-1},nums1 \times nums2 = 10^{m+n-2}$,乘积的长度为$m+n-1$;
  • 如果nums1nums2都取最大值,则$nums1 = 10^{m}-1,num2 = 10^{n}-1,nums1 \times nums2 = 10^{m+n}-10^{m}-10^{n}+1$,乘积显然小于$10^{m+n}$且大于$10^{m+n-1}$,所以乘积的长度为$m+n$;

由于nums1nums2的乘积的长度最多为$m+n$,因此可以创建长度为$m+n$的数组ans存储乘积。对于任意的$0 \leq i \leq m$和$0 \leq j \leq n$,$nums1[i] \times nums2[j]$的结果存储在$ans[i+j+1]$,如果$ans[i+j+1] \geq 10$,则将进位的部分加到$ans[i+j]$。

过程可以参见下图:

最后还需要将ans数组转化为字符串,如果最高位为0的话还需要舍弃最高位。

实例代码

string multiply(string& nums1, string& nums2){
    if(nums1 == "0" || nums2 == "0"){
        return "0";
    }

    vector<int> ans(nums1.size() + nums2.size(), 0);
    for(int i = nums1.size() - 1; i >= 0; --i){
        int x = nums1[i] - '0';
        for(int j = nums2.size() - 1; j >= 0; --j){
            int y = nums2[j] - '0';
            ans[i + j + 1] += x * y;
            if(ans[i + j + 1] > 9){
                ans[i + j] += ans[i + j + 1] / 10;
                ans[i + j + 1] %= 10;
            }
        }
    }

    string ansStr;
    int index = 0;
    if(ans[0] == 0) index++;
    while(index < ans.size()){
        ansStr += (ans[index] + '0');
        index++;
    }

    return ansStr;
}

复杂度分析

时间复杂度为:$O(mn)$,其中 $m$ 和 $n$分别是 nums1nums2的长度

空间复杂度为:$O(m+n)$,其中 $m$ 和 $n$分别是 nums1nums2的长度

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论