103.加一
题目
给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。
将大整数加 1，并返回结果的数字数组。
示例 1：
- 输入：digits = [1,2,3]
- 输出：[1,2,4]
- 解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。
示例 2：
- 输入：digits = [4,3,2,1]
- 输出：[4,3,2,2]
- 解释：输入数组表示数字 4321。 加 1 后得到 4321 + 1 = 4322。 因此，结果应该是 [4,3,2,2]。
示例 3：
- 输入：digits = [9]
- 输出：[1,0] 解释：输入数组表示数字 9。 加 1 得到了 9 + 1 = 10。 因此，结果应该是 [1,0]。
思路
步骤:
1. 从数组的最后一位开始往前遍历。
2. 把当前位加 1：digits[i] = digits[i] + 1。
3. 如果加 1 后等于 10，说明需要进位：把当前位设为 0，然后继续向前遍历（下一位加 1）。
4. 如果加 1 后小于 10，说明没有进位，直接返回数组（因为后面的位不会再受影响）。
5. 如果遍历完整个数组都没有返回，说明所有位都是 9，发生了全进位（例如 999 → 1000）。此时需要在数组最前面插入一个 1，后面全是 0。
为什么这样可以？ - 因为加 1 只会影响连续的若干个 9 以及它们前面的那一位。只要遇到一个不是 9 的位，加 1 后就不会产生进位，可以直接返回。 - 如果所有位都是 9，那么加 1 后所有位都变成 0，并在最前面加一个 1。
class Solution {
fun plusOne(digits: IntArray): IntArray {
// 从最低位开始遍历
for (i in digits.lastIndex downTo 0) {
// 当前位加1
digits[i]++
// 如果加1后等于10，需要进位
if (digits[i] == 10) {
digits[i] = 0 // 当前位置0
// 继续循环，处理下一位
} else {
// 没有进位，直接返回
return digits
}
}
// 所有位都是9，发生了全进位
val result = IntArray(digits.size + 1)
result[0] = 1 // 第一位是1，后面全是0（默认值）
return result
}
}
复杂度
- 时间复杂度: O(n)，最坏情况遍历整个数组。
- 空间复杂度: O(1)（不考虑返回的新数组）或 O(n)（全进位时需要新建数组）。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!