LeetCode(加一)

LeetCode(加一)

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：
输入：digits = [1,2,3] 输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0] 输出：[1]

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int flag = 1;                       //标记是否有进位
        for(int i=digits.size()-1;i>=0;i--)
        {
            flag = (digits[i] + 1)/10;
            digits[i] = (digits[i]+1)%10;
            if(flag == 0)                 //没有进位
                break; 
            if(i == 0)                    //最高位为9,进位一个1   
               digits.insert(digits.begin(),1);     
        }
        return digits;
    }
};

直接将数组逆序处理，只需要判断是否有进位即可
情况一：无进位
{1，2，3} 加一后没有进位
直接用flag标记没有进位，即flag = （3+1）/10 = 0
更改数组的值, (3+1)%10 = 4
判断无进位直接退出循环
情况二：有一次或者多次进位
{2,9,9} 加一后有进位
flag标记为,flag = (9+1)/10 = 1 循环继续执行
直到i=1时,flag = 0 退出循环
情况三：最高位需要进位
{9,9,9} 在情况二的基础之上 flag = 1 继续执行
那么就需要最高位进位,直接在数组头插入一个1即可