LeetCode-43. 字符串相乘

问题地址

LeetCode每日一题/2020-08-13

LeetCode43. 字符串相乘

问题描述

规则

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

示例1

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

示例2

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

提示

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解析

解题思路

根据题目要求不可以使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理，我们可以模拟竖式乘法计算两个字符串相乘。
对于n1 ✖ n2，我们的计算过程如下：

如果n1和n2之中有1个是0，则返回结果0；
如果n1=1则返回n2，如果n2=1则返回n1；
竖式乘法计算过程：
1. 多位数（A）在上，少位数(B)在下；
2. 用下边因数的个位数分别与上边因数的每一位数相乘，在计算的过程中任何一位数的乘积满十，需要进位，然后继续与上边因数的下一位数相乘；
3. 以此类推分别使用下边因数的十位数、百位数…与上边因数的每一位数相乘，所不同的是，除下边因数的个位数与上边因数的乘积不需要补0外，其它位数均需根据位数递增补0，如上图中黄色背景所示；
4. 将每次乘得的数相加即可；

复杂度分析

时间复杂度，竖式乘法需要用A的每一位乘以B的每一位，乘的次数是mn，A的每一位数乘以B所得出的乘积相加的复杂度为m*n，所以时间复杂度为O(mn+ $n^2$ );
空间复杂度，需要保存每一位相乘的结果，两数相乘最大长队位两数长度之和，所以空间复杂度位O(n+m);

定位问题

使用B的每一位与A的每一位相乘，结果存如字符数组中；
第一步计算结果求和；

数据操作分析

遍历数字A，得出A的每一位与数字B的乘积；
遍历第一步中得出的结果并与上一步的计算结果求和；

编码实现

public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        if (num1.equals("1")) return num2;
        if (num2.equals("1")) return num1;

        int outerCircLen = num1.length();
        int interCircLen = num2.length();
        if (outerCircLen > interCircLen) {
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
            outerCircLen = interCircLen;
            interCircLen = num2.length();
        }

        String ans = "0";
        for (int i = outerCircLen - 1; i >= 0; i--) {
            char[] chars = new char[interCircLen + outerCircLen - i];

            int carryNum = 0;
            for (int j = interCircLen - 1; j >= 0; j--) {
                int a = num1.charAt(i) - '0';
                int b = num2.charAt(j) - '0';
                int c = a * b;
                int currentPosNum = carryNum + (c % 10);
                if (currentPosNum >= 10) {
                    currentPosNum = currentPosNum % 10;
                }
                chars[j + 1] = Character.forDigit(currentPosNum, 10);
                carryNum = (c + carryNum) / 10;
                if (j == 0) chars[j] = Character.forDigit(carryNum, 10);
            }

            ans = strAdd(ans, chars);
        }

        return ans;
    }

    private String strAdd(String ans, char[] chars) {
        char[] ansChars = ans.toCharArray();
        int outerCircLen = ans.length();
        int interCircLen = chars.length;

        if (outerCircLen < interCircLen) {
            outerCircLen = interCircLen;
            char[] tChas = ansChars;
            ansChars = chars;
            chars = tChas;
            interCircLen = chars.length;
        }

        int[] result = new int[outerCircLen + 1];
        for (int i = 0; i < outerCircLen; i++) {
            if (ansChars[outerCircLen - i - 1] == '\u0000') ansChars[outerCircLen - i - 1] = '0';
            int a = ansChars[outerCircLen - i - 1] - '0';
            int b = 0;
            if (i < interCircLen) {
                b = chars[interCircLen - i - 1] - '0';
            }

            int d = result[outerCircLen - i];

            int c = a + b;
            result[outerCircLen - i] = 0;
            int currentPosNum = d + (c % 10);

            if (currentPosNum < 10) {
                result[outerCircLen - i] = currentPosNum;
            } else {
                c += currentPosNum;
            }
            result[outerCircLen - i - 1] = c / 10;
        }

        StringBuffer sb = new StringBuffer();
        StringBuffer sb = new StringBuffer();
        boolean isEncounteredGtZeroNum  = false;
        for (int i = 0; i < result.length; i++) {
            if (!isEncounteredGtZeroNum  && result[i] == 0) continue;
            isEncounteredGtZeroNum  = true;
            sb.append(result[i]);
        }

        return sb.toString();
    }

官方解法

做加法

