【LeetCode-简单】66. 加一

By 大Van家 on 2021-09-17
阅读时间 1 分钟
文章共 423
阅读量

要点:数组的遍历(正向遍历和反向遍历)

描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

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

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321

提示: 不要加直接数组转化为数字做加法再转回来

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let last = digits.length - 1

for (let i = last; i >= 0; i--) {
digits[i]++
if (digits[i] > 9){
digits[i] = 0
} else {
return digits
}
}
digits.unshift(1)
return digits
};
  • 111/111 cases passed (68 ms)
  • Your runtime beats 82.36 % of javascript submissions
  • Your memory usage beats 5.14 % of javascript submissions (38.3 MB)

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function (digits) {
var carry = 1; // 我们将初始的 +1 也当做是一个在个位的 carry
for (var i = digits.length - 1; i > -1; i--) {
if (carry) {
var sum = carry + digits[i];
digits[i] = sum % 10;
carry = sum > 9 ? 1 : 0; // 每次计算都会更新下一步需要用到的 carry
}
}
if (carry === 1) {
digits.unshift(1); // 如果carry最后停留在1,说明有需要额外的一个长度 所以我们就在首位增添一个 1
}
return digits;
};
  • 111/111 cases passed (72 ms)
  • Your runtime beats 65.82 % of javascript submissions
  • Your memory usage beats 95.49 % of javascript submissions (37.6 MB)

时间复杂度:$O(N)$

空间复杂度:$O(1)$


Tips: Please indicate the source and original author when reprinting or quoting this article.