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

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：
用返回一个整数列表来代替打印
n 为正整数

class Solution {
    /**
     * @Title: printNumbers
     * @Description: DFS
     * @author: itbird
     * @date 2022年3月21日 下午7:21:25
     * @param n
     * @return int[] 时间复杂度: O(N) 空间复杂度: O(Math.pow(10, n))
     */
    int[] res;
    int currentIndex = 0;

    public int[] printNumbers(int n) {
        // 数组总共的大小
        int k = (int) (Math.pow(10, n) - 1);
        // 初始化数组
        res = new int[k];
        // 遍历找到所有的全排列
        // 去除首位是0的，过程中控制首位元素

        // 外层循环，代表当前遍历的是几位数
        for (int i = 1; i <= n; i++) {
            for (char first = '1'; first <= '9'; first++) {
                char[] num = new char[i];
                num[0] = first;
                dfs(1, num, i);
            }
        }
        return res;
    }

    private void dfs(int index, char[] num, int digit) {
        if (index == digit) {
            // 终止条件
            res[currentIndex++] = Integer.parseInt(String.valueOf(num));
            return;
        }

        for (char i = '0'; i <= '9'; i++) {
            num[index] = i;
            dfs(index + 1, num, digit);
        }
    }

    /**
     * @Title: printNumbers
     * @Description: 累加
     * @author: itbird
     * @date 2022年3月21日 下午7:14:32
     * @param n
     * @return int[] 时间复杂度: O(1) 空间复杂度: O(Math.pow(10, n))
     */
    public int[] printNumbers1(int n) {
        int k = (int) (Math.pow(10, n) - 1);
        int[] result = new int[k];
        for (int i = 0; i < result.length; i++) {
            result[i] = i + 1;
        }
        return result;
    }
}