Plus One

Question

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_8

Given [1,2,3] which represents 123, return [1,2,4].

Given [9,9,9] which represents 999, return [1,0,0,0].

Tags

Array Google

Related Problems

Medium Divide Two Integers 15 % Easy Add Binary

Analysis

比较巧的方法是将 +1 当做末位digit的进位carries；每次进位 carries = sum / 10;，留下的数字为 digits[i] = sum % 10;

如果最终进位 ！= 0，说明要新增加一位，则新建数组把计算结果填进去。

Solution

public class Solution {
    /**
     * @param digits a number represented as an array of digits
     * @return the result
     */
    public int[] plusOne(int[] digits) {
        int carries = 1;
        for (int i = digits.length - 1; i >= 0 && carries > 0; i--) {
            int sum = digits[i] + carries;
            digits[i] = sum % 10;
            carries = sum / 10;
        }
        if (carries == 0) {
            return digits;
        }
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        for (int i = 1; i < result.length; i++) {
            result[i] = digits[i - 1];
        }
        return result;
    }
}

好久不见，写了一个特啰嗦的...：(0 ms beats 100% AC)

class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 0;
        int i = digits.length - 1;
        while (carry >= 0 && i >= 0) {
            int tmp = 0;
            if (i == digits.length - 1) {
                tmp = 1 + digits[i] + carry;
            } else {
                tmp = digits[i] + carry;
            }
            if (tmp > 9) {
                digits[i] = tmp % 10;
                carry = 1;
            } else {
                digits[i] = tmp;
                carry = 0;
            }
            i--;
        }
        int[] ans;
        if (carry > 0) {
            ans = new int[digits.length + 1];
            ans[0] = carry;
            for (int k = 1; k < ans.length; k++) {
                ans[k] = digits[k - 1];
            }
        } else {
            ans = digits;
        }
        return ans;
    }
}