关注Java领域相关技术 记录有趣的事情

LeetCode-43. 字符串相乘

US-B.Ralph
US-B.Ralph
2020-08-13

问题地址

LeetCode每日一题/2020-08-13

LeetCode43. 字符串相乘


问题描述

规则

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

示例1

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

示例2

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

提示

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

解析

解题思路

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

  • 如果n1和n2之中有1个是0,则返回结果0;
  • 如果n1=1则返回n2,如果n2=1则返回n1;
  • 竖式乘法计算过程:
    竖式乘法计算过程

    1. 多位数(A)在上,少位数(B)在下;
    2. 用下边因数的个位数分别与上边因数的每一位数相乘,在计算的过程中任何一位数的乘积满十,需要进位,然后继续与上边因数的下一位数相乘;
    3. 以此类推分别使用下边因数的十位数、百位数…与上边因数的每一位数相乘,所不同的是,除下边因数的个位数与上边因数的乘积不需要补0外,其它位数均需根据位数递增补0,如上图中黄色背景所示;
    4. 将每次乘得的数相加即可;

复杂度分析

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

定位问题

  1. 使用B的每一位与A的每一位相乘,结果存如字符数组中;
  2. 第一步计算结果求和;

数据操作分析

  1. 遍历数字A,得出A的每一位与数字B的乘积;
  2. 遍历第一步中得出的结果并与上一步的计算结果求和;

编码实现

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. 做加法
  • 思路:
    1. 如果num_1num_2之一是 0,则直接将 0 作为结果返回即可。
    2. 如果num_1num_2都不是 00,则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加。这道题中,被乘数是num_1,乘数是num_2
    3. 需要注意的是,num_2除了最低位以外,其余的每一位的运算结果都需要补0。
      竖式乘法思路
  • 复杂度分析:
    • 时间复杂度:O(mn+n^2),其中 m 和 n 分别是num_1num_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_1num_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();
    }
}
  1. 做乘法
  • 思路:
    方法一的做法是从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加,整个过程中涉及到较多字符串相加的操作。如果使用数组代替字符串存储结果,则可以减少对字符串的操作。
    令 m 和 n 分别表示num_1num_2的长度,并且它们均不为0,则num_1num_2的乘积的长度为m+n-1或m+n。简单证明如下:

    • 如果num_1num_2都取最小值,则 num_1=10^{m-1}num_2=10^{n-1}num_1 × num_2=10^{m+n-2},乘积的长度为 m+n-1;
    • 如果num_1num_2都取最大,则num_1=10^{m}-1num_2=10^{n}-1num_1 × num_2=10^{m+n}-10^{m}-10^{n}+1,乘积显然小于10^{m+2}大于10^{m+n-1},因此乘积的长度为m+n;

由于nm_1nm_2的乘积的最大长度为m+n,因此创建长度为m+n的数组ansArr用于存储乘积。对于任意0<=i<=m0<=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)×B(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的形式:

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

它揭示了多项式乘法的另一面:c_i序列其实是a_i序列和b_i序列的卷积,即:

\vec{c}=\vec{a}*\vec{b}

至此,我们就可以用一种叫做快速傅立叶变换(Fast Fourier Transform,FFT)的方法来加速卷积的计算,使得时间复杂度降低到 O(clogc),这里 c 是不小于 n + m 的最小的 2 的整数幂。由于这个方法并不在面试的考纲范围内,感兴趣的同学可以自行学习。

US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 3 =