题目
难度：★★★☆☆
类型：数组
方法：深度优先搜索
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
解答
从解决问题的角度来说，python很友好：
class Solution:
def lexicalOrder(self, n):
return sorted(range(1, n+1), key=str)
但是从学习的角度来说，我们用深度优先搜索来做：
我们从1位数开始，位数逐渐增加，用深度优先搜索遍历所有的情况：
1位数：0到9；
2位数：10到99:；
3位数：100到999；
...
定义结果列表，用于按题目要求顺序添加整数，定义深度优先搜索函数，函数输入为10的倍数，在入口处设置判断，排除已经超过给定值的情况，然后将该数乘以10，研究以该数为十位数的所有数字。通过递归调用实现所有数字的添加。
class Solution:
def lexicalOrder(self, n):
res = []
def dfs(cur):
if cur > n:
return
else:
res.append(cur)
for i in range(10):
if 10 * cur + i > n:
return
dfs(10 * cur + i)
for i in range(1, 10):
dfs(i)
return res
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
