386_字典序排数

难度：中等

题目

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例

示例一：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例二：

输入：n = 2
输出：[1,2]

提示

• $1 <= n <= 5 * 10^4$

解题

base 从 0 开始，当 base 小于 n 时，计算 num = base + i，（i 从 start 到 9 递增，一般来说是从 0 开始，但第一个数应该是从 1 开始），然后递归 dfs（num*10, 0, n, ans）

public List<Integer> lexicalOrder(int n) {
  List<Integer> ans = new ArrayList<>();
  dfs(0,1,n,ans);
  return ans;
}
// 以 base 为基数，从 start 开始添加个位数， <=n 的结果添加到 ans 中
public void dfs(int base, int start, int n, List<Integer> ans){
  if(base>n)
    return;
  for(int i=start; i<10; i++){
    int num = i+base;
    if(num<=n){
      ans.add(num);
      dfs(num*10,0,n,ans);
    }
  }
}