 字典序遍历)
★ FEATURED ARTICLE 教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文讲解 LeetCode 386「字典序排数」的完整解题思路与 Python 实现给定整数n如何按字典序即按字符串排序规则返回[1, n]中的所有整数并同时满足O(n)时间、常数级辅助空间的限制。核心方法是将数字视为一棵十叉树字典树上的节点通过深度优先搜索DFS进行先序式遍历。读完本文你将掌握「隐式字典树 DFS」这一处理字典序问题的通用框架并能自然迁移到「字典序第 K 小数字」等进阶题目。1. 题目概述1.1 题目链接与基本信息题目编号0386题目名称字典序排数Lexicographical Numbers标签深度优先搜索、字典树难度中等1.2 题目大意给定一个整数n要求按字典序返回范围[1, n]的所有整数并且要求时间复杂度为O(n)空间复杂度为O(1)。以n 13为例字典序排列为[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]可以看到按字典序排序时10排在2之前——因为字符串比较中10小于2。这正是本题与普通数值递增排序[1, 2, ..., 13]的本质区别。2. 解题思路隐式字典树 深度优先搜索2.1 把数字排列看成十叉树的遍历原题解给出的核心思路是按照字典序进行深度优先搜索实质上相当于构造一棵字典树然后将[1, n]中的数插入到字典树中并将遍历结果存储到列表中。这里所谓的字典树并不是真正显式建出来的节点结构而是一种逻辑模型根节点代表「空前缀」第一层子节点是1 ~ 90不能作为数字的开头从任一节点cur出发它的子节点为10 * cur 0到10 * cur 9共 10 个分支每个节点自身就是一个有效整数。因此数字集合天然构成一棵十叉树字典树树中的先序遍历顺序恰好就是字典序。这正是题目标签中「深度优先搜索、字典树」两个关键词的由来。2.2 字典树先序遍历与字典序的关系字典树的「字符串排序」应用在本仓库的字典树章节中有明确说明采用数组方式创建字典树时每个节点的所有子节点都按照其字符大小排序然后对字典树进行先序遍历输出的字符串即为按字典序排序的结果。本题正是把这一性质从「字符串」推广到了「整数」数字cur相当于一个前缀先访问当前数字本身先序根在前再依次访问其 10 个子节点10*cur ii从 0 到 9。仓库中字典树的标准实现string_trie.py以children哈希表存储子节点、isEnd标记单词结尾而本题不需要显式存储任何节点——10 * cur i的递推公式本身就隐含了「子节点指针」因此可以做到只靠递归栈遍历。2.3 DFS 的递归实现与仓库源码印证DFS 的核心是「沿一条路径尽可能深入无法继续时回溯」。本仓库的深度优先搜索教程与图 DFS 实现展示了递归 DFS 的标准形态def dfs_recursive(self, graph, u, visited): print(u) # 访问节点 visited.add(u) # 节点 u 标记其已访问 for v in graph[u]: if v not in visited: self.dfs_recursive(graph, v, visited)对照本题的 DFS这里的「图」是逻辑上无限的十叉树visited集合是不需要的因为数字树天然无环从cur只会走向更大的10*cur i「访问节点」动作替换为res.append(cur)「邻接节点」由for i in range(10): num 10 * cur i生成。3. 代码实现与逐行剖析3.1 完整代码原题解给出的 Python 实现如下class Solution: def dfs(self, cur, n, res): if cur n: return res.append(cur) for i in range(10): num 10 * cur i if num n: return self.dfs(num, n, res) def lexicalOrder(self, n: int) - List[int]: res [] for i in range(1, 10): self.dfs(i, n, res) return res3.2 逐行解读lexicalOrder主函数初始化结果列表res []由于数字不能以0开头因此只在for i in range(1, 10)中依次对1 ~ 9调用dfs每个以不同首位数字开头的分支对应字典树第一层的一个子树。dfs(cur, n, res)递归函数if cur n: return——递归边界当前数字超出[1, n]范围直接剪枝返回res.append(cur)——先序遍历的「访问根」动作先输出当前数字本身。这是保证字典序的关键1一定排在10、11之前10又一定排在100之前for i in range(10)——枚举当前节点的 10 个子分支num 10 * cur i——由父节点推导子节点值对应字典树中「父节点路径 一位数字」if num n: return——由于i递增枚举一旦num n后续更大的i必然也超出范围可以直接返回而非 continue这是关键的剪枝优化self.dfs(num, n, res)——递归深入子树。3.3 递归追踪示例n 13递归调用序列加入 res 的数字dfs(1)1dfs(10)10dfs(11)11dfs(12)12dfs(13)13dfs(2)2dfs(3) ... dfs(9)3, 4, ..., 9最终结果[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]注意10的子树会继续向100等更深层延伸当n足够大时这正是字典序中10排在2之前的原因——深度优先会先把1的整棵子树走完。4. 复杂度分析时间复杂度O(n)每个数字恰好被访问并加入结果列表一次递归调用次数与结果数量成正比空间复杂度O(log n)递归栈的深度由数字位数决定最多为log10(n)层。原题解标注为o(1)从实现结构看这里指的是除结果列表外只使用常数额外状态严格意义上递归调用会占用与数字位数等量的系统栈空间n很大时约为O(log n)。5. 算法要点与边界细节首位不能为 0主函数从1开始枚举而不是0否则会生成0, 01, 02...这类非数字前缀。越界即 return 的剪枝num n时直接return而不是continue因为i单调递增后续分支必然越界这保证了每个节点最多多计算一次越界判断总体仍是O(n)。无需去重与 visited十叉树递推10*cur i严格递增且无环天然不会重复访问节点省去了图 DFS 中的visited集合。空范围处理题目保证n 1[1, n]恒非空。6. 由本题延伸相关字典序题目6.1 字典序的第 K 小数字LeetCode 440本仓库的0440 题解将同一棵十叉树模型用于定位第 K 个节点采用「前缀计数法」定义辅助函数countPrefix(prefix, n)用层次遍历统计以prefix为前缀且不超过n的数字个数countPrefix(1, 13) 7包含1, 10, 11, 12, 13countPrefix(2, 13) 1只包含2。若count k说明目标不在当前前缀子树下跳过k - countprefix 1若count k说明目标在当前子树中深入一层k - 1prefix * 10。该题时间复杂度为O(log²n)与本题的O(n)全量遍历形成对照当 n 极大而只需要单个排名时前缀计数法能避免全量 DFS。这与 0386 的 DFS 先序遍历互为补充是理解字典序问题的一对最佳组合。6.2 其他涉及字典序/字典树思想的题目0440 字典序的第K小数字困难字典树0386 字典序排数中等深度优先搜索、字典树字典树基础讲解见04_08_trie.md其「字符串排序」一节直接论证了先序遍历输出即字典序的原理7. 总结LeetCode 386「字典序排数」是一道典型的「数据结构思想 遍历算法」结合题思想层面将[1, n]的整数映射为一棵隐式十叉树字典树利用字典树先序遍历输出字典序的性质实现层面用递归 DFS 配合10*cur i的递推公式隐式建树避免显式分配节点从而以O(n)时间完成遍历进阶方向把「全量先序遍历」升级为「前缀计数定位」即可解决 440 这类大范围字典序查找问题。掌握这道题你就同时掌握了字典树先序性质、DFS 递归遍历两个基础工具并能在字符串与整数两类字典序场景间自如切换。参考资料本题题解原文docs/solutions/0300-0399/lexicographical-numbers.md字典树教程docs/04_string/04_08_trie.md字典树实现源码codes/python/04_string/string_trie.py深度优先搜索教程docs/06_graph/06_03_graph_dfs.md图 DFS 递归实现源码codes/python/06_graph/Graph-DFS.py进阶题解0440 字典序的第K小数字docs/solutions/0400-0499/k-th-smallest-in-lexicographical-order.md赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐算法通关手册 · LeetCode 0014 最长公共前缀纵向遍历与字典树双解法详解算法通关手册 · LeetCode 0014 最长公共前缀纵向遍历与字典树双解法详解 本篇指南基于「算法通关手册」AlgoNote仓库中 docs/sol教程文档知识库LeetCode 124 二叉树中的最大路径和DFS 后序遍历与 O(n) 最优解全解析LeetCode 124 二叉树中的最大路径和DFS 后序遍历与 O n 最优解全解析 本文以仓库中 binary tree maximum path sum示例工程教程AlgoNote 算法通关手册LeetCode 31「下一个排列」字典序排列题解与双指针实现解析AlgoNote 算法通关手册LeetCode 31「下一个排列」字典序排列题解与双指针实现解析 本文基于《算法通关手册》AlgoNote题解库中 003教程文档知识库上一篇手势识别积木编程实战2个核心积木块3步快速打造免触控交互下一篇PaddleNLP 多轮对话精调指南从 chat_template 配置到源码级原理解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
