给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如,
给定 n =1 3,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lexicographical-numbers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ans(n); //n=1000
int cur = 1;
for(int i = 0; i < n; ++i)
{
ans[i] = cur;
if(cur*10 <= n)
cur *= 10; //1,10,100,1000
else
{
if(cur >= n) //1000
cur /= 10;
cur += 1; //101。。。109
while(cur%10 == 0) //110
cur /= 10; //11
}
}
return ans;
}
};
n = 1000
[1,10,100,1000,101,102,103,104,105,106,107,108,109,
11,110,111,112,113,114,115,116,117,118,119,12,120,
121,122,123,124,125,126,127,128,129,13,130,131,132,
133,134,135,136,137,138,139,14,140,141,142,143,144,
145,146,147,148,149,15,150,151,152,153,154,155,156,
157,158,159,16,160,161,162,163,164,165,166,167,168,.
class Solution {
vector<int> ans;
public:
vector<int> lexicalOrder(int n) {
for(int i=1; i<=9; i++)
dfs(i, n);
return ans;
}
void dfs(int cur, int n)
{
if(cur > n)
return;
ans.push_back(cur);
for(int i=0;i<10;i++)
{
if(10*cur + i > n)
return;
dfs(10*cur+i, n);
}
}
};