看到有人贴出腾讯的面试算法题, 实现大整数的乘法, 原实现臃肿低效不够优美, 忍不住自己动手写了一个
package com.vlee78.bigmul;
public class BigMul
{
public static final void main(String[] args) {
String bigInt0 = "99999999999999999999";
String bigInt1 = "9999999999999999999999";
System.out.println(bigInt0 + " x " + bigInt1 + " = " + bigMul(bigInt0, bigInt1));
}
private static final String bigMul(String bigInt0, String bigInt1)
{
int len0 = bigInt0.length();
int len1 = bigInt1.length();
int[] digits = new int[len0+len1];
for(int i=0; i<len0; i++) {
int digit0 = bigInt0.charAt(len0-i-1)-'0';
if(digit0<0 || digit0>9) return null;
for(int j=0; j<len1; j++) {
int digit1 = bigInt1.charAt(len1-j-1)-'0';
if(digit1<0 || digit1>9) return null;
add(digit0*digit1, digits, i+j);
}
}
StringBuilder sb = new StringBuilder(len0+len1);
for(int i=digits.length-1; i>=0; i--) {
if(sb.length()==0 && digits[i]==0) continue;
sb.append((char)('0'+digits[i]));
}
if(sb.length()==0) sb.append('0');
return sb.toString();
}
private static final void add(int val, int[] digits, int pos)
{
int digit = digits[pos] + val;
digits[pos] = digit%10;
if(digit>9) add(digit/10, digits, pos+1);
}
}
