leetcode题解-66.加一

题目-66. Plus One

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:

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

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

分析

实际上这个问题相当于是对一个整数加1，特别的是，这个整数的每一位都存储在了一个数组中。那么只需要按照加法的运算法则计算就可以了。从后往前遍历，如果该位是9，则置0进位，继续计算。直到最后该位不是9，退出循环。最后检查循环终止，如果没有循环到第一位，说明最终不需要增加1位，例如，98+1=99；如果循环到了第一位，说明最后需要进位，则数组长度需要加1，例如99+1=100。

代码

C语言实现代码如下：

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    if(NULL == digits)
        return NULL;
    int loop = 0;
    int *ret = NULL;
    /*按照普通加法计算，9+1进1，当前位置0*/
    for(loop = digitsSize-1; loop >= 0;loop--)
    {
        if(9 != digits[loop] )
        {
            /*当前不等于9，加1后退出即可*/
            digits[loop]+=1;
            break;
        }
        else
        {
            /*等于9时，进位，当前位置0*/
            digits[loop] = 0;
        }
    }
    /*没有循环到最后，说明结果位数不变*/
    if(0 <= loop)
    {
        /*这里直接返回原数组，是否不太好？*/
        *returnSize = digitsSize;
        return digits;
    }
    else
    {
        /*全为9，需要增加一位*/
        ret = (int*)calloc(digitsSize +1 ,sizeof(int));
        if(NULL == ret)
        {
            return NULL;
        }
        ret[0] = 1;
        *returnSize = digitsSize +1;
        return ret;
    }
}

运行时间

Runtime: 0 ms

推荐阅读：

关注公众号【编程珠玑】，第一时间获取更多原创技术文章