题目描述

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

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

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

样例

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

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

算法分析

类似高精度加法的原理

• 1、将当前数组的每个数逆序存入到链表中，且初始化t = 1
• 2、枚举所有位，将t = t + a[i]对t % 10 (10取模)的值放在当前位，将t / 10 (剩下的)放在下一位
• 3、若枚举完所有位后，t > 0，将t再次存入到下一位
• 4、将链表的元素逆序返回到一个数组中，然后返回数组

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        List<Integer> A = new ArrayList<Integer>();
        for(int i = n - 1;i >= 0;i --) A.add(digits[i]);

        int t = 1;
        for(int i = 0;i < A.size();i ++)
        {
            t += A.get(i);
            A.set(i,t % 10);
            t /= 10;
        }
        if(t != 0) A.add(t);

        int[] ans = new int[A.size()];
        for(int i = 0;i < A.size();i ++)
        {
            ans[i] = A.get(A.size() - i - 1);
        }
        return ans;
    }
}

C++代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> A;
        for(int i = digits.size() - 1;i >= 0;i --)
        {
            A.push_back(digits[i]);
        }
        vector<int> res;
        int t = 1;
        for(int i = 0;i < A.size() || t != 0;i ++)
        {
            if(i < A.size()) t += A[i];
            res.push_back(t % 10);
            t /= 10;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};