leetcode [#66]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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.

---

解决方案

public class Solution {
    public static int[] plusOne(int[] digits) {
        int N = digits.length;
        int[] result = handle(digits, N - 1);
        return result;
    }

    private static int[] handle(int[] a, int index){
        if(a[index] < 9){
            a[index]++;
            return a;
        } else {
            a[index] = 0;
            index--;
            if(index < 0){
                int[] y = new int[2];
                y[0] = 1;
                y[1] = 0;
                return y;
            } else if(index == 0){
                if(a[index] < 9){
                    a[index]++;
                    return a;
                } else {
                    a[index] = 0;

                    int res[] = new int[a.length + 1];
                    res[0] = 1;
                    for(int r = 1; r < a.length + 1; r++){
                        res[r] = a[r - 1];
                    }
                    return res;
                }
            } else {
                int[] t = handle(a, index);
                return t;
            }
        }
    }
}

---

注意事项

1. 以下方法思路正确，但是会超时，不符合复杂度要求：

   public static int[] plusOne(int[] digits) {
       int[] one = {1};
       int N = digits.length;
       if(N == 0) return one;
       int val = 0;
       for(int i = 0; i< N; i++){
           val += digits[i] * Math.pow(10, (N-i-1));
       }
       val++;
       List<Integer> list = new ArrayList<>();
       while(val != 0){
           list.add(val % 10);
           val = val / 10;
       }
       int[] result = new int[list.size()];
       for(int p = 0; p < list.size(); p++){
           result[p] = list.get(list.size() - 1 - p);
       }
       return result;
   }

2. 解决方案中，使用递归，从数组最高位开始判定，如果小于9，直接加1返回即可；如果为9，则要进位，递归调用本身判断前一位的情况。跳出递归的条件是当前索引值。