66. Plus One

题目描述

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<int> plusOne(vector<int>& digits) {
        int i, k, sum = 0, extra = 0;
        vector<int> 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<int> plusOne(vector<int>& 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;
    }
};