问题描述

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

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

大数进位问题,给一个由数组表示的数加上1,返回同样由数组表示的结果,比如:

[9 9 9] + 1 = [1 0 0 0]

思路

给数组最后一个数加1,然后判断是否大于9,大于9则进位标识为1,否则进位标识为0;往前遍历,前面的每个数都需加上进位标识,然后判断是否需要进位。

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
    	if(digits.size()==0) {
	    	return digits;
	    }
        vector<int> r(digits.size()+1);
        int i = digits.size()-1;
        int cur = 1;
        while(i>-1) {
        	int t = digits[i]+cur;
			cur = t<=9?0:1;
        	r[i+1]=t%10;
        	i--;
        }
        if(cur==1){
        	r[0] = cur;
        } else {
        	r.erase(r.begin());
        }
        return r;
    }
};