思路：
1. 如果 $num_1$ 和 $num_2$ 之一是 0，则直接将 0 作为结果返回即可。
2. 如果 $num_1$ 和 $num_2$ 都不是 00，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 $num_1$ ，乘数是 $num_2$ 。
3. 需要注意的是， $num_2$ 除了最低位以外，其余的每一位的运算结果都需要补0。
复杂度分析：
- 时间复杂度：O(mn+ $n^2$ )，其中 m 和 n 分别是 $num_1$ 和 $num_2$ 的长度。需要从右往左遍历 $num_2$ ，对于 $num_2$ 的每一位，都需要和 $num_1$ 的每一位计算乘积，因此计算乘积的总次数是 mn。字符串相加操作共有 n 次，相加的字符串长度最长为 m+n，因此字符串相加的时间复杂度是 O(mn+ $n^2$ )。总时间复杂度是O(mn+ $n^2$ )。
- 空间复杂度：O(m+n)O(m+n)，其中 m 和 n 分别是 $num_1$ 和 $num_2$ 的长度。空间复杂度取决于存储中间状态的字符串，由于乘积的最大长度为 m+n，因此存储中间状态的字符串的长度不会超过 m+n。

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String ans = "0";
        int m = num1.length(), n = num2.length();
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.append(0);
            }
            int y = num2.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            ans = addStrings(ans, curr.reverse().toString());
        }
        return ans;
    }

    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }
}

做乘法

思路：
方法一的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，整个过程中涉及到较多字符串相加的操作。如果使用数组代替字符串存储结果，则可以减少对字符串的操作。
令 m 和 n 分别表示num_1和num_2的长度，并且它们均不为0，则num_1和num_2的乘积的长度为m+n-1或m+n。简单证明如下：
- 如果 $num_1$ 和 $num_2$ 都取最小值，则 $num_1=10^{m-1}$ ， $num_2=10^{n-1}$ ， $num_1 × num_2=10^{m+n-2}$ ，乘积的长度为 m+n-1；
- 如果 $num_1$ 和 $num_2$ 都取最大，则 $num_1=10^{m}-1$ ， $num_2=10^{n}-1$ ， $num_1 × num_2=10^{m+n}-10^{m}-10^{n}+1$ ，乘积显然小于 $10^{m+2}$ 大于 $10^{m+n-1}$ ，因此乘积的长度为m+n；

由于 $nm_1$ 和 $nm_2$ 的乘积的最大长度为 $m+n$ ，因此创建长度为m+n的数组 $ansArr$ 用于存储乘积。对于任意 $0<=i<=m$ 和 $0<=j=10$ ，则将进位部分加到 $ansArr[i+j]$ ；
最后将数组 $ansArr$ 转为字符串，如果最高位是0则舍弃最高位；

复杂度分析：
- 时间复杂度：O(mn)，其中m和n分别是num1和num2的长度。需要计算 num1的每一位和num2的每一位的乘积。
- 空间复杂度：O(m+n)，其中m和n分别是num1和2num2的长度。需要创建一个长度为 m+n 的数组存储乘积。

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }
}

官方解法二的优化

方法二还可以用另外一种方法改写。我们把两个数相乘看成是两个多项式相乘，因为任何一个数都可以表示成为：

$\sum\limits_{i=0}^{n-1}a_i × 10^i$

的形式，也就相当于多项式：

$A(x)=\sum\limits_{i=0}^{n-1}a_ix^i$

在x = 10处求值。当两个数 $N_a、N_b$ 相乘的时候，我们也可以认为这两个数是两个多项式:

$\begin{cases} A(x)=\sum\limits_{i=0}^{n-1}a_ix^i& \\ B(x)=\sum\limits_{i=0}^{n-1}b_ix^i& \\ \end{cases}$

相乘的结果 $C(x)=A(x)\timesB(x)$ 在 x = 10 处求值。我们可以这样表示 C(x)：

$C(x)=\sum\limits_{i=0}^{m+n-2}c_ix^i$

这里：

$c_i=\sum\limits_{k=0}^{i}a_kb_{i-k}$

于是我们就可以顺序求解 $c_i$ ，每次 $O(i)$ 地选取下标和为 $i$ 的一组 $(a_k,b_{i-k})$ ，求到 $c_i$ 序列之后，再处理进位即可得到答案。对比这两种做法：
– 顺序求解 $c_i$ 的过程相当于集中计算 $c_i$ ；
– 而方法二相当于每对 $(a_i, b_j)$ ，对 $c_{i + j}$ 算贡献（注意这里的 $a_i$ 并不是题目中的 $num_1[i]$ ， $a_i$ 下标越小，代表的位权越小，而 $num_1[i]$ 下标越小，代表的位权越大);

它们的本质是一样的，并且时间复杂度都是 $O(max$ { $(n,m)^2$ }，我们在仔细观察 $c_i$ 的形式：