leetcode 386. Lexicographical Numbers | 386. 字典序排数（Java）

r囧r小猫 2022-08-31 13:24 23阅读 0赞

## 题目 ##

[https://leetcode.com/problems/lexicographical-numbers/][https_leetcode.com_problems_lexicographical-numbers]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

思路：先序遍历 10 叉树，参考：[Simple Java DFS Solution][]

The idea is pretty simple. If we look at the order we can find out we just keep adding digit from 0 to 9 to every digit and make it a tree.
    Then we visit every node in pre-order. 
           1        2        3    ...
          /\        /\       /\
       10 ...19  20...29  30...39   ....

class Solution { 
        public List<Integer> lexicalOrder(int n) { 
            ArrayList<Integer> res = new ArrayList<>();
            for (int i = 1; i < 10; i++) { 
                dfs(i, n, res);
            }
            return res;
        }
    
        public void dfs(int num, int max, List<Integer> list) { 
            if (num > max) return;
            list.add(num);
            for (int i = 0; i < 10; i++) { 
                if (num * 10 + i > max) return;
                dfs(num * 10 + i, max, list);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_lexicographical-numbers]: https://leetcode.com/problems/lexicographical-numbers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/b79f4eabf7bc4346b9a83d4137dccc0c.png
[Simple Java DFS Solution]: https://leetcode.com/problems/lexicographical-numbers/discuss/86231/Simple-Java-DFS-Solution
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/5372d418f0614ed4ad468a947cff8f16.png