flash网站下载,重庆做网站建设找谁,wordpress插件中文,外包员工题目描述
给定一个由 非负整数组成的非空数组#xff0c;表示一个整数。在该整数的基础上加一。
最高位数字在数组的首位#xff0c;数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外#xff0c;这个整数不会以零开头。
示例 1:
输入: digits [1,2,3]
输出:…题目描述
给定一个由 非负整数组成的非空数组表示一个整数。在该整数的基础上加一。
最高位数字在数组的首位数组中每个元素只存储单个数字。
你可以假设除了整数 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。解决方案
可以通过模拟加法操作从数组的尾部开始处理进位。
核心思路
从数组末尾向前遍历将最低位加一。如果加一后小于 10则无需进位直接返回结果。如果产生进位则将当前位置的数字置为 0继续处理更高位。如果遍历结束仍有进位如 [9,9,9]需要在数组开头插入 1。 C 语言实现
#include stdio.h
#include stdlib.hint* 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;
}代码说明 加法模拟 从数组尾部向前遍历依次处理每位数字的加一操作。如果某位加一后小于 10则无需进位直接返回。如果某位加一后等于 10则将其置为 0继续处理更高位。 处理进位 如果所有位都加完且仍有进位如 [9,9,9]需要扩展数组并在首位加 1。 动态内存分配 如果需要扩展数组例如 [9,9,9] - [1,0,0,0]需要动态分配新数组并返回。 返回结果 使用 returnSize 记录结果数组的长度。 复杂度分析
时间复杂度: O ( n ) O(n) O(n)需要遍历整个数组。空间复杂度: O ( 1 ) O(1) O(1)如果不需要扩展数组或 O ( n ) O(n) O(n)如果需要扩展数组。 测试示例
输入不同的测试用例观察输出是否正确
输入: [1,2,3]
输出: [1,2,4]输入: [9,9,9]
输出: [1,0,0,0]输入: [0]
输出: [1]
