43. 字符串相乘

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/multiply-strings

题目

给定两个以字符串模式示意的非负整数 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）或间接将输出转换为整数来解决。

解题思路

思路：竖式运算

首先审题，题目要求的是乘积，那么咱们能够模仿竖式乘法来计算乘积。

这里先要留神一种状况，当 num1 和 num2 任意一个为 0 时，间接返回 0。

如果 num1 和 num2 都不为 0，那么咱们能够遍历 num2 每一位和 num1 进行相乘，而后将每次相乘的后果进行累加。（这其实就是咱们竖式乘法运算的思维）如下图示：

之前咱们曾遇到过 415. 字符串相加，咱们在后续的累加的局部能够间接应用此题的思维。还有一个须要留神的，除了 num2 最低位与 num1 的运算除外，其余位与 num1 的乘积都应该补 0。

具体代码实现见【代码实现 # 竖式运算】

在下面的算法中，须要对每步计算计算的字符串进行相加的过程，屡次对字符串进行操作，会耗费性能。

在这里，咱们对竖式运算进行优化，咱们采纳数组代替字符串存储后果，防止频繁操作字符串。

先看题目前面的阐明中，第 2、3 条阐明 num1 和 num2 不存在前导 0 的状况，并且 num1 和 num2 中每位数只蕴含 0 到 9 之间的数字。在这里，咱们依据这个来确定定义数组的长度。

咱们晓得，（自然数中）只有 1 位的数字最小的是 0，最大为 9。两位数最小的是 10，最大的是 99。咱们能够发现，这里是有法则的。假如 n 为数字位数，那么当 n = 1 时，最小数字为 $0=10^{0}$，最大数字为 $9 = 10^{1}-1$；当 n = 2 时，最小数字为 $10 = 10^{2-1}$，最大数字为 $99 = 10^{2}-1$。也就说，当 n 取大于 0 的数（正整数）时，n 位数最小数为 $10^{n-1}$，最大数为 $10^{n} – 1$。

当初咱们假如，N1、N2 别离为 num1 和 num2 的长度。这里看 num1 和 num2 别离去最小值和最大值时可能的长度。

• 当 $\rm{num1}$ 和 $\rm{num2}$ 取最小值时，也就是 $\rm{num1}= 10^{N1-1}, \rm{num2}= 10^{N2-1}$，那么两者的乘积 $\rm{num1} \times \rm{num2}= 10^{N1+N2-2}$，也就说此时乘积的长度为 $N1+N2-1$；
• 当 $\rm{num1}$ 和 $\rm{num2}$ 取最大值时，也就是 $\rm{num1}= 10^{N1}-1, \rm{num2}= 10^{N2}-1$，那么两者的乘积 $\rm{num1} \times \rm{num2}= 10^{N1+N2} – 10^{N1}-10^{N2}+1$，这里咱们能够发现，两者的乘积是介于 [$10^{N1+N2-1}$, $10^{N1+N2}$] 之间的。也就说长度为 $N1+N2$

在这里，两数相乘的最大长度为两数长度之和。那么定义数组 ans 长度为 len(num1)+len(num2)。对于任意 $0\leq i <N1$ 和 $0\leq j < N2$，索引对应的数值乘积后果（最大两位数，形如 ‘ab’,’0a’ 的模式），后果第一位位于 ans[i+j] 中，第二位位于 ans[i+j+1] 中。可联合下图了解：

具体代码见【代码实现 # 竖式运算（优化）】

代码实现

# 竖式运算
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'

        ans = '0'
        N1, N2 = len(num1), len(num2)
        # 从后往前遍历 num2，与 num1 相乘
        for i in range(N2-1, -1, -1):
            carry = 0
            k = int(num2[i])
            # 补充 0
            curr = ['0'] * (N2-i-1)
            for j in range(N1-1, -1, -1):
                product = int(num1[j]) * k + carry
                carry = product // 10
                curr.append(str(product%10))
            # 确认 carry 是否不为 0，不为 0 则补充在最高位
            if carry != 0:
                curr.append(str(carry))
            # 造成字符串，放入下列求和办法中
            curr = ''.join(curr[::-1])
            ans = self.addStrings(ans, curr)
        return ans

    def addStrings(self, num1: str, num2: str) -> str:
        # 用以存储计算结果
        ans = []
        # 定义指针别离指向 num1, num2 开端
        p = len(num1) - 1
        q = len(num2) - 1
        # 存储进位
        carry = 0

        # 模仿加法运算
        # 这里将 carry 放到条件中，是思考后续计算完结后，还有进位，也就是 carry 为 1 的状况
        while p >= 0 or q >= 0 or carry:
            # 因为有可能呈现索引溢出的景象，# 当较短的字符串索引溢出时，要在头部增加 0，用以后续计算
            elem1 = int(num1[p]) if p >= 0 else 0
            elem2 = int(num2[q]) if q >= 0 else 0
            # 模拟计算，留神加上进位
            tmp = elem1 + elem2 + carry
            # 相加后果可能大于 10
            # 计算进位，并且就将后果模 10，余数增加到 ans 头部
            carry = tmp // 10
            # ans = str(tmp % 10) + ans
            ans.append(str(tmp % 10))
            # 往前持续计算
            p -= 1
            q -= 1

        return ''.join(ans[::-1])

# 竖式运算（优化）class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        N1, N2 = len(num1), len(num2)

        ans = [0] * (N1+N2)

        for i in range(N1-1, -1, -1):
            a = int(num1[i])
            for j in range(N2-1, -1, -1):
                b = int(num2[j])
                tmp  = ans[i+j+1] + a * b
                ans[i+j] += tmp // 10
                ans[i+j+1] = tmp % 10
        
        # 文章剖析了取值为最小最大时，两数乘积的长度为 N1 + N2 - 1 和 N1 + N2
        # 这里留神数组中首元素
        ans = ans[1:] if ans[0] == 0 else ans

        return ''.join(str(x) for x in ans)

实现后果

欢送关注

公众号【书所集录】