LeetCode-43 字符串相乘

1. 题目

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

2. 我的AC

方法一

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        return str(int(num1) * int(num2))

方法二:大整数乘法

  • m 位乘 n 位结果最大为 m+n 位
  • 建立中间数组,第 i 位乘第 j 位的结果保存在第 i+j 位
  • 处理中间数组,个位数和进位
  • 删除高位的0
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] * (length1 + length2)
        for i in range(length1):
            for j in range(length2):  
                temp[i+j] += int(num1[i]) * int(num2[j])
    
        result = []
        for i, num in enumerate(temp):
            digit = num % 10
            carry = num / 10 
            result.insert(0, str(digit))
            if i < length1 + length2 - 1:
                temp[i+1] += carry
        while result[0] == '0' and len(result) > 1: # "9133" * "0"
            result.pop(0)   
        return "".join(result)

3. 小结

  1. 删除列表第0位
result.pop(0)   
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。