⽤C语⾔实现数组值加⼀问题
1.题⽬描述
给定⼀个由 整数 组成的 ⾮空 数组所表⽰的⾮负整数，在该数的基础上加⼀。
最⾼位数字存放在数组的⾸位， 数组中每个元素只存储 单个 数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
2.解题⽅法
出最长的后缀9
3.解题思路
⾸先确定加⼀是在数组digits最后⼀位加上的，那么判断进位时可以倒着遍历。可以分为三种情况：
· 最后⼀位不为9，⽐如[1, 2, 3], 那么直接将最后⼀位加⼀，并返回 [1, 2, 4]；
· 倒着遍历，其中有若⼲个9，⽐如[1, 2, 9, 9] ，那么应到 倒着的最后⼀个 9，然后令它前⼀项，也就是2加⼀，其余9全部置0, 返
回 [1, 3, 0, 0]；
· 如果digits[0]也为9，⽐如[9 ,9, 9, 9]， 那么应该对digits重新分配⽐原来多1的内存。digits[0] 置1，其余全部置0，返回[1, 0, 0, 0, 0]。
⼤家可能并不明⽩这个returnSize是什么意思，其实它就是数组需要返回的长度。前两种情况下returnSize = digitsSize，第三种情况下returnSize = digitsSize+1。
4.程序代码
int* plusOne(int* digits, int digitsSize, int* returnSize){ //returnSize表⽰返回数组的长度    digits[digitsSize - 1] += 1; //先给最后⼀项加⼀
int i = digitsSize - 1; // 从最后⼀项开始遍历
while(digits[i] > 9 && i > 0) { //倒着到最后⼀个9，然后正着包括这个9往后都置零            digits[i - 1] += digits[i] / 10;
digits[i] = 0;
i--;
}
if (digits[0] > 9) { //最后⼀项出现9，加⼀后原数组长度加⼀
++digitsSize;
// 利⽤realloc对数组digits重新分配内存令数组全部的值为0
digits = (int *)realloc(digits, (digitsSize) * sizeof(int));
digits[0] /= 10;
digits[digitsSize - 1] = 0;
*returnSize =  digitsSize; //returnSize需要返回值
} else {
*returnSize =  digitsSize;
}
return digits;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。