力扣第 66 题 “加一”

题目描述

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

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

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

示例 1:

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

示例 2:

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

示例 3:

输入: digits = [9,9,9]
输出: [1,0,0,0]
解释: 输入数组表示数字 999。

---

解决方案

可以通过模拟加法操作，从数组的尾部开始处理进位。

核心思路

1. 从数组末尾向前遍历，将最低位加一。
2. 如果加一后小于 10，则无需进位，直接返回结果。
3. 如果产生进位，则将当前位置的数字置为 0，继续处理更高位。
4. 如果遍历结束仍有进位（如 [9,9,9]），需要在数组开头插入 1。

---

C 语言实现

#include <stdio.h>
#include <stdlib.h>int* plusOne(int* digits, int digitsSize, int* returnSize) {// 从末尾开始遍历，处理加法for (int i = digitsSize - 1; i >= 0; i--) {if (digits[i] < 9) {digits[i]++;  // 如果当前位小于 9，直接加一并返回*returnSize = digitsSize;return digits;}digits[i] = 0;  // 如果当前位为 9，置为 0，并继续处理高位}// 如果循环结束仍有进位，说明需要扩展数组int* result = (int*)malloc((digitsSize + 1) * sizeof(int));result[0] = 1; // 最高位为 1for (int i = 1; i <= digitsSize; i++) {result[i] = 0; // 其他位为 0}*returnSize = digitsSize + 1;return result;
}int main() {int digits[] = {9, 9, 9};int digitsSize = sizeof(digits) / sizeof(digits[0]);int returnSize;int* result = plusOne(digits, digitsSize, &returnSize);printf("结果: [");for (int i = 0; i < returnSize; i++) {printf("%d", result[i]);if (i < returnSize - 1) printf(", ");}printf("]\n");if (result != digits) {free(result); // 如果是动态分配的数组，记得释放内存}return 0;
}

---

代码说明

1. 加法模拟

   • 从数组尾部向前遍历，依次处理每位数字的加一操作。
   • 如果某位加一后小于 10，则无需进位，直接返回。
   • 如果某位加一后等于 10，则将其置为 0，继续处理更高位。

2. 处理进位

   • 如果所有位都加完且仍有进位（如 [9,9,9]），需要扩展数组并在首位加 1。

3. 动态内存分配

   • 如果需要扩展数组（例如 [9,9,9] -> [1,0,0,0]），需要动态分配新数组并返回。

4. 返回结果

   • 使用 returnSize 记录结果数组的长度。

---

复杂度分析

• 时间复杂度: $O(n)$，需要遍历整个数组。
• 空间复杂度: $O(1)$（如果不需要扩展数组）或 $O(n)$（如果需要扩展数组）。

---

测试示例

输入不同的测试用例，观察输出是否正确：

输入: [1,2,3]
输出: [1,2,4]输入: [9,9,9]
输出: [1,0,0,0]输入: [0]
输出: [1]