题目描述

解题思路

直接枚举

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

回溯

详细解析🔗
可以得知当，n等于4时，此时在4位数中，每位数字进行排序，也就可以得到需要列举的数字。
使用String来保存大数，应为int，long，short都有范围。
基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n = 2 时（数字范围 1 - 99），固定十位为 0 - 9 ，按顺序依次开启递归，固定个位 0 - 9 ，终止递归并添加数字字符串。
但是注意：

• 需要排除第一个0，所以在收集结果判断不等于0即可。
• 删除高位多余的 00 （例如：001）：

此时删除使用一个标记start，表示省略前面多少个0，例如n=3，当数为3时，此时start应该为2，但当数字到达9的时候，需要进一位，此时start就需要加一了，那么如何判断start该加一呢？我们使用一个nineCount标记共有多少位9，所以 n - start == nineCount 时，start就应该减一，例如n=3，此时数字如果是3，start=2，nineCount=0，当到达9之后，nineCount=1，此时start就需要减一，因为要进位了。但是注意此时是9，进位之后9的个数需要减一，防止影响2位数的递归。

    class Solution {
        int nineCount = 0, count = 0, start = 0, n = 0;
        int[] res;
        char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
        public int[] printNumbers(int n) {
            this.n = n;
            res = new int[(int) Math.pow(10, n)];
            count = n;
            start = n - 1; // 从个位开始
            dfs(0);
            return res;
        }
        public void dfs(int x) {
            if (n == x) {
                // 前面的0使用start标志，表示舍弃多少个0
                String s = String.valueOf(num).substring(start);
                // 直接跳过0，从1开始
                if (!s.equals("0")) {
                    res[count++] = Integer.parseInt(s);
                }
                // 如果总位数减去前面0的位数等于都为9的位数，需要扩大一位
                // 例如999，此时下一个数就是1000，start需要减一
                if (n - start == nineCount) start--;
                return;
            }
            for (char c : loop) {
                // 9的个数加一
                if (c == '9') nineCount++;
                num[x] = c;
                // 递归下一位数
                dfs(x + 1);
            }
            // 注意减去9的数量，回溯
            nineCount--;
        }
    }