题目描述

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

思路

让个位数开始+1，判断有没有进位（也就是是否大于10），有的话前面的那一位要加一，没有的话继续往前进，直到第一位，如果这个数没进位，比如 98 -> 99。就不用特殊考虑。

如果这个数也进位了，比如99 - > 100, 那你需要设置一个额外的变量来存第一个位的值，没进位是零，有进位是1，然后将所有的值赋给新的数组。

class Solution {public:    vector
     
       plusOne(vector
      
       & digits) {        int i, k, sum = 0, extra = 0;        vector
       
         ans;        int count = 0;        int n = digits.size();        if (n == 1)        {            digits[0] = digits[0] + 1;            if (digits[0] >= 10)            {                digits[0] = 1;                digits.push_back(0);                return digits;            }            sum = extra * 10 + digits[0];            if (sum >= 1 && sum <= 9)            {                digits[0] = sum;                return digits;            }        }        k = digits[n - 1] + 1;        for (i = 1; i < n; i++)        {            if (k >= 10)            {                digits[n - i] = k % 10;                digits[n - i - 1] += 1;                if (digits[0] >= 10)                {                    extra = 1;                    digits[0] = digits[0] % 10;                }                k = digits[n - i - 1];            }            else            {                digits[n - i] = k;                k = digits[n - i - 1];            }        }        if (extra != 0)            ans.push_back(extra);        for (i = 0; i < digits.size(); i++)        {            ans.push_back(digits[i]);        }        return ans;    }};
       
      
     

简化

class Solution {public:    vector
     
       plusOne(vector
      
       & digits) {        int i, sum = 0, one = 1;//进位标识        for (i = digits.size()-1; i >= 0; i--)        {               sum = digits[i] + one;//每一次加进位后的值               digits[i] = sum % 10;//实际值            one = sum / 10;//进位        }        if (one != 0)            digits.insert(digits.begin(),one);        return digits;    }};