给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
分析:这道题是不是看第一眼是不是就想把数组转化为整数,然后再用这个整数加1,再将这个结果转化为数组~那可就调入这道题的陷阱里了,这样做是不行的,因为这个整数可以很大,大的超过int的范围,甚至超过long的范围。所以我们应该换个角度思考。我们可以分情况讨论,第一,我们让数组的最后一个数加1,即个位加1,如果小于10,则说明不存在进位的问题。所以我们就可以直接返回digits数组;第二,个位加1之后,若大于等于10,说明存在进位问题,所以最后的结果数组的长度可能为digits的数组长度加1。我们可以定义一个数组result,长度为digits的长度+1,然后把digits数组copy一份到result[1]~result[digits.length],然后来处理进位的问题。那进位怎么处理呢?其实也很简单,因为个位加1后大于等于10,所以个位的数保留相加之和的个位,然后定义初始进位carry为1,从result[digits.length-1],即十位开始,当carry !=0时,就继续上前进位,本身保留与进位相加结果之和的个位即可,最后判断result[0],即第一位是否为0,若不为0,则直接返回result,若为0,则返回从索引1到索引digits.length的子串即可。
代码实现:
int* plusOne(int* digits, int digitsSize, int* returnSize) {
int* result = (int*)malloc(sizeof(int)*(digitsSize + 1));
int i;
for (i = 0; i < digitsSize; i++)//判断是否进位
{
if (digits[i] != 9)
break;
}
if (i == digitsSize)//判断是否要加长输出数组长度(输入数组全为9)
{
*returnSize = digitsSize + 1;
result[0] = 1;
for (int i = 1; i<digitsSize + 1; i++)
result[i] = 0;
return result;
}
i = digitsSize - 1;
result[i] = digits[i] + 1;
for (i; i>0; i--)
{
if (result[i] == 10)//判断不是第一位为9的进位
{
result[i] = 0;
result[i - 1] = digits[i - 1] + 1;
}
else
result[i - 1] = digits[i - 1];
}
*returnSize = digitsSize;
return result;
}