题目描述

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

题目大意

用一个数组表示一个数，把这个数做加一操作。

思路

不需要flag！
从右向左，遇到9就变0，非9就加1，然后break;
digits[0]如果等于0，说明长度增加了1，则新插入一个首位，首位为1，其他位为0。

代码

#include<iostream>
#include<vector>
using namespace std;

vector<int> plusOne(vector<int> &digits)
{
    for(int i=digits.size()-1; i>=0; i--)
    {
        // 若当前位小于9，只需在当前位加一就可以结束循环了
        // 并且当前结束循环后不存在第一位进位，因此置标识符为true
        if(digits[i] < 9)
        {
            digits[i] += 1;
            break;
        }
        // 若当前数字为9，则需要向前一位进位，并且把本位置为0
        else if(digits[i] == 9)
        {
            digits[i] = 0;
        }
    }
    // digits[0]如果等于0，说明长度增加了1。
    // vector.insert(iterator loc, const TYPE &val)，
    // 表示在指定位置loc前插入值为val的元素，
    // 返回指向这个元素的迭代器,
    if(digits[0] == 0)
    {
        digits.insert(digits.begin(), 1);
    }

    return digits;
}

int main()
{
    vector<int> vec1;
    for(int i=1; i<5; i++)
    {
        vec1.push_back(i);
    }
    // 1 2 3 4
    plusOne(vec1);
    for(int i=0; i<vec1.size(); i++)
    {
        cout<<vec1[i]<<' ';
    }
    cout<<endl;
    //
    vector<int> vec2;
    for(int i=9; i>4; i--)
    {
        vec2.push_back(9);
    }
    // 9 9 9 9 9
    plusOne(vec2);
    for(int i=0; i<vec2.size(); i++)
    {
        cout<<vec2[i]<<' ';
    }
    cout<<endl;
    return 0;
}

运行结果

以上。