386. Lexicographical Numbers 发表于 2022-01-31 Recursion12345678910111213141516171819202122class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> list = new ArrayList<>(n); for (int i = 1; i <= 9; i++) { dfs(n, i, list); } return list; } private void dfs(int n, int i, List<Integer> list) { if (i > n) { return; } list.add(i); for (int j = 0; j <= 9; j++) { dfs(n, i * 10 + j, list); } }} Iterate1234567891011121314151617181920212223class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> list = new ArrayList<>(n); int x = 1; while (list.size() < n) { // 进入至最下一层,在此过程中不断添加至结果集 while (x <= n) { list.add(x); x *= 10; } // 此时 x 已经大于 n, 我们需要返回至上一层,如 190 需要返回到 19, 此时应该优先遍历 2, 所以我们使用了 while 探测尾部数字是否为 9, 此时应继续返回至 1 节点,以便进入到 2 节点 while (x > n || x % 10 == 9) { x /= 10; } x++; // 移动至当前层的右侧节点 } return list; }} Reference386. Lexicographical Numbers