Multiply Strings
String
, Math
Medium
Given two non-negative integersnum1
andnum2
represented as strings, return the product ofnum1
andnum2
, also represented as a string.
Example 1:
Input:
num1 = "2", num2 = "3"
Output:
"6"
Example 2:
Input:
num1 = "123", num2 = "456"
Output:
"56088"
Note:
The length of both
num1
andnum2
is < 110.Both
num1
andnum2
contain only digits0-9
.Both
num1
andnum2
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.
Analysis & Solution
九章的解法要点:
两个位数为
m
和n
的数字相乘,乘积不会超过m + n
位。乘法操作从右往左计算时,每次完成相加就确定了当前 digit. 并且是在
res[i + j + 1]
位上,需要跟当前值,进位值共同确定最终保留的digit。同一个 digit 多次修改,用
int[ ]
.
public class Solution {
public String multiply(String num1, String num2) {
if(num1 == null || num2 == null) return null;
int maxLength = num1.length() + num2.length();
int[] nums = new int[maxLength];
int i, j, product, carry;
for(i = num1.length() - 1; i >= 0; i--){
// 中间部分相当于多位数乘一位数,起始 carry 为 0
carry = 0;
for(j = num2.length() - 1; j >= 0; j--){
int a = num1.charAt(i) - '0';
int b = num2.charAt(j) - '0';
product = nums[i + j + 1] + a * b + carry;
nums[i + j + 1] = product % 10;
carry = product / 10;
}
// 循环结束,最左面为当前最高位数,如果 carry 还有就设过去
nums[i + j + 1] = carry;
}
StringBuilder sb = new StringBuilder();
int index = 0;
while(index < maxLength - 1 && nums[index] == 0) index ++;
while(index < maxLength) sb.append(nums[index++]);
return sb.toString();
}
}
更优雅的方法 by yavinci:
基于了一个乘法特性:每个数字相乘时:
num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]
[i + j] 是进位
[i + j + 1] 是当前位
Code:
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] pos = new int[m + n];
for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
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;
pos[p2] = (sum) % 10;
}
}
StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}
Reference
https://mnmunknown.gitbooks.io/algorithm-notes/525_string_za_ti.html
https://leetcode.com/problems/multiply-strings/discuss/17608/AC-solution-in-Java-with-explanation
Last updated
Was this helpful?