精选力扣500题 第72题 LeetCode 43. 字符串相乘【c++/java详细题解】

目录

1、题目

给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。

2、思路

(字符串模拟) O ( n ∗ m ) O(n*m) O(nm)

普通竖式

num1 = 123 , num2 = 456为例:我们遍历 num2 每一位与 num1 进行相乘,将每一步的结果进行累加,在这个过程如果相乘或者相加的结果大于等于10 ,我们都要去满10进位,如下图所示:

《精选力扣500题 第72题 LeetCode 43. 字符串相乘【c++/java详细题解】》

这样模拟普通竖式计算的方法较为复杂,我们可以考虑优化版的竖式计算。

优化竖式

其实在相乘或者相加计算过程的每一位,我们可以考虑先不去满10进位,等到计算完所有的相乘结果以后,最终将其加到一块,再去满10进位 ,最后的结果和普通竖式 一样,但却可以大大简化我们的模拟过程。(如下图所示)

《精选力扣500题 第72题 LeetCode 43. 字符串相乘【c++/java详细题解】》

具体过程如下:

  • 1、长度是n和长度是m的数字相乘,最多只有n + m位,为了方便计算,将num1num2反向存储到A[]B[]中,即位数低的在数组前面,且开一个大小是n + mC[]存储计算后的答案。
  • 2、两个数相乘时,将A[i] * B[j]的结果累加到C[i + j]中,最后C[i + j]表示i + j这个位数的值是C[i + j](如上图所示)
  • 3、由于C[]数组中的某些位数字可能是大于等于10的,我们从0枚举到n + m - 1,进行满10进位, 将所有位的值全部变成个位数。
  • 4、最后将C[]数组反转输出。

细节:

  • 最终得到的数组C[]的高位可能包含前导0,因此在反转之前要先去除高位前导0

时间复杂度分析: O ( n ∗ m ) O(n*m) O(nm) n n n m m m分别是 n u m 1 num1 num1 n u m 2 num2 num2的长度。

3、c++代码

class Solution { 
public:
    string multiply(string num1, string num2) { 
        vector<int> A, B;
        int n = num1.size(), m = num2.size();
        for (int i = n - 1; i >= 0; i -- ) A.push_back(num1[i] - '0'); //反向存贮
        for (int i = m - 1; i >= 0; i -- ) B.push_back(num2[i] - '0');
        vector<int> C(n + m);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                C[i + j] += A[i] * B[j];
        int t = 0;  //存贮进位
        for (int i = 0; i < C.size(); i ++ ) { 
            t += C[i];
            C[i] = t % 10;
            t /= 10;
        }
        int k = C.size() - 1;
        while (k > 0 && !C[k]) k -- ;  //去除前导0
        string res;
        while (k >= 0) res += C[k -- ] + '0';  //反转
        return res;
    }
};

4、java代码

class Solution { 
    public String multiply(String num1, String num2) { 

        int n = num1.length(), m = num2.length();
        int[] A = new int[n], B = new int[m];
        for (int i = n - 1; i >= 0; i--) A[n - 1 - i] = num1.charAt(i) - '0';
        for (int i = m - 1; i >= 0; i--) B[m - 1 - i] = num2.charAt(i) - '0';

        int[] C = new int[n + m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                C[i + j] += A[i] * B[j];
        int t = 0;
        for (int i = 0; i < C.length; i++) { 
            t += C[i];
            C[i] = t % 10;
            t /= 10;
        }
        int k = C.length - 1;
        while (k > 0 && C[k] == 0) k--;
        StringBuilder sb = new StringBuilder();
        while (k >= 0) sb.append((char)(C[k--] + '0'));
        return sb.toString();
    }
}

原题链接: 43. 字符串相乘
《精选力扣500题 第72题 LeetCode 43. 字符串相乘【c++/java详细题解】》

    原文作者:林深时不见鹿
    原文地址: https://blog.csdn.net/weixin_45629285/article/details/119271984
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