【leetcode】字符串相乘

旧城等待， 2022-03-10 10:12 221阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

# 解题思路： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]

1.  长度为n1的数字和长度为n2的数字相乘，总的最长长度为n1 + n2
2.  最高位(n1 + n2 - 1)是进位所得，所以k的最大值为n1 + n2 - 2
3.  注意这是从高到低的结果，需要进行翻转  
    4 3 2 1 0
4.  注意去掉前面0的时候，注意结果为0的情况，别全部去掉了。

--------------------

# 代码 #

class Solution:
        def multiply(self, num1: str, num2: str) -> str:
            if num1 == '' or num2 == '':
                return ''
            n1, n2 = len(num1), len(num2)
            k = n1 + n2 - 2
            temp = [0] * (n1 + n2)
            for i in range(n1):
                for j in range(n2):
                    temp[k - i - j] += (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            carry = 0
            for i in range(n1 + n2):
                temp[i] += carry
                carry = temp[i] // 10
                temp[i] = temp[i] % 10
            i = n1 + n2 - 1
            while i >= 0 and temp[i] == 0:
                i -= 1
                #当结果为0的时候
                if i == 0 and temp[i] == 0:
                    return '0'
            string = ''
            while i >= 0:
                string += str(temp[i])
                i -= 1
            return string

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220310/0e612a1634cf454e93f76693e514c23f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: /images/20220310/3232f50f2bb5494bb7000cfc2382a3a5.png