LeetCode Plus One

Plus One

Given a number represented as an array of digits, plus one to the number.

入门题。

我分为两种解法：

1 通用法，可以适用于+1到9数字的

2 特定法，稍微优化点，因为只是加1，所以，如果当前数字小于9的时候就直接加1就可以返回结果了。

两种方法都可以写出很简练的程序。

知识点：

要会根据特定情况优化算法。

下面是1 通用法的程序：

class Solution {
public:
	vector<int> plusOne(vector<int> &digits) 
	{
		if (digits.empty()) return digits;

		int carry = 1;
		for (int i = digits.size()-1; i >= 0; i--)
		{
			int sum = digits[i] + carry;
			carry = sum / 10;
			digits[i] = sum % 10;
		}

		if (carry == 1) digits.insert(digits.begin(), 1);

		return digits;
	}
};

下面是利用本题的特有性质优化的程序：

class Solution {
public:
    vector<int> plusOne(vector<int> &digits)
	{
		int i = 0;
		for (i = digits.size()-1; i >= 0; i--)
		{
			if (digits[i] >= 9) digits[i] = 0;
			else
			{
				digits[i]++;
				return digits;
			}
		}
		if (i < 0) digits.insert(digits.begin(), 1);
		
		return digits;
	}
};

//2014-1-7
	vector<int> plusOne4(vector<int> &digits) 
	{
		int n = digits.size()-1;
		while (n>=0 && digits[n] == 9) digits[n--] = 0;
		if (n>=0) digits[n]++;
		else digits.insert(digits.begin(),1);
		return digits;
	}

//2014-2-8 update
	vector<int> plusOne(vector<int> &digits) 
	{
		int i = digits.size()-1;
		for ( ; i >= 0 && digits[i] == 9; i--) digits[i] = 0;
		if (i >= 0) digits[i]++;
		else digits.insert(digits.begin(), 1);
		return digits;
	}