Given two non-negative integers num1
and num2
represented as strings, return the product of num1
and num2
, also represented as a string.
Example 1:
1 2
|
Input: num1 = "2", num2 = "3" Output: "6"
|
Example 2:
1 2
|
Input: num1 = "123", num2 = "456" Output: "56088"
|
Note:
- The length of both
num1
and num2
is < 110.
- Both
num1
and num2
contain only digits 0-9
.
- Both
num1
and num2
do not contain any leading zero, except the number 0 itself.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
解法
其实就是大数相乘的算法,这里需要注意的是在每次做乘法运算时,不考虑进位问题,直接把结果存入结果数组的对应位上,最后统一处理进位问题。注意,计算从数组的尾部开始。
具体代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
class { public String multiply(String num1, String num2) { int l1 = num1.length(); int l2 = num2.length(); int[] result = new int[l1 + l2]; int k = l1 + l2 - 1; for (int j = l2 - 1; j >= 0; j--) { int kk = k; for (int i = l1 - 1; i >= 0; i--) { result[kk] += (num2.charAt(j) - '0') * (num1.charAt(i) - '0'); kk--; } k--; } for (k = l1 + l2 - 1; k >= 0; k--) { int j = result[k] / 10; result[k] = result[k] % 10; if (k >= 1) { result[k - 1] += j; } } StringBuffer s = new StringBuffer(); int i = 0; for (; i < result.length && result[i] == 0; i++) ; for (; i < result.length; i++) { s.append(result[i]); } if (s.length() == 0) { return "0"; } String res = new String(s); return res; } }
|
近期评论