了解JavaScript的BigInt:加一 | 刷题打卡

题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

思路分析

一开始我就错了：现将数组遍历转换为字符串，再将字符串转换为数字 + 1，最后再转换为字符串分割为数组。想法很天真，现实很残酷：大数的计算也会存在精度丢失！！！ 比如， 输入 [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3],经过我的逻辑处理完毕之后，结果变成了[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,0,0,0]。原因在于 JavaScript 的数遵循 双精度IEEE 754 64位浮点 规范,取值范围为-2^53 至2^53-1 ,即[-(Math.pow(2,53)-1), Math.pow(2,53)-1]。当我们在控制台输入9999999999999999时，可能您会得到10000000000000000……

好在'皇天不负有心人'，ES10 中引入了新的数据类型--BigInt，顾名思义就是大整型，BigInt 是一种内置对象，它提供了一种方法来表示大于 2^53 - 1 的整数。于是就有了以下暴力解法。

AC 代码

暴力解法

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    let num = BigInt(digits.join(''))
    return String(num + BigInt(1)).split('')
};

// 社区天秀写法
// return [...`${BigInt(digits.join("")) + 1}`].map(item => +item);


// @lc code=end

// 111/111 cases passed (80 ms)
// Your runtime beats 80.92 % of javascript submissions
// Your memory usage beats 70.4 % of javascript submissions (37.8 MB)

逻辑法

按照题干的意思，我们可以这么理解，可以分为两种情况来讨论：

① 末位数为 0-8 ， 直接 +1 即可。 如 [1,2,3] ==> [1,2,4]；
② 末位数为 9 ， 则替换为 0,如果前一位也是 9 ，继续替换为 0,直到所有补位完成，如 [7,8,9] ==> [7,9,0]，[9,9,9] ==> [1,0,0,0]

因此，我们可以从右至左遍历，从末位开始，如果不等于 9 则 ++ ；前一位如果等于 9 则替换为 0 ；如果所有的数都判断完毕仍有等于 9 的，也就是说类似于 [9,9,9] 的情况，则首位补一个 1。 代码实现如下：

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i = digits.length - 1;i >= 0; i--) {
        if(digits[i] !== 9 ) {
            digits[i] ++ 
            return digits
        } 
        digits[i] = 0;
      
    }
    return [1,...digits]
};
// @lc code=end

// 111/111 cases passed (80 ms)
// Your runtime beats 80.92 % of javascript submissions
// Your memory usage beats 51.74 % of javascript submissions (37.9 MB)

递归法

根据上面分析的逻辑，我们还可以使用递归的方法来实现,用 start 和 end 分别标记起始位置，start 从 0 开始， end 从数组最后一个元素开始，直至所有的元素被处理完毕,递归就结束，有点变相循环的感觉：

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  recursion(digits, 0, digits.length - 1);
  return digits;
};
recursion = (digits, start, end) => {
  if (digits[end] !== 9) {
    digits[end]++;
    return;
  }
  digits[end] = 0;
  if (start === end) {
    digits.unshift(1);
  } else {
    recursion(digits, start, end - 1);
  }
};
// @lc code=end

// 111/111 cases passed (92 ms)
// Your runtime beats 26.83 % of javascript submissions
// Your memory usage beats 55.09 % of javascript submissions (37.9 MB)

数学法

利用 %10 的特性来判断加一之后的数是否是0并给前一位加1：

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  recursion(digits, 0, digits.length - 1);
  return digits;
};
recursion = (digits, start, end) => {
  digits[end] = (digits[end] + 1) % 10;
  if (digits[end]) {
    return;
  }
  if (start === end) {
    digits.unshift(1);
  } else {
    recursion(digits, start, end - 1);
  }
};
// @lc code=end

// 111/111 cases passed (76 ms)
// Your runtime beats 91.53 % of javascript submissions
// Your memory usage beats 50.65 % of javascript submissions (37.9 MB)

总结

还是那就话，刷题真的可以更好地学习语言特性，这不平时基本没机会了解的 BigInt 居然在刷题中 Get 到！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看活动详情