leetcode66:加一
Opened this issue · 1 comments
wangyewei commented
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/plus-one
wangyewei commented
思路和算法
当对数组digits加1时,只需要关注数组末尾出现几个9即可。那么可以考虑一下三种情况。
- 当末尾没有9,直接加一返回,如
[1, 2, 3]
返回[1, 2, 4]
- 当末尾有9时,我们只需要重末尾往前找到不为9的元素加一,其后所有9置0,如
[1, 2, 3, 9, 9 ,9]
返回[1, 2, 4, 0, 0, 0]
- 当数组全是9时,只需要构造一个长度比digits大1的数组,其首位元素置1,其余置0,如
[9, 9, 9 , 9]
返回[1, 0, 0, 0, 0]
算法
对数组 digits 进行一次逆序遍历,找出第一个不为 99的元素,将其加一并将后续所有元素置零即可。如果 digits 中所有的元素均为 9,那么对应着「思路」部分的第三种情况,我们需要返回一个新的数组
代码
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
for(let i = digits.length -1; i >= 0 ; i--){
if(digits[i] != 9) {
digits[i]++
return digits
}
digits[i] = 0
}
// 如果循环完还是没有返回说明数组中全是9
let newArr = new Array(digits.length + 1).fill(0)
newArr[0] = 1
return newArr
};
复杂度分析
-
时间复杂度:O(n),其中 nn 是数组 digits 的长度。
-
空间复杂度:O(1)。返回值不计入空间复杂度