LeetCode刷题-加一

加一

问题描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

样例

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

Code1

时间复杂度O(n)，空间复杂度O(1)；

vector<int> plusOne(vector<int>& digits) {
	add(digits, 1);
	return digits;
}
private:
void add(vector<int> &digits, int digit) {
	int c=digit;
	for(auto it=digits.rbegin(); it!=digits.rend(); ++it) {
		*it+=c;
		c=*it/10;
		*it%=10;
	}
	if(c>0) {
		digits.insert(digits.begin(), 1);
	}
}

Code2

时间复杂度O(n)，空间复杂度O(1)；

vector<int> plusOne(vector<int>& digits) {
	add(digits, 1);
	return digits;
}

private:
void add(vector<int> &digits, int digit) {
	int c=digit;
	for_each(digits.rbegin(), digits.rend(), [&c](int &d) {
		d+=c;
		c=d/10;
		d%=10;
	});
	if(c>0) digits.insert(digits.begin(), 1);
}