066.md

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.

题意：用一个数组表示一个数，对该数加一用数组的形式返回。

如[9,9]表示 99，要对这个数加上1，输出结果为[1,0,0]。

思路

使用一个bool值初始化为 carry=false 记录是否需要进位。

将数组从后往前遍历，如果是9说明下一位要加1，将当前位置为0，carry置为true。

继续处理下一位，如果为9同上面一样处理，如果不为9则将改位的值加1，置carry的值为false.

如果遍历了整个数组 carry仍然为true，表示整个数组原来存的值都是9，循环一边之后整个数组已经变为0了，将最高位置为1，后面push_back(0)。

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int sz = digits.size();
        int i = sz-1;
        bool carry = false;//是否需要进位
        //从最低位往最高位扫描
        while(i>=0){
            //等于9需要进位
            if(digits[i]==9){
                digits[i--] = 0; 
                carry = true;
            }else{
                digits[i--]++;
                //不需要增加位数
                carry = false;
                break;
            }
        }
        //0~n个9的数，将最高位置为1，最后加上0.
        if(carry){
            digits[0] = 1;
            digits.push_back(0);
        }
        return digits;
    }
};