今天筆試騰訊時遇到的一個手寫算法題：不用BigInteger和Long，實現(xiàn)大整數(shù)相乘。
在筆試時，時間不夠只寫了思路。結(jié)果面試時，面試官讓我當(dāng)場寫算法，有點不能接受，太久沒搞算法了，并且很多好用的api不記得名字，手寫代碼只能都自己實現(xiàn)了。硬著頭皮上，把偽代碼寫好后，面試官說讓我把代碼寫完整，細(xì)節(jié)處理都寫出來。當(dāng)時我是難以接受的，但是遇到了有什么辦法呢。只能上了。寫完之后，面試官就看代碼，不是看思路，看代碼細(xì)節(jié)，數(shù)組越界啊、int溢出啊，幸好處理的比較充分，還加了些注釋。最終勉強過了這關(guān)，只是前面沒進(jìn)入狀態(tài)，面試不太順利，讓我在試題留了電話，說回去等通知。
面試回來查了一下實現(xiàn)思路，我面試時是模擬手寫乘法的思路，用數(shù)B的每一位與數(shù)A相乘，然后把中間結(jié)果加起來。下面是我回來實現(xiàn)的，注釋的很清楚了，如果有問題，歡迎探討！
public class TestMult {
public static void main(String[] args) {
long timeStart = System.currentTimeMillis();
System.err.println("\nresult=" + getMult("99", "19"));
System.err.println("\nresult=" + getMult("99", "99"));
System.err.println("\nresult=" + getMult("123456789", "987654321"));
System.err.println("\nresult=" + getMult("12345678987654321", "98765432123456789"));
System.err.println("\ntake time: " + (System.currentTimeMillis() - timeStart));
}
public static String getMult(int bigIntA, int bigIntB) {
return getMult(String.valueOf(bigIntA), String.valueOf(bigIntB));
}
public static String getMult(String bigIntA, String bigIntB) {
int length = bigIntA.length() + bigIntB.length();
// if (length < 10) { // Integer.MAX_VALUE = 2147483647;
// return String.valueOf(Integer.valueOf(bigIntA) * Integer.valueOf(bigIntB));
// }
int[] result = new int[length]; // 保證長度足夠容納
int[] aInts = reverse(toIntArray(bigIntA)); // 將大數(shù)拆分為數(shù)組，并反轉(zhuǎn) 讓個位從0開始
int[] bInts = reverse(toIntArray(bigIntB)); // 也可以直接在轉(zhuǎn)數(shù)組時順便反轉(zhuǎn)
int maxLength = 0; // 保存中間結(jié)果的最大長度，便于后面累加的數(shù)組
int[][] tempDatas = new int[bInts.length][]; // 儲存中間已移位的結(jié)果，之后用于累加
int extra = 0; // 進(jìn)位
for (int i = 0; i < bInts.length; i++) {
int[] singleResult = new int[aInts.length]; // bigIntB中每一位與bigIntA的乘積
extra = 0; // 進(jìn)位清零，否則會影響后面結(jié)果
for (int j = 0; j < aInts.length; j++) {
int t = bInts[i] * aInts[j] + extra;
singleResult[j] = t % 10;
extra = t / 10;
}
if (extra > 0) { // 乘積最后進(jìn)位，需要拓展一位存儲extra
int[] temp = new int[aInts.length + 1];
for (int m = 0; m < singleResult.length; m++) {
temp[m] = singleResult[m];
}
temp[temp.length-1] = extra;
singleResult = temp;
}
singleResult = insertZero(singleResult, i, true); // 移位加0
print(singleResult); // 打印中間結(jié)果
tempDatas[i] = singleResult; // 保存中間結(jié)果
if (singleResult.length > maxLength) { // 獲取位數(shù)最多的中間結(jié)果
maxLength = singleResult.length;
}
}
// 將中間結(jié)果從個位開始累加
extra = 0;
for (int k = 0; k < maxLength; k++) {
int sum = extra;
for (int[] datas : tempDatas) {
if (k < datas.length) {
sum += datas[k];
}
}
result[k] = sum % 10;
extra = sum / 10;
}
if (extra > 0) { // 99*19
result[maxLength] = extra; // 在初始化result[]時，已確認(rèn)不會越界
}
// 將計算結(jié)果轉(zhuǎn)為數(shù)字字符串
StringBuilder builder = null;
for (int i = result.length - 1; i >= 0; i--) {
if (result[i] != 0 && builder == null) { // 去除高位多余的0
builder = new StringBuilder();
}
if(builder != null) {
builder.append(result[i]); // 會將結(jié)果反轉(zhuǎn)，之前為便于計算，使下標(biāo)為0的為個位
}
}
return builder.toString();
}
/**
* 將數(shù)字字符串拆解為int數(shù)組
*/
static int[] toIntArray(String bigNumberStr) {
char[] cs = bigNumberStr.toCharArray();
int[] result = new int[cs.length];
for (int i = 0; i < cs.length; i++) {
result[i] = cs[i] - '0';
}
return result;
}
/**
* 在數(shù)組插入0做偏移，例如與百位相乘時，結(jié)果需要加兩個0
*/
static int[] insertZero(int[] datas, int count, boolean hasReversed) {
if (count <= 0) {
return datas;
}
int[] result = new int[datas.length + count];
if (hasReversed) {
for (int i = result.length - 1; i >= 0; i--) {
int index = i - count;
if (index >= 0) {
result[i] = datas[index];
} else {
result[i] = 0;
}
}
} else {
for (int i = 0; i < result.length - 1; i++) {
if (i < datas.length) {
result[i] = datas[i];
} else {
result[i] = 0;
}
}
}
return result;
}
/**
* 數(shù)組反轉(zhuǎn)
*/
static int[] reverse(int[] datas) {
for (int i = 0; i < datas.length / 2; i++) {
int temp = datas[i];
datas[i] = datas[datas.length - i - 1];
datas[datas.length - i -1] = temp;
}
return datas;
}
/**
* 打印數(shù)組
*/
static void print(int[] datas) {
for (int i = 0; i < datas.length; i++) {
System.out.print(datas[i] + ", ");
}
System.out.println();
}
}
運算結(jié)果
評論中那位童鞋提供了一個算法，與我的思路是一樣的，只不過我的實現(xiàn)把中間結(jié)果也記錄下來，處理稍顯麻煩。我把這個算法整理了一下，下面就貼出優(yōu)化過后的實現(xiàn)。上面的算法作為我面試時的一個過程記錄，我就暫且保留著，23333
伸手黨接好咯：
public class TestMulti {
public static void main(String[] args) {
long timeStart = System.currentTimeMillis();
System.err.println("\nresult=" + getMult("99", "19"));
System.err.println("\nresult=" + getMult("99", "99"));
System.err.println("\nresult=" + getMult("123456789", "987654321"));
System.err.println("\nresult=" + getMult("12345678987654321", "98765432123456789"));
System.err.println("\ntake time: " + (System.currentTimeMillis() - timeStart));
}
public static String getMult(String bigIntA, String bigIntB) {
int maxLength = bigIntA.length() + bigIntB.length();
// if (maxLength < 10) { // Integer.MAX_VALUE = 2147483647;
// return String.valueOf(Integer.valueOf(bigIntA) * Integer.valueOf(bigIntB));
// }
int[] result = new int[maxLength];
int[] aInts = new int[bigIntA.length()];
int[] bInts = new int[bigIntB.length()];
for (int i = 0; i < bigIntA.length(); i++) {
aInts[i] = bigIntA.charAt(i) - '0';// bigIntA字符轉(zhuǎn)化為數(shù)字存到數(shù)組
}
for (int i = 0; i < bigIntB.length(); i++) {
bInts[i] = bigIntB.charAt(i) - '0';// bigIntB字符轉(zhuǎn)化為數(shù)字存到數(shù)組
}
int curr; // 記錄當(dāng)前正在計算的位置，倒序
int x, y, z; // 記錄個位十位
for (int i = bigIntB.length() - 1; i >= 0; i--) {
curr = bigIntA.length() + i; // 實際為 maxLength - (bigIntB.length() - i) 簡化得到
for (int j = bigIntA.length() - 1; j >= 0; j--) {
z = bInts[i] * aInts[j] + result[curr]; // 乘積 并加上 上一次計算的進(jìn)位
x = z % 10;// 個位
y = z / 10;// 十位
result[curr] = x; // 計算值存到數(shù)組c中
result[curr - 1] += y; // curr-1表示前一位，這里是進(jìn)位的意思
curr--;
}
}
int t = 0;
for (; t < maxLength; t++) {
if (result[t] != 0) {
break; // 最前面的0都不輸出
}
}
StringBuilder builder = new StringBuilder();
if (t == maxLength) { // 結(jié)果為0時
builder.append('0');
} else { // 結(jié)果不為0
for (int i = t; i < maxLength; i++) {
builder.append(result[i]);
}
}
return builder.toString();
}
}
運算結(jié)果是一樣的，不再重復(fù)貼圖。
