Leetcode386:字典序排数——dfs、迭代
目录
题目
https://leetcode-cn.com/problems/lexicographical-numbers/
日常做不出来😭
题解
什么是字典序？（原谅我到了大二才搞明白什么是字典序😂）
对于字符串，先按首字符排序，如果首字符相同，再按第二个字符排序，以此类推。 如aa,ab,ba,bb,bc就是一个字典序。
dfs
我们可以画一棵树。
第一层设置为0。
第二层是1,2,3…,9
第三层是0,1,2,3,…,9
第四层及往后层都同第三层
深度优先遍历这棵树，记录路径就是答案啦。
当然了，把树具体化为代码其实是一件很难得事情：
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
for i in range(1,10):
if i > n:
break
res.append(i)
self.dfs(i, n, res) # 以i为开头枚举
return res
def dfs(self, i, n, res):
for k in range(0,10):
val = i*10+k
if val > n:
return
else:
res.append(val)
self.dfs(val, n, res)
细节：
- 先枚举1,2,3…,9，因为第一个数不能为0。
- 在后面枚举时要把0加上。
时间复杂度O(n)，空间复杂度O(logn)，主要为栈的开销
迭代法
很有思维的一种方法！
代码：
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
ans = [0] * n
num = 1
for i in range(n):
ans[i] = num
if num * 10 <= n:
num *= 10
else:
while num % 10 == 9 or num + 1 > n:
num //= 10
num += 1
return ans
作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/lexicographical-numbers/solution/zi-dian-xu-pai-shu-by-leetcode-solution-98mz/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。