BFE.devAI解答 - JavaScript 代码题
115. 实现大整数除法(BigInt)
解题思路：
大整数除法的过程类似手算除法，从被除数的最高位开始，依次做减法，求出商的当前位数字，再将余数除以除数作为下一步的被除数。
但是由于 JavaScript 对大整数的处理存在精度问题，因此我们可以采用字符串的形式来处理大整数。具体来说，我们可以采用如下的做法：
- 先将两个大整数转换为相应的数字数组，方便数位的访问和运算。
- 利用比较简单的小学奥数方法，从高位到低位模拟手算除法，依次求出商的每一位数字，并计算当前的余数。
- 如果结果为负数，则商的当前位减1，余数加上除数的绝对值。
- 最后得到的商的数字数组除以 10 就是最终的结果。
代码如下：
function divide(str1, str2) { // 将字符串反转，便于从高位到低位计算 const num1 = str1.split('').reverse().map(x => +x); const num2 = str2.split('').reverse().map(x => +x); // 判断正负号 const sign1 = num1[num1.length - 1] < 0 ? -1 : 1; const sign2 = num2[num2.length - 1] < 0 ? -1 : 1; const sign = sign1 * sign2; // 去掉正负号，转成绝对值 num1.pop(); num2.pop(); const len1 = num1.length, len2 = num2.length; // 特判除数为 0 的情况 if (len2 === 0) { throw new Error('除数不能为 0'); } // 特判被除数为零的情况 if (len1 === 0 || (len1 === 1 && num1[0] === 0)) { return '0'; } // 特判两数相等的情况 if (len1 === len2 && num1.every((digit, i) => digit === num2[i])) { return sign > 0 ? '1' : '-1'; } // 将数字数组倒序，方便从高位到低位计算 num1.reverse(); num2.reverse(); const result = []; // 存放商的每一位数字 let r = 0; // 当前的余数 // 从高位到低位模拟手算除法 for (let i = len1 - 1; i >= 0; i--) { r = r * 10 + num1[i]; // 加上上一位剩下来的余数 let q = Math.floor(r / num2[0]); // 计算商的当前位 // 如果结果为负数，则商的当前位减1，余数加上除数的绝对值 if (q < 0) { q -= 1; r += Math.abs(num2[0]); } result.push(Math.abs(q)); r %= num2[0]; } // 将商的数字数组倒序，除以10，转成字符串 const quotient = result.reverse().reduce((str, digit) => str + digit, '') || '0'; return sign > 0 ? quotient : '-' + quotient;}由于 JavaScript 对 BigInt 的支持还不够完善，因此在实现时使用了数字数组来处理大整数。例如，对于大整数 '1123456787654323456789'，我们把它转换成数字数组 [9, 8, 7, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 1, 1]，其中数组的第一项表示个位，最后一项表示最高位。这样我们就可以方便地从高位到低位访问和计算这个数了。
另外，我们在处理负数时，需要特判商的当前位小于等于 0 的情况。此时我们需要将商的当前位减 1，余数加上除数的绝对值。例如，在上面的例子中，当计算 r / num2[0] < 0 时，我们需要把商的当前位 q 减去 1，余数加上除数的绝对值 |num2[0]|。这是因为在手算除法中，计算商的当前位时是采用除数与被除数的高位项相除的方式，即如果 a >= b，则当前位的商为 $a/b$ 的整数部分。而在 JavaScript 中，整数除法采用的是取商向 0 取整的方式，即 $\lfloor a/b\rfloor$，因此需要特判这种情况。这里的实现方式非常简单，只需要检查商 q 是否小于等于 0 即可，如果是，则将其减 1，余数加上除数的绝对值即可。
时间复杂度：$O(n^2)$，其中 $n$ 为两个大整数的位数之和。具体来说，我们需要对每一位做除法，对于每个除法，都需要做一次减法和一次求商，因此总时间复杂度为 $O(n^2)$。
空间复杂度：$O(n)$，其中 $n$ 为两个大整数的位数之和。使用数字数组存储数位和结果可能需要的额外空间为 $O(n)$。