题目描述

给定一个非负整数数组 digits，表示一个非负整数。每次操作将整个数组增加 1（即加一操作）。你需要找出加一操作后的数组表示。

示例

示例 1

输入: digits = [1,2,3]
输出: [1,2,4]
解释: 数组表示数字 123，加一操作后变为 124。

示例 2

输入: digits = [4,3,2,1]
输出: [4,3,2,2]
解释: 数组表示数字 4321，加一操作后变为 4322。

示例 3

输入: digits = [0]
输出: [1]
解释: 数组表示数字 0，加一操作后变为 1。

题解

这个问题可以通过模拟加法操作来解决。

1. 从最低位开始：从数组的最后一个元素开始，模拟加一操作。
2. 加一并处理进位：对于每个元素，将其加一，如果结果大于 9，则设置该元素为 0 并产生一个进位。
3. 处理最高位的进位：如果在整个数组遍历结束后仍有进位，需要在数组的最前面添加一个新元素 1。

代码实现

vector<int> plusOne(vector<int>& digits) {int n = digits.size();int carry = 1; // 初始进位为 1for (int i = n - 1; i >= 0; i--) {int sum = digits[i] + carry;digits[i] = sum % 10; // 更新当前位carry = sum / 10; // 计算进位}if (carry > 0) {digits.insert(digits.begin(), carry); // 处理最高位的进位}return digits;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 digits 的长度。我们需要遍历一次数组。
● 空间复杂度：O(1)，因为我们是在原地修改数组，没有使用额外的空间。
这个算法的优势在于它直接模拟了加法操作，不需要复杂的数学计算。