leetcode 66 | 加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 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;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-01-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读