66. Plus One

Given a **non-empty** array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

**Example 1:**

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
**Example 2:**
1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
思路:从后往前遍历,加一,满十进一,当不满十时,即可马上终止。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {

digits[digits.size() - 1] += 1;

for (int i = digits.size() - 1; i > 0; i--){

if (digits[i] > 9) {
digits[i] = 0;
digits[i - 1] += 1;
} else {
return digits;
}
}

if (digits[0] > 9){
digits[0] = 0;
digits.insert(digits.begin(), 1);
}

return digits;
}
};
Res. 0ms, Ranking 100.100%. 查了一下最快的算法,如下,采用除余与整除的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int adder = 1;
for (int i = digits.size() - 1; i >= 0; i--){
int n = digits[i] + adder;
digits[i] = n % 10;
adder = n / 10;
if (adder == 0){
break;
}
}
if (adder == 0){
return digits;
}
else{
digits.insert(digits.begin(), 1);
return digits;
}
}
};
虽然写法更为简洁,但出发和除余的操作显然会比加减更耗资源,因此上面的解法是较优解法。