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:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

原文链接：https://leetcode.com/problems/plus-one/

---

给定一个数组，这个数组中存放的所有数字组合起来代表一个数字，例如：[1,2,3] 代表123，[9,9]代表99。需要我们将这个数组中的数字加一，并且返回加一之后的数字所代表的数组。
例如：
[1,2,3] --> 123–> 加1 --> 124 -->[1,2,4]，
[9,9] --> 99 --> 加1 --> 100 --> [1,0,0]。

---

这应该是一个比较经典的题，如果给的数组中数字比较小的话，完全可以数组先转换为原来的数字再将其加一后转换为数组。
以下代码只适合数字比较小，不合适大数，该题无法AC：

// 不适用大数
/*class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int end=digits.size();
        long long sum=0,n=1;
        vector<int> result;
        while(end--) { // 将其加起来得到原来的数字
            sum += digits[end]*n;
            n *= 10;
        }
        sum++;// plus one
        while(sum) {
            result.insert(result.begin(),sum%10);
            sum /= 10;
        }
        return result;
    }
};*/

但是数组可以很大，所以能够代表很大很大一个数字，这样int 或者 long long类型都无法表达出这个数字，所以我们只能从数组的角度来分析。这个题主要是需要考虑进位的问题，我们需要从最低位进行加一，如果不需要进位的话，则直接返回即可，这种情况很简单。

但是如果需要进位的话就需要考虑进位之后教高一位是否还需要进位，如果需要的话继续进位依次从最低位向最高位遍历计算。如果到最高为了还需要进位这就说明是：9、99、999这种特殊情况，我们需要变成：10、100、100，在最高位之前插入一个1，后面全是0即可。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i=digits.size()-1;i>=0;i--) { // 从后往前遍历
            digits[i]++;// 当前位加一
            if(digits[i]==10) {// 如果需要进位
                digits[i]=0;// 将当前位置为0
                if(i==0) // 如果是第一位并且还需要进位，则在最前面插入一个1，例如 9，99
                    digits.insert(digits.begin(),1);
            } else {//如果不进位，则直接返回加一后的数组
                return digits;
            }
        }
        return digits;
    }
};