题目描述

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

https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

题解

递归生成全排列

该题《剑指Offer》是要求打印大数的，所以以字符串存储，dfs 递归生成全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// class Solution {
// public:
//     vector<int> printNumbers(int n) {
//         vector<int> res(pow(10, n) - 1);
//         iota(res.begin(), res.end(), 1);
//         return res;
//     }
// };

// 考虑大数问题
class Solution {
    // 生成长度为 len 的数字 number，正在生成从左往右第 x 位，最后存储在 numbers 中
    void dfs(int len, int x, string& number, vector<string>& numbers) {
        if (x == len) {     // 从第 0 位开始的，所以 x == len 时已经完成了
            numbers.push_back(number);
            return;
        }
        // 这里保证第 0 位从 '1' 开始，不会出现有前导零的问题
        int start = (x == 0 ? 1 : 0);   // 如果是第 0 位，要从 1 开始
        for (char i = start + '0'; i <= '9'; ++i) {
            number.push_back(i);            // 确定本位数字为 'i'
            dfs(len, x + 1, number, numbers);   // 确定下一位数字
            number.pop_back();              // 删除本位数字，继续循环
        }
    }
public:
    vector<int> printNumbers(int n) {
        vector<string> numbers;
        for(int i = 1; i <= n; ++i) {
            string number = "";
            dfs(i, 0, number, numbers);
        }
        // -------------------------------
        vector<int> ret;    // 为了提交正确
        for (string num : numbers)
            ret.push_back(stoi(num));
        return ret;
    }
};

时间复杂度：O(10n)O(10^n) 。生成 10n10^n 个数字，生成每个数字用的时间为 1~n，可看作常数。
空间复杂度：O(10n)O(10^n)，不考虑返回空间为 O(n)O(n)。
如果考虑返回的空间，O(10n)O(10^n)，返回 10n10^n 个字符串，而字符串的长度为 1~n，可看作常数。
如果不考虑返回空间，那递归深度最大为 n，临时存储字符串空间为 n，所以有 O(n)O(n) 。