给你一个整数 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]

提示：

1 <= n <= 5 * 104

  1. class Solution {
  2.     /**
  3.     运用dfs求解，根节点是0，从第二层开始搜起，[1, 9]然后之后每层都从cur * 10 + i, i[0, 9]
  4.      */
  5.     List<Integer> res = new ArrayList<>();
  6.     public List<Integer> lexicalOrder(int n) {
  7.         for (int i = 1; i <= 9; ++i) dfs(i, n);
  8.         return res;
  9.     }
  11.     void dfs(int cur, int limit) {
  12.         if (cur > limit) return;
  13.         res.add(cur);
  14.         for (int i = 0; i <= 9; ++i) dfs(cur * 10 + i, limit);
  15.     }
  16. }

迭代

  1. class Solution {
  2.     public List<Integer> lexicalOrder(int n) {
  3.         List<Integer> res = new ArrayList<>();
  4.         for (int i = 0, j = 1; i < n; ++i) {
  5.             res.add(j);
  6.             if (j * 10 <= n) {
  7.                 j = j * 10;
  8.             } else {
  9.                 while (j % 10 == 9 || j + 1 > n) j /= 10;
  10.                 j ++;
  11.             }
  12.         }
  13.         return res;
  14.     }
  15. }