【LeetCode】43.字符串相乘--Python

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode】43.字符串相乘--Python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2894字，纯文字阅读大概需要5分钟。

内容图文

题目描述
??给定以字符串形式比表示的非负整数num1和num2，返回num1和num2的乘积的字符串形式。
??例如num1=“123”,num2=“456”
??输出：“56088”
分析
??这类涉及乘法的问题要考虑数字界限，但对于Python来说，大数完全没问题。可以直接return str(int(num1)*int(num2))，但是对于我们这些有追求的人 老实人，还是要考虑一下界限问题。思路是这样的，我们需要考虑平时手算乘法的过程，例如：

代码

def multiply(num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = list(num1)
num1 = list(map(int, num1))
num2 = list(num2)
num2 = list(map(int, num2))
len1 = len(num1)
len2 = len(num2)

以上首先把字符串转变成数字列表，“123”变[1,2,3]，并且获取每个列表的长度方便遍历。

for i in range(len1):
    partition = 0
    for j in range(len2):
        index1 = len1 - i - 1
        index2 = len2 - j - 1
        partition += num1[index1] * num2[index2] * (10 ** (len2 - index2 -1))
    num += partition* (10 ** (len1 - index1 -1))
return str(num)

以上for循环是分析中计算过程的实现，(10 ** (len2 - index2 -1)是补0的操作。另外，许多代码就在这一步return了计算出的num。但从我的角度来看，我觉得不对。以列表的方式做乘法计算，就是为了防止数字过大，而以上代码本质上还是计算了一个很大的num，然后转换成str，这和return str(int(num1)*int(num2))没什么区别。我的做法是，把每一个partition存在列表中，再把他们存在num_matrix中。那么num_matrix就是[partition_1,partition_2,…,partition_n]。partition是什么呢？例如123×456，partition1 = 456×3，partition2=456×20，partition3=456×100。最后我们得到了三个partition分别是[7,3,8],[6,1,5,0],[4,9,2,0,0]，把它们以列表的形式(没有大数)相加就是最终结果。以下是完整代码。

def multiply(num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    num1 = list(num1)
    num1 = list(map(int, num1))
    num2 = list(num2)
    num2 = list(map(int, num2))
    len1 = len(num1)
    len2 = len(num2)
    num_matrix = []
    num = 0
    for i in range(len1):
        partition = 0
        for j in range(len2):
            index1 = len1 - i - 1
            index2 = len2 - j - 1
            partition += num1[index1] * num2[index2] * (10 ** (len2 - index2 -1))
        # num += partition* (10 ** (len1 - index1 -1))
    # return str(num)
        partition = map(int,str(partition))
        for k in range(0,i):
            partition.append(0)
        num_matrix.append(partition)


    max_len = len(num_matrix[len(num_matrix) - 1])

    for i in range(len(num_matrix)):
        num_matrix[i].reverse()
        while len(num_matrix[i]) < max_len:
            num_matrix[i].append(0)
    total = [0 for i in range(max_len)]
    add = 0
    for i in range(max_len):
        for j in range(len(num_matrix)):
            total[i] += num_matrix[j][i] + add
            if add:
                add = 0
        add = total[i] / 10
        total[i] = total[i] % 10
    if add:
        total.append(add)

    total.reverse()
    total = map(str,total)
    total = ''.join(total)

    if total.count('0') == len(total):
        return '0'

    return total

if __name__ =='__main__':
    num1 = '123456789'
    num2 = '987654321'
    print multiply(num1,num2)

我的代码就像老奶奶的裹脚布，又臭又长。
最后

内容总结

以上是互联网集市为您收集整理的【LeetCode】43.字符串相乘--Python全部内容，希望文章能够帮你解决【LeetCode】43.字符串相乘--Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端