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 internal library such as BigInteger.
这道题求的大数乘法，不允许用BigInteger并且不允许将num1和num2转换成int类型。
当然数据非常大，就算把num1和num2转换成int也会溢出。
虽然不允许使用BigInteger，但是可以回忆一下BigInteger。
刚开始使用了双StringBuilder，一个来存储最终结果，一个来存储每一次的乘法结果，虽然AC，但是成绩很差。
public class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
if( len1 > len2)
return multiply(num2,num1);
StringBuilder result = new StringBuilder();
StringBuilder num ;
int aa = 0, bb = 0, pos = 0;
for( int i = len1-1; i>=0;i--){
if( num1.charAt(i) == 0)
continue;
aa = 0;
num = new StringBuilder();
for( int j = len2-1; j>=0 ; j--){
if( num1.charAt(i) == 1){
num.append(num2);
break;
}
num.insert(0,((num2.charAt(j)-'0')*(num1.charAt(i)-'0')+aa)%10);
aa = ((num2.charAt(j)-'0')*(num1.charAt(i)-'0')+aa)/10;
}
if(aa > 0)
num.insert(0, aa);
bb = 0;
for( int k = num.length()-1 ; k>=0;k--){
pos = num.length()-k+len1-2-i;//从右往左数第pos位
pos = result.length()-1 - pos;//第pos位
if( pos < 0 ){
while( pos < 0 ){
result.insert(0, num.charAt(k)-'0'+bb);
bb = 0;
pos++;
}
}
else{
int cc = (num.charAt(k)-'0') + (result.charAt(pos)-'0') + bb;
result.replace(pos, pos+1, String.valueOf(cc%10));
bb = cc/10;
}
}
if( bb > 0){
if( pos == 0 )
result.insert(0, String.valueOf(bb));
else if( pos > 0)
result.replace(pos-1, pos, String.valueOf(result.charAt(pos-1)-'0'+bb));
}
}
for( int i = 0; i< result.length() ; i++){
if( result.charAt(i) == '0'){
result.delete(i,i+1);
i--;
}else
break;
}
if( result.length() == 0)
return "0";
return result.toString();
}
}
然后将StringBuilder转变成int[]：
1。因为一个n位数与一个m位数相乘，最多为m+n位数
2。另一个n位数同样的与一个一位数相乘。那么最多为n+1位数。
这样做避免了对对象的多次操作，提高了速度，但是结果仍旧不是很理想。
public class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
if (len1 > len2)
return multiply(num2, num1);
int[] res = new int[len1+len2];
int pos = 0, aa =0;
for( int i =len1-1; i>=0;i--){
if (num1.charAt(i) == '0')
continue;
aa = 0;
for( int j = len2-1; j>=0; j--){
pos = j+1+i;
int mi = (num2.charAt(j) - '0')*(num1.charAt(i) - '0') + aa + res[pos];
res[pos] = mi%10;
aa = mi/10;
}
if (aa > 0)
res[pos-1] =res[pos-1]+ aa;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < res.length; i++) {
if( !(res[i] == 0 && result.length() == 0))
result.append(res[i]);
}
if( result.length() == 0)
return "0";
return result.toString();
}
}
最后在查找了资料发现，jvm启动时间影响太大，同样的代码运行的时间也会不一样，因此不再纠结于代码速度达到最快。
相比于上一次，最后还是有了一些微调，主要就是进位的操作放在最后一次进行，这大量减少了操作次数，也就提高了运行时间。
public class Solution {
public static String multiply(String num1, String num2) {
int len1 = num1.length() ,len2 = num2.length();
int[] Num2 = ToInt(num2);
int[] res = new int[len1+len2];
for( int i =len1-1; i>=0;i--){
add(num1.charAt(i)-'0',Num2,res,i);
}
for( int i = len1+len2-1,b = 0;i>=0;i--){
int a = res[i] + b;
res[i] = a%10;
b = a/10;
}
StringBuilder result = new StringBuilder();
for(int i = 0;i< res.length;i++){
if( res[i]!= 0 ){
while( i<res.length){
result.append(res[i]);
i++;
}
}
}
if( result.length() == 0)
return "0";
return result.toString();
}
public static void add(int num,int[] num1,int[] res,int pos){
for( int i =num1.length-1 ; i >=0;i--){
res[i+pos+1] += num*num1[i];
}
}
public static int[] ToInt(String num){
int[] res = new int[num.length()];
for( int i =0;i<num.length(); i++){
res[i] = num.charAt(i)-'0';
}
return res;
}
}