LeetCode——字符串相乘（Multiply Strings）

港控/mmm° 2022-05-14 12:25 145阅读 0赞

# 题目：     #

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

# 思路：  #

这个题目在C语言课本看到过，当时无从下手，现在再看想明白了。想弄明白这个，我们需要拆解多位数的乘法。第一步，将num2的某一位数乘num1，这里就得到了一个a1，遍历num2，就可以得到a1,a2,...,an，然后在将这些数以阶梯式相加，如果不明白什么意思，请用手算“123x123”等于多少。所以这道题的难点就是：

阶梯式相加如何加，这里我们采用算出一个ai，我们就加上一个，得出一个result字符串。

**代码**：

class Solution:
        def multiply(self, num1, num2):
            """
            :type height: List[int]
            :rtype: int
            """
            if num1 == '0' or num2 == '0':
                return '0'
            resultStr = ''
            tempStr = ''
            index1 = len(num1) - 1
            index2 = len(num2) - 1
            multNum = 0
            n1 = 0
            n2 = 0
            resultN = 0
            while index2 >= 0:#遍历num2所有数字，让每个数字乘num1
                n2 = int(num2[index2])
                index1 = len(num1) - 1
                tempStr = ''
                while index1 >= 0:
                    if index1 >= 0:
                        n1 = int(num1[index1])
                    else:
                        n1 = 1
                    resultN = n1 * n2 #得到当前两个数的运算值
                    tempMultNum = int(resultN / 10)#得到前一步计算的积/10的商，放入下一步的计算结果中
                    resultN = resultN % 10 #得到余数
    
                    resultN += multNum #加上上一次运算遗留的商
                    multNum = int(resultN / 10) #因为加上乘子，可能会超过10，所以需要再做一步除法操作
                    resultN = resultN % 10
                    multNum += tempMultNum
                    tempStr = str(resultN) + tempStr
                    index1 -= 1
                if multNum != 0:#当跳出循环，我们还要加上不为零的乘子
                    tempStr = str(multNum) + tempStr
                    multNum = 0
                if resultStr == '':
                    resultStr = tempStr
                else:
                    resultStr = self.strPlus(resultStr, tempStr,len(num2) -1 - index2)
                index2 -=1
    
            return resultStr
        
        def strPlus(self, str1, str2, bitNum):
            """
            应用于阶梯式相加，str1在上层阶梯，str2在下层阶梯
            :param str1: 
            :param str2: 
            :param bitNum: 这个是str2需要前移多少位
            :return: 
            """
            resultStr = str(str1[len(str1) - bitNum:]) #先将str1的某位数添加到结果集中
            i = len(str1) - bitNum -1 #第一个字符串索引
            j = len(str2) - 1
            multNum = 0
            n1 = 0
            n2 = 0
            resultN = 0
            while i >= 0 or j >= 0:
                if i >= 0:
                    n1 = int(str1[i])
                else:
                    n1 = 0
                if j >= 0:
                    n2 = int(str2[j])
                else:
                    n2 = 0
                resultN = n1 + n2  # 得到当前两个数的运算值
                tempMultNum = int(resultN / 10)  # 得到前一步计算的积/10的商，放入下一步的计算结果中
                resultN = resultN % 10  # 得到余数
    
                resultN += multNum  # 加上上一次运算遗留的商
                multNum = int(resultN / 10)  # 因为加上乘子，可能会超过10，所以需要再做一步除法操作
                resultN = resultN % 10
                multNum += tempMultNum
                resultStr = str(resultN) + resultStr
                j -= 1
                i -= 1
            if multNum != 0:
                resultStr = str(multNum) + resultStr
            return resultStr
    
    if __name__ =="__main__":
        res = Solution()
        print(res.multiply("9", "99"))
        #print(res.strPlus("6888", "492",2))
        pass