如果笔记

如果笔记

做有价值的技术笔记

【算法第4期】大整数相乘(LeetCode 43)

在 JS 里,除大整数类型外,能被**安全使用**的最大整数是 2^53,也就是 9007199254740992。当强行使用大于这个数的整数时,就有可能会出现失真,不安全。看下面的例子: ```javascript console...

在 JS 里,除大整数类型外,能被**安全使用**的最大整数是`2^53`,也就是 9007199254740992。当强行使用大于这个数的整数时,就有可能会出现失真,不安全。看下面的例子: ```javascript console.log(9007199254740992) console.log(9007199254740993) console.log(9007199254740994) console.log(9999999999999992) console.log(9999999999999993) console.log(9999999999999994) // 以上代码输出如下: 9007199254740992 9007199254740992 9007199254740994 9999999999999992 9999999999999992 9999999999999994 ``` 可以看到,9007199254740993 和 9999999999999993 失真了。 所以,较大整数的运算尤其是两数相乘,就需要特殊处理,否则很可能就超过了这个安全上限。 > 其实现在 JS 里已经有大整数类型 BigInt,使用它时用常规运算符就能安全计算,本文就不讲了 要使用普通的整数类型完成安全计算,需要把数字表示成单个数字组成的数组,例如 12306 应该表示成`[1,2,3,0,6]`。这样按照中国大陆小学阶段教的运算步骤就能实现无限大(别抬杠。。)的整数运算。 回忆回忆小学的两数相乘步骤,直接上代码吧: ```javascript function bigIntMultiply(a, b) { const bCount = b.length let res = [] for (let i = a.length, aOffset = 0; i--; aOffset++) { for (let j = bCount, bOffset = 0; j--; bOffset++) { res = bigIntAdd(res, num2arr(a[i] * b[j]), aOffset + bOffset) } } return res } // 把一个整数转换成 [1, 2, 3, 0, 6] 这样的数组 function num2arr(num) { return String(num).split('').map(Number) } function bigIntAdd(a, b, offset = 0) { let i = a.length - offset let j = b.length let sum = 0 let res = a.slice(i) while (i > 0 || j > 0) { i--, j-- if (i > -1) { sum += a[i] } if (j > -1) { sum += b[j] } if (sum > 9) { res.unshift(sum % 10) sum = 1 } else { res.unshift(sum) sum = 0 } } sum && res.unshift(sum) return res } ``` 有了上面的算法,就可以完成 LeetCode 43: ```javascript var multiply = function (num1, num2) { if (num1 === '0' || num2 === '0') return '0' return bigIntMultiply(num2arr(num1), num2arr(num2)).join('') } ``` --- 下期预告:超级回文(LeetCode 906)

算法

hahaboy