[Leetcode][python]Multiply Strings/字符串相乘

秒速五厘米 2022-06-08 14:19 160阅读 0赞

## 题目大意 ##

将两个用字符串表示的数进行乘法操作并返回字符串结果。

注意点：  
给的数是非负整数  
数字可以无穷大

## 解题思路 ##

参考：[https://shenjie1993.gitbooks.io/leetcode-python/043%20Multiply%20Strings.html][https_shenjie1993.gitbooks.io_leetcode-python_043_20Multiply_20Strings.html]

123*456
    
    100        400
     20         50
      3          6
    
    [3*6, 2*6+3*5, 1*6+2*5+3*4, 2*4+1*5, 1*4, 0]
    
    [18, 27, 28, 13, 4, 0]
    
    [8, 27+1, 28, 13, 4, 0]
    
    [8, 8, 28+2, 13, 4, 0]
    
    [8, 8, 0, 13+3, 4, 0]
    
    [8, 8, 0, 6, 5, 0]
    
    "880650"-->"056088"
    
    "56088"

## 代码 ##

class Solution(object):
        def multiply(self, num1, num2):
            """
            :type num1: str
            :type num2: str
            :rtype: str
            """
            num1 = num1[::-1]
            num2 = num2[::-1]
            length1 = len(num1)
            length2 = len(num2)
            temp = [0 for __ in range(length1 + length2)]  # 最多是length1 + length2位数
            # 将手算乘法的每列数字放入其格内
            for i in range(len(num1)):
                for j in range(len(num2)):
                    # temp[i+j]是重点
                    temp[i+j] += int(num1[i]) * int(num2[j])
            print temp
    
            ans = []
            for i in range(len(temp)):
                digit = temp[i] % 10  # 该位最后的数
                carry = temp[i] / 10  # 进位的数
                if i < len(temp)-1:
                    temp[i+1] += carry
                ans.insert(0, str(digit))  # 直接往前写，省的最后反转
            # 删去前面的所有0
            while ans[0] == '0' and len(ans) > 1:
                ans.pop(0)
            return ''.join(ans)

## 总结 ##

这题存疑，直接把str转成int，总感觉违背初衷，我还一直在思考怎么从ascii码来判断每一位的数字。

[https_shenjie1993.gitbooks.io_leetcode-python_043_20Multiply_20Strings.html]: https://shenjie1993.gitbooks.io/leetcode-python/043%20Multiply%20Strings.html