题目

题目来源：力扣（LeetCode）

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

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

你可以假设除了整数 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]

思路分析

理解题意

  • 数组是非空的,且每个数组元素都是非负的
  • 每个数组元素的取值在 0~9之间
  • 我们要返回一个数组让其是原数组的最后一位加上1

加一的结果可能会有 3 中情况

  1. 数组长度不变，数组最后一位元素加一且不需要进一位，如：123 + 1 = 124；
  2. 数组长度不变，数组最后一位元素加一且需要进一位，如 129 + 1 = 130；
  3. 数组长度发生变化，长度需要加一位，数组最后一位元素加一且需要进一位，如99 + 1 = 100；

解法

  • 递归
  1. 从后往前递归遍历数组元素；
  2. 先让数组最后一个元素 +1，若不等于10则在此基础上 +1 并 return，反之则保留个位并进一，再判断倒数第二位元素 +1 是否等于10，以此类推；
  3. 我们只需要判断 digits[i] + 1 是否等于0，若等于则传入倒数第二个下标进入递归，直到 digits[i] + 1 !== 10 || i == -1结束递归。
  1. /**
  2.  * @param {number[]} digits
  3.  * @return {number[]}
  4.  */
  5. // 用算法模拟加1往前是否进位的操作逻辑
  6. var plusOne = function (digits) {
  7.   // 找到当前数组的最后一个元素的下标
  8.   let index = digits.length - 1;
  9.   // 进入递归，传入数组，和数组的倒数第一个数
  10.   addOne(digits, index);
  11.   return digits;
  12. };
  13. function addOne(arr, index) {
  14.   // 如果数组的第一位+1，也等于10，在数组的头部插入1；例子：99+1= 100
  15.   if (index === -1) return arr.unshift(1);
  16.   // 当前个位 +1 等于10 往前进一位，个位等于0； 例子：129+1= 130
  17.   if (arr[index] + 1 === 10) {
  18.     arr[index] = 0;
  19.     addOne(arr, index - 1)
  20.   } else { //加完1 不等于10，照常加1 返回； 例子：123+1=124
  21.     arr[index] += 1;
  22.     return arr;
  23.   }
  24. }
  • 迭代 ```javascript /**
    • @param {number[]} digits
    • @return {number[]} */ var plusOne = function(digits) { const len = digits.length; for(let i = len - 1; i >= 0; i—) {
      1. digits[i]++;
      2. digits[i] %= 10;
      3. if(digits[i]!=0) return digits;
      } // 末位有进位，并且一直进位到最前方导致结果多出一位 digits = […Array(len + 1)].map(_=>0);; digits[0] = 1; return digits; };

```