剑指 Offer 17. 打印从1到最大的n位数

Simulation

class Solution {
    public int[] printNumbers(int n) {
        int[] res = new int[(int) Math.pow(10, n) - 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

DFS

class Solution {
    private static final char[] NUMS = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    private static class State {
        private int startIndex;
        private int countOfNine;
        private int resIndex;
        private final int n;

        public State(int n) {
            this.n = n;
            this.startIndex = n - 1; // 不要忘记初始化 startIndex, 且为最右侧元素索引，注意不是 0
        }
    }

    public int[] printNumbers(int n) {
        int[] res = new int[(int) Math.pow(10, n) - 1];
        char[] numArray = new char[n];
        State state = new State(n);
        StringBuilder sb = new StringBuilder();
        dfs(res, numArray, 0, state);
        return res;
    }

    private void dfs(int[] res, char[] numArray, int level, State state) {
        if (level == state.n) {
            int value = Integer.parseInt(new String(numArray).substring(state.startIndex));
            if (value != 0) {
                res[state.resIndex++] = value;
            }

            if (state.countOfNine + state.startIndex == state.n) {
                state.startIndex--;
            }

            return; // 此处不要忘记 return
        }

        for (char num : NUMS) {
            if (num == '9') {
                state.countOfNine++;
            }

            numArray[level] = num;
            dfs(res, numArray, level + 1, state);
        }

        state.countOfNine--;
    }
}

References

剑指 Offer 17. 打印从1到最大的n位数