[LintCode] 407 Plus One 解题报告

Description
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.


Example
Given [1,2,3] which represents 123, return [1,2,4].
Given [9,9,9] which represents 999, return [1,0,0,0].


思路
从最后一位开始看。
只要不是9，就说明没有进位。那么只需要更新这一位即可。
如果是9，那么加1以后这一位变成0。并且之前一位开始加1。
如果一直进位进到最后。说明这个数是10...0。我们新开一个数组把第一位置1即可。


Code

public class Solution {
    /**
     * @param digits a number represented as an array of digits
     * @return the result
     */
    public int[] plusOne(int[] digits) {
        // Write your code here
        int len = digits.length - 1;
        while (len >= 0) {
            if (digits[len] < 9) {
                digits[len]++;
                return digits;
            }
            else {
                digits[len--] = 0;
            }
        }
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }
}