leetcode-386 字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
根据题目描述，所谓字典顺序，即数值按照类似字符串首字母的ASCII大小进行排序
那么数值的字典序即为一个十叉树，比如以1为树顶的树状形式如下：
1
｜
10 11 … 19
｜\ \
100 101 102…109
可以看到第一层第一个数 1 和第二层之间的计算方式：
1 *10 + (1…9)
第二层 第一个树 100 和第三层之间的计算方式
10*10 + (1…9)
综上我们可以实现 n 以内的字典排序数如下：
vector lexicalOrder(int n) {
vector res;
int cur = 1;
for (int i = 1;i <= n; i++) {
res.push_back(cur);
/*深度优先，查找第一颗子树的节点，大小在n以内*/
if(cur * 10 = n){
cur /= 10;
}
cur += 1;
/*处理子树切换时的场景：例如
19 --> 2
1999 --> 2
*/
while(cur % 10 == 0) {
cur /= 10;
}
}
}
return res;
}
作者：浮夸-vigour
