leetcode386_字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
思路：
1 2 3 ...
/\ /\ /\
10 ...19 20...29 30...39 ....
数据较小，直接dfs
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i < 10; i++) { //1-9之间插入数字
dfs(i, n, res);
}
return res;
}
public void dfs(int cur, int n, List<Integer> res) {
if (cur > n) //退出条件
return;
else {
res.add(cur);
for (int i = 0; i < 10; ++i) { //0-9
if (10 * cur + i > n) //退出条件
return;
dfs(10 * cur + i, n, res);
}
}
}
投递蔚来等公司7个岗位
