使用 Karatsuba 算法与 Python 相乘字符串-Leetcode
Multiply strings-Leetcode using Karatsuba algorithm with Python
给定两个表示为字符串的非负整数 num1 和 num2,return num1 和 num2 的乘积,也表示为字符串。
示例 1:
Input: num1 = "2", num2 = "3"
Output: "6"
示例 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
注:
num1 和 num2 的长度都小于 110。
num1 和 num2 都只包含数字 0-9。
num1 和 num2 都不包含任何前导零,数字 0 本身除外。
您不得使用任何内置的 BigInteger 库或将输入直接转换为整数。
解决这个问题有很多不同的方法。其中之一是使用 Karatsuba algorithm。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if len(num1)==1 or len(num2)==1:
return str(int(num1)*int(num2))
m=max(len(num1),len(num2))
m2=m//2
num1=int(num1)
num2=int(num2)
a=num1//10**m2
b=num1%10**m2
c=num2//10**m2
d=num2%10**m2
z0=self.multiply(str(b),str(c))
z1=self.multiply(str(a+b),str(c+d))-a*c-b*d
z2=self.multiply(str(a), str(c))
return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)
应用的伪代码是正确的,但代码由于字符串和整数之间的重复转换而受到影响。我可以做些什么来改进它?这是解决这个问题的正确方法吗?提前致谢
这是对我有帮助的参考资料link-https://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/
class Solution:
def multiply(self, num1: str, num2: str) -> str:
def mul(num1, num2):
if len(num1) == 1 or len(num2) == 1:
return int(num1) * int(num2)
m = min(len(num1), len(num2)) // 2
a, b = num1[:len(num1) - m], num1[len(num1) - m:]
c, d = num2[:len(num2) - m], num2[len(num2) - m:]
z0 = mul(b, d)
z2 = mul(a, c)
z1 = mul(str(int(a) + int(b)), str(int(c) + int(d))) - z2 - z0
return (10 ** (2 * m)) * z2 + (10 ** m) * z1 + z0
return str(mul(num1, num2))
原来我也是问同样问题的人,后来想通了就把解决方法贴出来
给定两个表示为字符串的非负整数 num1 和 num2,return num1 和 num2 的乘积,也表示为字符串。
示例 1:
Input: num1 = "2", num2 = "3"
Output: "6"
示例 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
注:
num1 和 num2 的长度都小于 110。 num1 和 num2 都只包含数字 0-9。 num1 和 num2 都不包含任何前导零,数字 0 本身除外。 您不得使用任何内置的 BigInteger 库或将输入直接转换为整数。
解决这个问题有很多不同的方法。其中之一是使用 Karatsuba algorithm。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if len(num1)==1 or len(num2)==1:
return str(int(num1)*int(num2))
m=max(len(num1),len(num2))
m2=m//2
num1=int(num1)
num2=int(num2)
a=num1//10**m2
b=num1%10**m2
c=num2//10**m2
d=num2%10**m2
z0=self.multiply(str(b),str(c))
z1=self.multiply(str(a+b),str(c+d))-a*c-b*d
z2=self.multiply(str(a), str(c))
return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)
应用的伪代码是正确的,但代码由于字符串和整数之间的重复转换而受到影响。我可以做些什么来改进它?这是解决这个问题的正确方法吗?提前致谢
这是对我有帮助的参考资料link-https://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/
class Solution:
def multiply(self, num1: str, num2: str) -> str:
def mul(num1, num2):
if len(num1) == 1 or len(num2) == 1:
return int(num1) * int(num2)
m = min(len(num1), len(num2)) // 2
a, b = num1[:len(num1) - m], num1[len(num1) - m:]
c, d = num2[:len(num2) - m], num2[len(num2) - m:]
z0 = mul(b, d)
z2 = mul(a, c)
z1 = mul(str(int(a) + int(b)), str(int(c) + int(d))) - z2 - z0
return (10 ** (2 * m)) * z2 + (10 ** m) * z1 + z0
return str(mul(num1, num2))
原来我也是问同样问题的人,后来想通了就把解决方法贴出来