今天笔试腾讯时遇到的一个手写算法题：不用BigInteger和Long，实现大整数相乘。
在笔试时，时间不够只写了思路。结果面试时，面试官让我当场写算法，有点不能接受，太久没搞算法了，并且很多好用的api不记得名字，手写代码只能都自己实现了。硬着头皮上，把伪代码写好后，面试官说让我把代码写完整，细节处理都写出来。当时我是难以接受的，但是遇到了有什么办法呢。只能上了。写完之后，面试官就看代码，不是看思路，看代码细节，数组越界啊、int溢出啊，幸好处理的比较充分，还加了些注释。最终勉强过了这关，只是前面没进入状态，面试不太顺利，让我在试题留了电话，说回去等通知。
面试回来查了一下实现思路，我面试时是模拟手写乘法的思路，用数B的每一位与数A相乘，然后把中间结果加起来。下面是我回来实现的，注释的很清楚了，如果有问题，欢迎探讨！
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)); // 将大数拆分为数组，并反转 让个位从0开始
int[] bInts = reverse(toIntArray(bigIntB)); // 也可以直接在转数组时顺便反转
int maxLength = 0; // 保存中间结果的最大长度，便于后面累加的数组
int[][] tempDatas = new int[bInts.length][]; // 储存中间已移位的结果，之后用于累加
int extra = 0; // 进位
for (int i = 0; i < bInts.length; i++) {
int[] singleResult = new int[aInts.length]; // bigIntB中每一位与bigIntA的乘积
extra = 0; // 进位清零，否则会影响后面结果
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) { // 乘积最后进位，需要拓展一位存储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); // 打印中间结果
tempDatas[i] = singleResult; // 保存中间结果
if (singleResult.length > maxLength) { // 获取位数最多的中间结果
maxLength = singleResult.length;
}
}
// 将中间结果从个位开始累加
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[]时，已确认不会越界
}
// 将计算结果转为数字字符串
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]); // 会将结果反转，之前为便于计算，使下标为0的为个位
}
}
return builder.toString();
}
/**
* 将数字字符串拆解为int数组
*/
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;
}
/**
* 在数组插入0做偏移，例如与百位相乘时，结果需要加两个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;
}
/**
* 数组反转
*/
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;
}
/**
* 打印数组
*/
static void print(int[] datas) {
for (int i = 0; i < datas.length; i++) {
System.out.print(datas[i] + ", ");
}
System.out.println();
}
}
运算结果
评论中那位童鞋提供了一个算法，与我的思路是一样的，只不过我的实现把中间结果也记录下来，处理稍显麻烦。我把这个算法整理了一下，下面就贴出优化过后的实现。上面的算法作为我面试时的一个过程记录，我就暂且保留着，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字符转化为数字存到数组
}
for (int i = 0; i < bigIntB.length(); i++) {
bInts[i] = bigIntB.charAt(i) - '0';// bigIntB字符转化为数字存到数组
}
int curr; // 记录当前正在计算的位置，倒序
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]; // 乘积 并加上 上一次计算的进位
x = z % 10;// 个位
y = z / 10;// 十位
result[curr] = x; // 计算值存到数组c中
result[curr - 1] += y; // curr-1表示前一位，这里是进位的意思
curr--;
}
}
int t = 0;
for (; t < maxLength; t++) {
if (result[t] != 0) {
break; // 最前面的0都不输出
}
}
StringBuilder builder = new StringBuilder();
if (t == maxLength) { // 结果为0时
builder.append('0');
} else { // 结果不为0
for (int i = t; i < maxLength; i++) {
builder.append(result[i]);
}
}
return builder.toString();
}
}
运算结果是一样的，不再重复贴图。
网友评论