不考虑大数的情况
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> ret;
int maxNum = pow(10, n);
for(int i = 1; i < maxNum; ++i)
ret.push_back(i);
return ret;
}
};
|
考虑大数的情况
需要使用字符串来表示数字
首先通过回溯，对于特定的位数，衔接上0~9
再进行去除前导0，设字符串无前导0的起始点为start，n为3时
则
1~9时，start=2
10~99时，start = 1
100~999时，start=0
综上可以得出start=n-(9的个数)
所以当碰到9时，增加9的个数，而但start = n - nine时，这时的所有位都是9，使start-1，表示要进位了
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
| class Solution {
public:
vector<string> printNumbers(int n) {
vector<string> ret;
string tmp;
int start = n - 1;
backTrack(ret, n, 0, tmp, start);
return ret;
}
private:
void backTrack(vector<string>& ret, int n, int nine, string& tmp, int& start)
{
if (n == tmp.size())
{
auto res = tmp.substr(start);
if(res != "0")
ret.push_back(res);
if (start == n - nine)
--start;
return;
}
for (int i = 0; i <= 9; ++i)
{
tmp += (char)(i + '0');
if (i == 9)
nine += 1;
backTrack(ret, n, nine, tmp, start);
tmp.pop_back();
}
}
};
|