题目
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2 输出：[1,2]
解题
方法一：字典树+前序遍历
class Trie{ public: bool isEnd=false; vector<Trie*> next=vector<Trie*>(10,nullptr); }; class Solution { public: Trie* trie=new Trie(); vector<int> res; vector<int> lexicalOrder(int n) { for(int i=1;i<=n;i++){ insert(to_string(i)); } traversal(trie,0); return res; } //字典树前序遍历 void traversal(Trie* root,int path){ if(root->isEnd){ res.push_back(path); } for(int i=0;i<10;i++){ if(root->next[i]){ traversal(root->next[i],path*10+i); } } } //字典树插入节点 void insert(string&& s){ Trie* node=trie; for(char c:s){ if(node->next[c-'0']==nullptr){ node->next[c-'0']=new Trie(); } node=node->next[c-'0']; } node->isEnd=true; } };
方法二：迭代
class Solution { public: vector<int> lexicalOrder(int n) { vector<int> res(n); int num=1; for(int i=0;i<n;i++){ res[i]=num; if(num*10<=n){ num*=10; }else{ while(num%10==9||num+1>n){ num/=10; } num++; } } return res; } };
