面試題:寫一個函式處理「大數相加」——所謂大數,是指超出整數、長整數等常規型別表示範圍的數字。實作語言不限。
這題的關鍵不在語法,而在能不能想到「用什麼存」以及「怎麼模擬手算豎式」。
Number 的安全整數上限是 2^53-1(約 9007 兆),超過就會失真。最簡單可行的方案是用字串保存——字串長度理論上沒有上限,而且天生適合逐位元處理。
確定用字串之後,題目就明朗了:
為了讓「從低位開始」變得方便,可以先把字串反轉,這樣索引 0 就是個位。
var strAdd = function (srcA, srcB) {
var i, temp, tempA, tempB, len, lenA, lenB, carry = 0;
var res = [], arrA = [], arrB = [], cloneArr = [];
arrA = srcA.split('');
arrB = srcB.split('');
arrA.reverse();
arrB.reverse();
lenA = arrA.length;
lenB = arrB.length;
len = lenA > lenB ? lenB : lenA;
// 兩邊都有的部分
for (i = 0; i < len; i++) {
tempA = parseInt(arrA[i], 10);
tempB = parseInt(arrB[i], 10);
temp = tempA + tempB + carry;
if (temp > 9) {
res.push(temp - 10);
carry = 1;
} else {
res.push(temp);
carry = 0;
}
}
// 較長字串的剩餘部分
cloneArr = lenA > lenB ? arrA : arrB;
for (; i < cloneArr.length; i++) {
tempA = parseInt(cloneArr[i], 10);
temp = tempA + carry;
if (temp > 9) {
res.push(temp - 10);
carry = 1;
} else {
res.push(temp);
carry = 0;
}
}
// 別忘了最高位可能還有進位
if (carry) res.push(carry);
return res.reverse().join('');
};
原版少寫了最後那個 if (carry) res.push(carry);,這代表 999 + 1 會得到 000 而不是 1000——這是最容易漏掉的分支,值得特別留意。
s.charCodeAt(i) - 48 比 parseInt 快得多,因為不用解析整段字串。function bigAdd(a, b) {
var i = a.length - 1, j = b.length - 1, carry = 0, out = [];
while (i >= 0 || j >= 0 || carry) {
var sum = carry + (i >= 0 ? +a[i--] : 0) + (j >= 0 ? +b[j--] : 0);
out.push(sum % 10);
carry = sum > 9 ? 1 : 0;
}
return out.reverse().join('');
}
用一元正號把字元轉數字,並以 while 條件一次涵蓋「兩邊都沒了但還有進位」的情況,就不需要拆成兩個迴圈。
補充:原始面試題其實有提示「用字串保存大數」,難度已經被降低過。若沒有這個提示,能否自行想到,才是真正的篩選點。