1.题目描述

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

2.解题思路

将数列模拟成十叉树，先序遍历即可

3.代码实现

class Solution(object): def dfs(self,k,n,res): # 过滤掉第一个数 0 if k!=0: res.append(k) # 每一层次的遍历依赖于i的移动 for i in range(0,10): # 先序遍历 1，10，11，12，...,19,100,101,102,...199 # k*10+i>0：保证第一个数0不参与dfs if k*10+i<=n and k*10+i>0: self.dfs(k*10+i,n,res) def lexicalOrder(self, n): """ :type n: int :rtype: List[int] """ res=[] self.dfs(0,n,res) return res