66. Plus One

Posted on | In |

LeetCode 66. Plus One

如题所述，要在用数组表示的数值上加1，其中数组里每个位置上的数值表示十进制的一位。这里存在一个问题：这个数字是大端表示还是小端表示？根据测试用例我们可以看到是大端表示。

一种直觉的解法是按照加法的操作，对个位数加一然后看有没有进位，循环处理进位。如果处理到最后还有进位，就重开一个大小比原来数组大1的数组，并且将最高位置为1，其他位为0。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] plusOne(int[] digits) {
    int i, carry = 1, n = digits.length;
    for (i = n - 1; i >= 0; i--) {
        int temp = digits[i];
        digits[i] = (temp + carry) % 10;
        carry = (temp + carry) / 10;
    }
    if (carry == 1) {
        int[] result = new int[n + 1];
        result[0] = 1;
        return result;
    }
    return digits;
}

但是这个代码并不是很简洁。实际上，我们并不需要按照加法的法则去处理这个问题。我们可以观察输入和输出。

  • 如果个位数小于9，那么只需要个位数自增就可以返回结果。如果个位数是9，那么需要进位，也就是个位数变成0，同时向十位数进位。

  • 如果十位数小于9，那么只需要十位数自增就可以返回结果，如过十位数是9，那么需要进位，也就是十位数变成0，同时向百位数进位。

  • …

通过一个循环就可以处理整个加法。如果循环到最后都没有返回，那么就可以确定所有位置原来的数字都是9。我们只需要开辟一个新的大小为原数组大小加1的数组，并且将数字的最高为置为1即可。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] plusOne(int[] digits) {
    int n = digits.length;
    for (int i = n - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    int[] result = new int[n + 1];
    result[0] = 1;
    return result;
}