给定两个以字符串形式表示的非负整数 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) 或直接将输入转换为整数来处理.
从题目要求来看, 应该是让我们实现一个比较省内存的大数乘法, 先分享几个我在 discuss 中发现的不太切合题意的解法:
- class Solution:
- def multiply(self, num1, num2):
- """
- :type num1: str
- :type num2: str
- :rtype: str
- """ return str(eval(num1+'*'+num2))
- 这个可以说是个毫无技术含量的解法, 如果面试的时候掏出这种解法, 八成是跪了.
- 还有很多人使用了以下的解法.
- class Solution:
- def multiply(self, num1, num2):
- """
- :type num1: str
- :type num2: str
- :rtype: str
- """ dict = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
- if (num1=='0' or num2=='0'):
- return "0"
- n1 = 0
- n2 = 0
- for c in num1:
- val = dict[c]
- n1 = n1*10 + val
- for s in num2:
- val = dict[s]
- n2 = n2*10 + val
- result = n1 * n2;
- return str(result)
- 这种解法我觉得还是没有切合题意, 将注意力放在的字符串转数字上, 乘法还是使用的 *. 题目要求不能将输入直接转成数字类型, 解体人自己实现了 int 方法完成了字符串的转换, 好像是符合要求, 但有投机取巧的感觉.
- 我来分享一下我的解法, 思路很简单也很好理解, 当我们徒手计算 222*11 时我们怎么计算呢, 肯定是分解成 222+2220 来计算的, 那么我们就可以使用一个一维列表来记录计算结果 11 分解成 10+1, 第一轮计算列表的结果为 [0, 2, 2, 2], 第二轮计算后变为[2, 2+2, 2+2, 2] 计算结束. 如果需要进位的话, 进位的计算放到最后一步.
- class Solution(object):
- def multiply(self, num1, num2):
- """
- :type num1: str
- :type num2: str
- :rtype: str
- """ if num1 =="0"or num2 =="0":
- return "0"
- num1 = num1[::-1]
- num2 = num2[::-1]
- str_list = [0 for _ in range(len(num1)+len(num2))]
- for i in range(len(num1)):
- for j in range(len(num2)):
- str_list[i+j] += (int(num1[i])*int(num2[j]))
- result = ""
- up = 0
- for i in str_list:
- now = i + up
- cur = now % 10
- up = now / 10
- result += str(cur)
- begin = 0
- result = result[::-1]
- for i in result:
- if i == "0":
- begin += 1
- else:
- break
- return result[begin:]
祝大家每天开心~
来源: https://www.cnblogs.com/baiyb/p/9575349.html