# 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?
那么要解决这两个问题就需要分别处理它们,关于一直进位,可以使用 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)),以便获取我最新的题解以及文章通知。
# 参考
- 画解算法:66. 加一 (opens new window)
- 【数组】加一 (opens new window)
- JavaScript:超便捷,利用 ES10 基本类型 BigInt 来解题 (opens new window)
- 18 - 加一 (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('');
};