算法题二

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.

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.

其实这道题的主要考点就是：加法进位

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  
{
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        vector<int> res(digits.size(), 0);
        int sum = 0;
        int one = 1; 
        
        for(int i = digits.size()-1; i >= 0; i--)
        {
            sum = one + digits[i];
            one = sum / 10;          
            res[i] = sum % 10;
        }
        
        if(one > 0)
        {
            res.insert(res.begin(),one);
        }
        
        return res;
    }
};