解题方法：模拟法

十进制加法

我们先回顾一下十进制加法的计算过程：
加法.001.jpeg
使用「竖式」计算十进制的加法的方式：

两个「加数」的右端对齐；
从最右侧开始，依次计算对应的两位数字的和。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位。
依次向左计算对应位置两位数字的和，如果有进位需要加上进位。如果和大于等于 10，仍然把和的个位数字计入结果，并向前面进位。
当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。
本题解法

本题给出的数字是 digits 以列表形式给出每一位数字，让我们对 digits 加一。

其实就是模拟十进制加法的过程：两个加数分别是 digitis 和 $1$ 。

直接按照上面的十进制加法的模拟思路进行计算就可以。

在实现中需要注意的有：

不可以把 digits 先转化成 int 型数字再求和，因为可能溢出；
另一个「加数」是 adder ，初始化为 $1$ ，以后都是 $0$；
两个「加数」的长度可能不同；
在最后，如果进位 carry 不为 0，那么最后需要计算进位；

方法：循环

循环的思想比较朴素，就是倒序遍历 digits 的每个元素，与另一个加数 adder 和进位 carry相加的过程。

代码中的巧妙之处：

while (p1 >= 0 || adder > 0 || carry > 0)含义：
1. digits 和 adder 只要有一个没遍历完，那么就继续遍历；
2. 如果字符串 digits 和 adder 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
取当前位置的数字的时候，如果 digits 已经遍历完了（即 $p1 <= 0$），则认为 digits 的对应位置是 $0$ 。

Java / C++ / Python 三种语言的代码：

class Solution {
    public int[] plusOne(int[] digits) {
        int N = digits.length;
        List<Integer> resultList = new ArrayList<>();
        int p1 = N - 1;
        int carry = 0;
        int adder = 1;
        while (p1 >= 0 || adder > 0 || carry > 0) {
            int num = p1 >= 0 ? digits[p1] : 0;
            int sum = num + adder + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            resultList.add(sum);
            p1 --;
            adder = 0;
        }
        int[] res = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); ++i) {
            res[i] = resultList.get(resultList.size() - i - 1);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        const int N = digits.size();
        vector<int> res;
        int p1 = N - 1;
        int carry = 0;
        int adder = 1;
        while (p1 >= 0 || adder > 0 || carry > 0) {
            int num = p1 >= 0 ? digits[p1] : 0;
            int sum = num + adder + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            res.push_back(sum);
            p1 --;
            adder = 0;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution(object):
    def plusOne(self, digits):
        N = len(digits)
        res = []
        adder = 1
        carry = 0
        p1 = N - 1
        while p1 >= 0 or adder > 0 or carry > 0:
            num = digits[p1] if p1 >= 0 else 0
            sum = num + adder + carry
            carry = 1 if sum >= 10 else 0
            sum = sum - 10 if sum >= 10 else sum
            res.append(sum)
            p1 -= 1
            adder = 0
        return res[::-1]

复杂度分析：

时间复杂度：$O(max(N))$，$N$ 是 digits的长度；
空间复杂度：$O(1)$，只使用了常数的空间。

类似题目

看完本题解本题，你可以解决以下题目：

总结

「加法」系列题目都不难，其实就是「列竖式」模拟法。
需要注意的是 while循环结束条件，注意遍历两个「加数」不要越界，以及考虑进位。

——
我是 @负雪明烛，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
公众号有更多精彩内容，点击关注。

算法每日一题题解

66. 加一