Question:

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.

Thinking:

  • Method1
    1. 将数组中储存的数字取出来加一。
    2. 将结果通过栈存入结果数组中。
    3. 因为long位数限制的原因无法AC。
class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        long sum = digits[0];
        for(int i = 1; i < len; i++){
            sum = sum * 10 + digits[i];
        }
        sum++;
        Stack<Integer> st = new Stack<>();
        while(sum != 0){
            st.push((int)(sum % 10));
            sum /= 10;
        }
        int size = st.size();
        int[] result = new int[size];
        for(int i = 0; i < size; i++)
            result[i] = st.pop();
        return result;
    }
}
  • Method2:
    1. 对位操作，计算每一位的值和carry。
    2. 唯一要注意的就是对于第一位的carry是1，这就起到了+1的效果，同时维护了循环的一致性。
class Solution {
    public int[] plusOne(int[] digits) {
        if(digits == null || digits.length == 0) return null;
        int len = digits.length;
        int[] result = new int[len + 1];
        int carry = 1;
        for(int i = len - 1; i >= 0; i--){
            int current = digits[i] + carry;
            result[i + 1] = current % 10;
            carry = current / 10;
        }
        if(carry == 1){
            result[0] = carry;
            return result;
        }
        return Arrays.copyOfRange(result, 1, len + 1);
    }
}

二刷

二刷的时候想法和一刷的第二个想法是一样的，所以很快就AC了。

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int[] result = new int[len + 1];
        if(len == 0){
            result[0] = 1;
            return result;
        }
        int carry = 0;
        result[len] = (digits[len - 1] + 1) % 10;
        carry = (digits[len - 1] + 1) / 10;
        for(int i = len - 2; i >= 0; i--){
            result[i + 1] = (digits[i] + carry ) % 10;
            carry = (digits[i] + carry ) / 10;
        }
        if(carry == 1){
            result[0] = 1;
            return result;
        }else{
            return Arrays.copyOfRange(result, 1, len + 1);
        }
    }
}