📃 题目描述

题目链接：剑指 Offer 17. 打印从1到最大的n位数 (opens new window)

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

示例 1:

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

🔔 解题思路

小数问题

class Solution {
    public int[] printNumbers(int n) {
        int end = 9;
        while (n != 1) {
            end = end * 10 + 9;
            n --;
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= end; i ++) {
            list.add(i);
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

大数问题，DFS

参考链接：https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/jian-zhi-offer-17-da-yin-cong-1dao-zui-d-ngm4/

在数字很大的情况下，哪怕 long 类型也无法承载，那必须要用字符串保存。

对于本题其实就是对数字 0 ~ 9 的全排列，从 1 位数 0 ~ 9 的全排列到 n 位数 0~9 的全排列，其中要注意的是数字开头不应该有 0。

以下是具体步骤

• 为了避免数字开头出现 0，先把首位 first 固定，first 取值范围为1~9
• 用digit表示要生成的数字的位数，本题要从1位数一直生成到n位数，对每种数字的位数都生成一下首位，所以有个双重for循环
• 生成首位之后进入递归生成剩下的 digit - 1 位数，从 0~9 中取值
• 递归的中止条件为已经生成了 digit 位的数字，即 index == digit，将此时的数num转为int加到结果res中

class Solution {
    public int[] printNumbers(int n) {
        List<Integer> list = new ArrayList<>();

        // 构造 digit 位数的全排列
        for (int digit = 1; digit <= n; digit ++) {
            // 固定第一位（把第一位单独拉出来的原因是，第一位不能为 0）
            for (char first = '1'; first <= '9'; first ++) {
                char[] temp = new char[digit];
                temp[0] = first;

                // 生成首位之后进入递归生成剩下的 digit - 1 位数，从 0~9 中取值
                // 从下标 index 位开始往后递归选取
                int index = 1;
                dfs(index, digit, temp, list);
            }
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private void dfs(int index, int digit, char[] temp, List<Integer> list) {
        if (index == digit) {
            list.add(Integer.parseInt(String.valueOf(temp)));
            return ;
        }

        for (char i = '0'; i <= '9'; i ++) {
            // 将下标为 index 位设为 i
            temp[index] = i;
            // 递归设置下标 index + 1 位
            dfs(index + 1, digit, temp, list);
        }
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：