18 - 加一

题目

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

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

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

示例 1:

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

示例 2:

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

解答

简言之，就是一个数字，一位位变成一个数组。然后输出值需要将其加一。

也就是说，要给数组最后一位数加一。如果有进位，就一位位向前进。

变成数字再做运算

可以把数组变成字符串，变成数字，加一，再倒回去。

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
  const str = digits.join("");
  const ans_str = parseInt(str, 10) + 1 + "";
  return ans_str.split("").map(Number);
};

我觉得是可行的，但实际测下来不可行。反例：[6, 1, 4, 5, 3, 9, 0, 1, 9, 5, 1, 8, 6, 7, 0, 5, 5, 4, 3]。

在js里面，输入6145390195186705543，会自动变成6145390195186705000。

image-20190713203942672

若是输入61453901951867055会变成61453901951867060。

image-20190713203926144

因为js的最大安全整数是$2^{53}-1$，即9007199254740991。如果超过这个值，那么任何的计算都会失去精度【可能和内部靠16位存储有关】。也就是上面这些数字的显示情况。

不过查了半天发现，大于上限的数字可以用BigInt来表达：BigInt。也就是在数字后面加一个n，如1n。

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
  const str = digits.join("");
  const ans_str = BigInt(str) + 1n + "";  // 转成bigint
  return ans_str.split("").map(Number);
};

Runtime: 44 ms, faster than 99.44% of JavaScript online submissions for Plus One.

Memory Usage: 34.1 MB, less than 8.13% of JavaScript online submissions for Plus One.

bigint类似于一种特殊的类型，有别于number。因此不能和number混着计算，也不能用math的方法。简言之就是为存储而生，能做的运算也有限。

作为数组直接加一

需要进位就向前一位加一，如果没有前一位，说明是全9，那么就重新做一个数组，第一个是1，后面长度都是0

var plusOne = function(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    digits[i]++;
    digits[i] %= 10;
    if (digits[i] !== 0) {
      return digits;
    }
  }
  let arr = new Array(digits.length + 1);
  for (let i = 0; i < digits.length + 1; i++) {
    arr[i] = 0;
  }
  arr[0] = 1;
  return arr;
};

Runtime: 44 ms, faster than 99.44% of JavaScript online submissions for Plus One.

Memory Usage: 33.8 MB, less than 74.62% of JavaScript online submissions for Plus One.

整个程序分为两个部分。第一部分是判断是否需要进位。最开始想到的做法：

...
    for (let i = digits.length - 1; i >= 0; i--) {
    digits[i]++;
    if (digits[i] !== 10) {
      return digits;
    } else {
      digits[i] = 0;
    }
  }
...

但这么做的话，运行速度就会明显下降

Runtime: 64 ms, faster than 21.73% of JavaScript online submissions for Plus One.

Memory Usage: 33.7 MB, less than 94.18% of JavaScript online submissions for Plus One.

上面取余的做法，来自于题解：

作者：guanpengchn

链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-66-jia-yi-by-guanpengchn/

第二部分是需要整体多一位的做法。思路是新建一个全为0的数组，然后令第一个元素为1。

有趣的是，许多看起来装逼的写法，速度并不快。

创建全0数组

对比网址

最快的是最基础的for循环，可能是因为这是最早出来的，所以优化地最好吧。其他的新招式，看就要慢得多了。

所以在解题当中也是用了最快的做法。

第二部分可以更加优雅

第二部分的目的是做一个数组，长度加一位，第一位为1，剩下的都是0。我第一反应就是新建一个数组再赋值。

@ふたりの距离の概算 提出了两种更加优雅的做法：

digits.unshift(1);
return digits;

或者

return [1, ...digits];

感觉确实比我之前的做法要简洁直观不少！感觉很酷！

执行用时 :72 ms, 在所有 JavaScript 提交中击败了91.84%的用户

内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了44.99%的用户

测了几次，发现执行速度差不多，内存略有增加，可能是因为要全部复制一下digits数组吧。不过这样代码的可读性就好了很多。

测试代码

/**
 *
 * @param {number[]} ans：输入的answer
 * @param {number[]} target：答案
 * @param {number} index：报错标记符
 * @returns {boolean}
 */
const ensure = (ans, target, index) => {
  const Ans = ans.toString();
  const Target = target.toString();
  if (Ans !== Target) {
    wrongMsg(ans, target, index);
    return false;
  } else {
    return true;
  }
};