LeetCode (66)：加一

这次来写一下 LeetCode 的第 66 题，加一

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

这道题目的思路比较符合我们平时列竖式的思路，这道题目我使用 C 语言进行完成，看我下面的分析。

问题分析

这道题目是给出一个数组，数组的每个元素都是一个 个位数 ，然后对数组的最后一个元素进行加一的操作，加一的操作看似很容易，但是需要考虑两个问题点。

如果数组的最后一个元素是一个小于 9 的元素，那么直接加一就算完成了整个数组的加一操作。但是，如果数组的最后一个元素是 9，那么就会向数组的倒数第二个元素进行进位，因为要保持每个数组的元素都是一个个位数。因此，我们就需要对数组的倒数第二个元素的值也做加一。那么当数组的倒数第二个元素在加一后也产生进位，那么就需要接着把进位向前相加。

最后一个元素小于9的情况

倒数两个元素都等于9的情况

这个问题这样其实还不算完， 当我们对数组最后一个元素进行加一，并且对最后一个元素之前的元素进行进位调整的时候，我们会从数组的最后一个元素向数组的第一个元素这样倒序进行操作。而当数组的每一位都为 9 的时候，进行加一的数组比原始数组是多一个元素的。

两个数组的元素不同

在原始数组中每一个元素都是 9 的情况下，我们新数组的数组元素个数一定要比原始数组的元素个数多一个。不但如此，在前面两幅图中，循环的时候，两个数组的下标是相同的。而对于当前图来说，两个数组在进行循环的时候，下标是不相同的。（这段话可能表达的不是很清楚，请看代码进行理解吧）

代码实现

代码实现如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize){
    if (digits == NULL) {
        *returnSize = 0;
        return NULL;
    }


    int* pArr = NULL;


    int size = digitsSize;
    int i = 0;


    // 如果 digits 每一位都为 9，申请内存时要多一个元素
    for (; i < digitsSize; i ++) {
        if (digits[i] != 9) {
            break;
        }
    }
    // 新数组长度
    // 原始数组的每位都为9
    if (i == digitsSize) {
        size = digitsSize + 1;
    }


    pArr = (int *)malloc(size * sizeof(int));

    // 进位标志
    int sf = 1;
    // 原始数组最后一个元素的下标
    i = digitsSize - 1;
    // 新数组最后一个元素的下标
    int j = size - 1;


    while (i >= 0) {
        pArr[j] = (digits[i] + sf) % 10;
        sf = (digits[i] + sf) / 10;




        i --;
        j --;
    }
    // 调整最高位
    if (j >= 0) {
        pArr[0] = sf;
    }


    *returnSize = size;
    return pArr;
}

提交结果

在写完 plusOne 函数体后，点击右下角的 “ 执行代码 ”，然后观察  “输出” 和 “预期结果”  是否一致，一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体， 如果所有的测试用例都通过了，那么就会给出 “通过” 的字样， 如果没有通过，会给出失败的那一组测试用例，我们继续修改代码 。我们以上代码 “提交” 以后的截图如下：