Multiply Strings 大数乘法
发布时间:2020-12-14 01:43:03 所属栏目:大数据 来源:网络整理
导读:Given two numbers represented as strings,return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. Converting the input string to integer is? NOT ?allowed. You should? NOT ?use inter
Given two numbers represented as strings,return multiplication of the numbers as a string. Note:
假设有: ? ? ? ?4 5 6 7 2 * ? ? ? ? ? ? ?5 ?4 ------------------ ? ? ?1 8 2 6 8 8 ?(4与45672相乘) ? 2 2 8 3 6 0 ? ? ? ( 5与45672相乘) 最后将相乘后的结果相加,可得 2466288。 所以,我们事先一个1位数与多位数的简单乘法和大数加法就可以实现大数乘法的。 在这里,介绍一个更加简单容易实现的方法。 从右到左,对每个数字pair做乘法,然后将相乘后的结果加在一起。 num1 [ i ] 和 num2 [ j ] 的相乘结果将会被放置在 新数组的 i + j 位 (放置进位信息) 和 i + j + 1位。 运行时间:
代码:
public class MultiplyStrings { public String multiply(String num1,String num2) { int m = num1.length(),n = num2.length(); int[] pos = new int[m + n]; for (int j = n - 1; j >= 0; j--) { for (int i = m - 1; i >= 0; i--) { int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); int p1 = i + j,p2 = i + j + 1; int sum = mul + pos[p2]; pos[p1] += sum / 10;//save as carry pos[p2] = sum % 10; } } StringBuilder sb = new StringBuilder(); for (int p : pos) { if (p != 0 || sb.length() != 0) { sb.append(p); } } return sb.length() == 0 ? "0" : sb.toString(); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |