leetcode——[66]Plus One加一

题目

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。

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

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

示例 1:

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

示例 2:

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

Given a non-empty array of digits representing a non-negative integer, plus 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 contain a single digit.

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

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

解题方法

转化为整数

将数组先转换为一个整数，然后再加一，最后再还原为数组。首先说明这种方法是失败的。为了规避超大整数溢出，我先采用long型整数，结果发现测试案例中有比long型还大的数，然后尝试了使用double，结果因为double低位精度损失而输出错误，不过我觉得这个思路还是值得写下来的。

class Solution {
    public int[] plusOne(int[] digits) {
        // Method_01  error
        int length = digits.length;
        double num = 0;
        int index = 0;
        while (--length >= 0) {
            num += digits[index++] * Math.pow(10, length);
        }
        num++;

        int[] tmp = new int[digits.length + 1];
        int len = 0;
        while (num > 0) {
            tmp[len++] = (int) (num % 10);
            num /= 10;
        }

        int[] result = new int[len];
        int pos = len - 1;
        for (int i = 0; i < len; i++) {
            result[i] = tmp[pos--];
        }

        return result;
    }
}

进位标志

可以参考leetcode——[002]Add Two Numbers两数相加中进位标志的方法，用一个变量标记是否进位，然后从最后一位向前进行计算，并考虑考虑最高位进位时只有各位数均为9的特殊情况。这段代码跑了0ms，超过100%的java提交。

class Solution {
    public int[] plusOne(int[] digits) {
        // Method_02  0ms  100%
        int carry = 1;
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            int tmp = digits[i] + carry;
            digits[i] = tmp % 10;
            carry = tmp / 10;
        }
        
        // special case 9999999999...
        if (carry == 1) {
            int[] res = new int[n + 1];
            res[0] = 1;
            return res;
        }

        return digits;
    }
}

小于9停止

考虑这道题只加一，则进位时每一位也最多只会加1，当上面方法进位标记已经变为0时，即某位数+1小于9，便可以停止循环了，所以对上面代码进行改进。这种方法当然也只跑了0ms，超过了100%的java提交。

class Solution {
    public int[] plusOne(int[] digits) {
        // Method_03  0ms  100%
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9){
                digits[i]++;
                return digits;// stop loop
            }
            digits[i] = 0;
        }

        // special case 999999....
        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
    }
}

结语

希望中国能够早日实现高端芯片自研自产，虽然还菜得很，但未来尤可期也！