Add One To Number

Given a non-negative number represented as an array of digits,

add 1 to the number ( increment the number represented by the digits ).

The digits are stored such that the most significant digit is at the head of the list.

If the vector has [1, 2, 3]

the returned vector should be [1, 2, 4]

as 123 + 1 = 124.

思路:

Implement一般的加法即可，需要注意的点是要把结果的leading zero去除。

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public ArrayList<Integer> plusOne(ArrayList<Integer> A) {
        int carry = 0;
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = A.size() - 1; i >= 0; i --) {
            int digit = A.get(i);
            int add = i == A.size() - 1 ? 1 : 0;
            if (digit + carry + add >= 10) {
                digit = digit + carry + add - 10;
                carry = 1;
            } else {
                digit = digit + carry + add;
                carry = 0;
            }
            result.add(digit);
        }
        if (carry == 1) result.add(1);
        Collections.reverse(result);
        ListIterator<Integer> it = result.listIterator();
            while (it.hasNext() && it.next() == 0) {
            it.remove();
        }
        return result;
    }
}