「66. 加一」题解

4/22/2021 LeetCodeAlgorithm

# 66. 加一

# 题目描述

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

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

你可以假设除了整数 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 之后再裂变为数组,于是我得到了下面这一版代码:

/**
 * @param {number[]} digits
 * @return {number[]}
 */
//不能AC
var plusOne = function (digits) {
  let num = Number(digits.join(""));
  num++;
  return num.toString().solit("");
  //等价于 return (1+Number(digits.join(''))).toString().split('')
};

很不幸的是,这个版本的代码不能 AC,因为测试用例中有数据超过了 Number 所能表示的最大值,溢出了。但这就完了吗?不,既然思路没有问题,而是数据类型溢出了,那我们就改变数据类型吧。在 ES10 中,增加了一种基本数据类型 BigInt,它的数据范围更大。所以我们可以使用它来优化上面的代码。

var plusOne = function (digits) {
  let num = BigInt(digits.join("")) + 1n;
  //1 默认是number类型,加上n缀代表BigInt类型。
  return num.toString().solit("");
};
var plusOne = function (digits) {
  //使用 bigint 解决溢出问题
  return (BigInt(digits.join("")) + 1n).toString().split("");
  //一行代码解决
};

# 方法二:直接作为数组加一

从尾至头,将每一位看作数字的数位,那么有可能有产生以下三种情况:

  1. 末位加一后无进位,直接返回;
  2. 末位加一后有进位,但是进位到中间位置便停止了
  3. 末位加一后,一直进位,导致最高位之前多出来了一位。

简而言之就是思考两个问题:

  1. 是否产生进位?
  2. 产生进位后是否导致高位+1?

那么要解决这两个问题就需要分别处理它们,关于一直进位,可以使用 for 循环,同时需要判断中途是否进位停止;关于进位后导致高位+1 的情况,可以新建数组,或者从数组头部压入一位数。

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 = 1; i < digits.length + 1; i++) {
    arr[i] = 0; //数组填充0
  }
  arr[0] = 1; //最高位置1
  return arr;
};

上边的代码是纯原始的写法,下面我们可以使用 JavaScript API 来优化代码,提升代码的可读性。

var plusOne = function (digits) {
  //数组遍历+新建数组
  const len = digits.length;
  for (let i = len - 1; i >= 0; i--) {
    digits[i]++;
    digits[i] %= 10;
    if (digits[i] != 0)
      //判断进位是否停止
      return digits;
  }
  //长度改变时新建数组并填充0
  digits = new Array(len + 1).fill(0);
  digits[0] = 1;
  return digits;
};
var plusOne = function (digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    digits[i]++;
    digits[i] %= 10;
    if (digits[i] !== 0) {
      //判断进位是否停止
      return digits;
    }
  }
  digits.unshift(1);
  //等价于 digits=[1,...digits]
  return digits;
};

以上就是本题的所有题解啦,感谢你能看到这里,如果本文对你有所帮助的话,别忘了给一个 Star 嗷~ 如果你对题解中的代码有不一样的优化意见,也欢迎你在 issue 中指出~ 最重要的是不要忘了点点关注嗷(Github (opens new window)力扣 (opens new window)),以便获取我最新的题解以及文章通知。

# 参考

# 全部代码

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 *
 * https://leetcode-cn.com/problems/plus-one/description/
 *
 * algorithms
 * Easy (45.69%)
 * Likes:    674
 * Dislikes: 0
 * Total Accepted:    279.5K
 * Total Submissions: 611.8K
 * Testcase Example:  '[1,2,3]'
 *
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
 * 
 * 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
 * 
 * 你可以假设除了整数 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 
 * 0 
 * 
 * 
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
    //使用 bigint 解决溢出问题
    return (BigInt(digits.join("")) + 1n).toString().split('');
};
// @lc code=end
var plusOne = function (digits) {
    //数组遍历+新建数组
    const len = digits.length;
    for (let i = len - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if (digits[i] != 0)
            //判断进位是否停止
            return digits;
    }
    //长度改变时新建数组并填充0
    digits = new Array(len + 1).fill(0);
    digits[0] = 1;
    return digits
};

var plusOne = function (digits) {
    //使用unshift()方法
    for (let i = digits.length - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if (digits[i] != 0)
            return digits;
    }
    digits.unshift(1);
    //长度改变时只从数组头部添加一位1
    return digits
};

var plusOne = function (digits) {
    //使用 bigint 解决溢出问题
    return (BigInt(digits.join("")) + 1n).toString().split('');
};