66. 加一
小目标:百篇题解之七,破百开源成库。关注我(Github、力扣),即可获取最新题解。
题目描述
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 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; };
以上就是本题的所有题解啦,感谢你能看到这里,如果本文对你有所帮助的话,别忘了给一个点赞三连嗷~
当然如果你对题解中的代码有不一样的优化意见,也欢迎你在评论区指出~
最重要的是不要忘了点点关注嗷(Github、力扣),以便获取我最新的题解以及文章通知。