​LeetCode刷题实战66：加一

今天和大家聊的问题叫做 加一，我们先来看题面：

https://leetcode-cn.com/problems/plus-one/

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

题意

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

例题

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

解题

解法的关键在于弄明白什么情况下会产生进位。使用个位、十位、百位进行列举：

个位：想让个位+1进位，那么个位必须为99+1 = 0carry = 1

十位：想让十位+1进位，那么十位必须为9，想要产生进位carry，那么必须由个位进位而来。想让个位进位，个位必须为9.99 + 1 = 00carry = 1

百位：想让百位+1进位，那么百位必须为9，想要产生进位carry，那么必须由十位进位而来，想让十位进位，那么十位必须为9，想要产生进位，个位必须为9。999 + 1 = 000carry = 1

根据以上可以推论得出两种情况：

最高位进位
若最高位进位，那么比他低的位数字都为9，且加1后都为0，需要初始化一个长度为(lenght+1)的新数组，0位置为1代表进位。

最高位不进位若最高位不进位，那么不需要产生新数组，后续数字由更低位计算而来。我们来看下代码

class Solution {
    public int[] plusOne(int[] digits) {
 int carry = 1;
    for (int i = digits.length - 1; i >= 0; i--) {
        if (carry == 0) {
            return digits;
        }
        int tmp = digits[i] + carry;
        carry = tmp / 10;
        digits[i] = tmp % 10;
    }
    if (carry != 0) {
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }
    return digits;
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。