【leetcode】3. 数组-加一

题目

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

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

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

题解

解法一

分析

此题可以理解为模拟加法。因此本题需要考虑的一点是进位问题，尤其是要考虑最高位进位。
看完题目，最近直接想方法是十进制加法，从最低位位开始加一，设数组digits长度为n，则从digits[n-1]开始加1，当gigits[n-1]+1>10,则产出进位1，逆序遍历数组digits每个元素加上上一个元素执行加法操作之后的进位c。至此，大家可能已经发现最初的被加数1，其实可以看作c=1。直接上代码。
时间复杂度：O(N)
空间复杂度：O(1)

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int c = 1;// 加1，看作最初的进位
        vector<int> ret(digits);
        for (int i = ret.size() - 1; i >= 0; i--) {
            int tmp = ret[i] + c;
            c = tmp / 10;
            ret[i] = tmp % 10;
            if (c == 0) {
                return ret;
            } // 提前返回
        }
        if (c == 1) {
            ret.insert(ret.begin(), c);// vector的非尾部插入极其耗时。
        }// 处理最高位进位
        return ret;
    }
};

解法二

分析

解法一是很常规的解法，就是模拟加法。我们仔细研究题目，会发现本题有几个特点：

1. 只加1，意味着，只有在对应的元素digits[i]是9的时候才会产生进位1
2. 产生进位之后digits[i]对应位上只能是0
   综上，我们只需要逆序遍历数组digits（这是数组长度为n）,如果索引i对应的元素是9，则置0继续遍历，不是9的则加1，直接返回，当一致遍历到i=0,切digits[0] = 9,才会在最高位产生进位，注意，此时索引1~(n-1)位上都是0。因此只需要将digits[0]设置为1，并且在数组尾部新增一个元素0即可。（有同学应该已经发现，只有digits数组是类似[9,9,9]（即所以元素都是9的时候）才会产生溢出）.
   相比解法一，少了取模和除法操作，也少了vector插入操作，耗时进一步优化。
   时间复杂度：O(N)
   空间复杂度：O(1)

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int c = 1;
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i] += 1;
                return digits;
            }
            digits[i] = 0;
        }
        digits.push_back(0);
        digits[0] = 1;
        return digits;
    }
};