加一
问题描述
给定一个由整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
1
2
3
| 输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
|
示例 2：
1
2
3
| 输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
|
示例 3：
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
思路
从数组的最后一个元素（即整数的最低位）开始，将进位（初始为1，因为我们要加一）加到当前位上，然后更新当前位的值和进位。如果遍历完数组后还有进位（即最高位有进位），则在数组的最前面插入这个进位。这种方法避免了使用额外的数据类型（如long int或string），直接在原数组上进行操作，因此更加高效且避免了溢出问题。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int carry=1;
int n=digits.size();
for (int i = n-1; i >=0 ; --i) {
int sum=digits[i]+carry;
digits[i]=sum%10;
carry=sum/10;
if (carry==0){
return digits;
}
}
if(carry!=0){
digits.insert(digits.begin(),carry);
}return digits;
}
};
int main() {
vector<int> digits = {9,8,7,6,5,4,3,2,1,0};
Solution s;
vector<int> res=s.plusOne(digits);
for (int i = 0; i < res.size(); ++i){
cout << res[i] << " ";
}
return 0;
}
答案: 987653211
|
