[LeetCode] 66. 加一

[Animenzzzz]

题目描述：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

解题思路：首先考虑一种情况，如果末尾不是9，直接在操作最后一个数就好（其实可以不考虑这种情况，不过好像这样耗时能短一些）；使用栈存每一次相加好的结果，因为使用栈解决了逆序问题，出栈就是正序了。最后看看最后一位是否有进位，有进位要把1加在栈顶

C++解法：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        if(digits[digits.size() - 1] != 9){
            int tmp = digits.back();
            tmp++;
            digits.pop_back();
            digits.push_back(tmp);
            return digits;
        }
        stack<int> ss;
        int jinwei = 1;
        for (int i = digits.size() - 1; i >= 0; i--)
        {
            int result = digits[i] + jinwei;
            if(result >= 10){
                jinwei = 1;
            }else{
                jinwei = 0;
            }
            ss.push(result%10);
        }
        if(jinwei) ss.push(1);
        vector<int> res;
        while (!ss.empty()){
            res.push_back(ss.top());
            ss.pop();
        } 
        return res;
    }
};