实现一个十进制数字报数程序，请按照数字从小到大的顺序返回一个整数数列，该数列从数字 1 开始，到最大的正整数 cnt 位数字结束。

示例 1：

**输入：**cnt = 2
输出：[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,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]

cnt特别大时会超出long long范围，要用字符串表示

第一位必须为1-9，再对后面每位进行遍历

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
class Solution {
    vector<string> anstr;

public:
    vector<string> countNumbers(int cnt) {
        if (cnt == 0)
            return {};

        for (int i = 1; i <= cnt; i++) {
            for (int f = 1; f <= 9; f++) {
                string mid;
                mid.push_back(f + '0');
                dfs(mid, i, 1);
            }
        }
        return anstr;
    }
    void dfs(string mid, int cnt, int len) {
        if (cnt == len) {
            anstr.push_back(mid);
            return;
        }
        for (int i = 0; i <= 9; i++) {
            mid.push_back(i + '0');
            dfs(mid, cnt, len + 1);
            mid.pop_back();
        }
        return;
    }
};

也可以使用BFS

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
class Solution {
public:
    vector<int> countNumbers(int cnt) {
        vector<string> str;
        queue<string> q;
        for (int i = 1; i <= 9; i++)
            q.push(to_string(i));

        while (!q.empty()) {
            string mid = q.front();
            str.push_back(mid);
            q.pop();
            if (mid.length() < cnt) {
                for (int i = 0; i <= 9; i++) {
                    q.push(mid + to_string(i));
                }
            }
        }

        vector<int> ans;
        for (string i : str) {
            ans.push_back(stoi(i));
        }
        return ans;
    }
};