教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于「算法通关手册AlgoNote」仓库中的 0247. 中心对称数 II 题解系统讲解如何生成所有长度为 n 的「中心对称数」旋转 180° 后仍与自身相同的数字。你将掌握中心对称数字的旋转映射关系、从外向内递归构造的完整思路与可运行代码、奇偶长度边界处理以及该解法的时间/空间复杂度分析。通过本文你可以独立写出这套递归构造模板并能将其迁移到同系列的「中心对称数 III区间计数」等进阶问题。一、题目背景与理解1.1 题目大意给定一个整数 $n$要求返回所有长度为 $n$ 的「中心对称数」返回顺序不限。说明中心对称数指一个数字在旋转了 180 度之后看起来依旧相同的数字或者上下颠倒地看。数据范围$1 \le n \le 14$。示例输入n 2 输出[11,69,88,96] 输入n 1 输出[0,1,8]1.2 中心对称数在算法题系列中的位置在 AlgoNote 的题解体系中「中心对称数」是一个三题递进系列见 0200-0299 题解索引题号题目核心任务难度主要方法0246. 中心对称数判断给定字符串是否为旋转对称简单哈希表 双指针0247. 中心对称数 II生成长度为 n 的全部中心对称数中等递归构造0248. 中心对称数 III统计 $[low, high]$ 区间内的中心对称数个数困难递归生成 计数本文聚焦其中的 0247它既是 0246 判断逻辑的「生成」版本又是 0248 区间计数的基础只要掌握了如何枚举所有长度为 n 的中心对称数0248 只需在生成结果上增加范围过滤即可。二、核心预备知识旋转映射关系中心对称数旋转 180° 后仍然有意义只有 5 个数字可以参与构造$0$ 旋转后还是 $0$$1$ 旋转后还是 $1$$6$ 旋转后变成 $9$$8$ 旋转后还是 $8$$9$ 旋转后变成 $6$。其他数字如 $2, 3, 4, 5, 7$旋转后无法形成有效数字因此不可能出现在中心对称数中。在代码中这组映射既可以组织为成对列表本解法所用也可以组织为字典0246、0248 所用# 0247 采用成对列表遍历时同时取 left / right 两个字符 strobogrammatic_pairs [ (0, 0), (1, 1), (6, 9), (8, 8), (9, 6) ] # 0246 采用字典用于双指针判断 strobogrammatic_map { 0: 0, 1: 1, 6: 9, 8: 8, 9: 6 }注意一个容易混淆的细节$6$ 与 $9$ 是互相旋转的关系而不是自对称因此在构造「对数」时必须写成(6, 9)和(9, 6)两个方向分别代表「左 6 右 9」与「左 9 右 6」两种布局。三、解题思路从外向内递归构造3.1 核心思想观察中心对称数的结构可知旋转前后保持对称意味着数字两端成对出现且越靠近中间的位置越对称。因此可以采用「从两端向中间」的递归构建方式对于长度为 $n$ 的中心对称数从两端开始构建每次选择一对可以相互旋转的数字 $(a, b)$其中 $a$ 旋转后变成 $b$递归处理中间部分直到构建完成特殊情况当 $n$ 为奇数时最中间位置只能放置自对称数字 $0, 1, 8$当 $n$ 为偶数时从空字符串开始向两侧扩展不能以 $0$ 开头除非 $n 1$即最外层不能放0以避免出现前导零。3.2 递推公式视角用递归「三步法」可参考仓库基础教程 07_02 递归算法可以这样拆解递推公式$f(m) { left s right \mid (left, right) \in pairs, \ s \in f(m-2) }$终止条件$f(0) {}$偶数长度基准$f(1) {0, 1, 8}$奇数长度基准翻译为代码定义build_strobogrammatic(m)递归函数主体遍历映射对拼接先判断终止条件。之所以每次递归长度减 2是因为每在外层套上一对 $(left, right)$可用的中间区域就向中心收拢 2 位。3.3 前导零过滤递归构造天然会产出0...开头的候选串因为映射对中包含(0, 0)。这些串在 $n 1$ 时不构成合法的整数表示必须在最后统一过滤$n 1$直接返回全部候选此时只有0, 1, 8三个$n 1$只保留不以0开头的候选。这也解释了为什么内部位置允许出现0如1001、8008都是合法中心对称数只有最外层受限制——该约束与 0248 题解中「最外层不能是 0内层可以是 0」的说明完全一致。四、完整代码与逐步运行演示4.1 参考代码以下代码与原题解保持一致补充了类型与注释可直接运行from typing import List class Solution: def findStrobogrammatic(self, n: int) - List[str]: # 定义中心对称数字的映射关系成对列表left 旋转后为 right strobogrammatic_pairs [ (0, 0), (1, 1), (6, 9), (8, 8), (9, 6) ] def build_strobogrammatic(m: int) - List[str]: # 递归构建长度为 m 的中心对称数 if m 0: return [] # 偶数长度的基准空字符串 if m 1: return [0, 1, 8] # 奇数长度的基准中间位自对称数字 # 递归构建中间部分长度减少 2 inner build_strobogrammatic(m - 2) result [] for left, right in strobogrammatic_pairs: for inner_str in inner: # 在中间部分两端套上对称的一对数字 result.append(left inner_str right) return result # 获取所有可能的中心对称数候选 candidates build_strobogrammatic(n) # 过滤掉以 0 开头的数字除非 n 1 if n 1: return candidates return [num for num in candidates if not num.startswith(0)]4.2 逐步推演n 2以 $n 2$ 为例递归过程如下build_strobogrammatic(2)调用build_strobogrammatic(0)返回[]遍历 5 对映射对每个内层空串拼接(0,0)→00(1,1)→11(6,9)→69(8,8)→88(9,6)→96得到候选[00, 11, 69, 88, 96]过滤掉以0开头的00最终输出[11, 69, 88, 96]与题目示例一致。4.3 逐步推演n 3对于奇数长度 $n 3$build_strobogrammatic(3)调用build_strobogrammatic(1)返回[0, 1, 8]遍历 5 对映射将每对数字套在0 / 1 / 8两侧得到[000, 010, 080, 101, 111, 181, 609, 619, 689, 808, 818, 888, 906, 916, 986]等 15 个候选过滤掉以0开头的 3 个最终得到 12 个结果如101, 111, 181, 609, ...。可以验证无论 $n$ 奇偶中间位置始终取自{0, 1, 8}奇数时显式给出偶数时空串本质等价而外层位置始终遍历 5 对映射并去除前导零。五、复杂度分析原题解给出的复杂度结论为时间复杂度$O(5^{n/2} \times n)$其中 $n$ 是目标长度。每次递归有 5 种选择递归深度为 $n/2$每个结果字符串长度为 $n$空间复杂度$O(5^{n/2} \times n)$需要存储所有可能的中心对称数结果含递归调用栈与结果列表。由于 $n \le 14$$5^{n/2}$ 的量级在本题数据范围内完全可控。从更细的粒度看长度为 $n$ 时最外层不能为0故有 $4$ 种选择其余每层含中间层有 $5$ 种选择最终结果数量约为 $4 \times 5^{n/2 - 1}$每个结果的字符串拼接与startswith(0)过滤均需 $O(n)$ 时间因此总时间复杂度为「结果数 × 字符串长度」。六、变体与延伸从「生成」到「计数」掌握 0247 的递归构造后可以无缝迁移到同系列其他题目1. 判断0246无需生成直接用哈希表 双指针从两端向中间校验旋转映射关系时间复杂度 $O(n)$、空间复杂度 $O(1)$参见 0246 题解。2. 区间计数0248在递归生成基础上做两点改动增加length参数使「最外层不能为 0」的约束只在最外层生效生成所有长度位于 $[\text{len}(low), \text{len}(high)]$ 的候选后先比较长度再按字典序过滤进 $[low, high]$ 区间计数返回。 完整实现与复杂度推导见 0248 题解。3. 方法论归属从仓库的算法基础教程看0247 的解法属于典型的**递归递推公式 终止条件**应用参见 07_02 递归算法当递归过程包含「试错 撤销选择」时则进入回溯范畴可参考 07_04 回溯算法。本题的「从外向内成对套壳」模式本质上是一种按位置约束枚举所有解的结构化搜索与回溯问题中「逐位枚举 合法性剪枝」的决策树思想相通。七、易错点与要点小结映射方向别写反6与9互为旋转成对列表必须双向各写一条否则会漏解中间位限制长度为奇数时中间位只能是0, 1, 8自对称数字递归基准m 1返回[0, 1, 8]即体现了这一约束前导零过滤n 1时必须以not num.startswith(0)过滤且应放在递归完成之后统一处理而不是在递归内禁止(0,0)因为内部层允许 0复杂度记忆结果数量级为 $O(5^{n/2})$配合每个字符串的 $O(n)$ 构建成本得到 $O(5^{n/2} \times n)$ 的总复杂度系列题打通0246判断→ 0247生成→ 0248计数难度递进共享同一张旋转映射表建议对照阅读。八、相关资源本题题解原文档docs/solutions/0200-0299/strobogrammatic-number-ii.md系列题目0246 中心对称数、0248 中心对称数 III算法基础07_02 递归算法、07_04 回溯算法题解总览0200-0299 章节索引、题库列表赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 0112 路径总和Path Sum全解AlgoNote 算法通关手册中的递归 DFS 判定法LeetCode 0112 路径总和Path Sum全解AlgoNote 算法通关手册中的递归 DFS 判定法 本文依据 path sum.md http教程文档知识库gqlgen 错误处理完全指南向 GraphQL 响应发送自定义错误数据gqlgen 错误处理完全指南向 GraphQL 响应发送自定义错误数据 导读 本文以 gqlgen 官方参考文档 docs/content/referenc教程文档知识库AlgoNote「算法通关手册」题解LeetCode 390 消除游戏——递归与数学规律的 O(log n) 解法AlgoNote「算法通关手册」题解LeetCode 390 消除游戏——递归与数学规律的 O log n 解法 导读 本文是「算法通关手册」 LeetCod教程文档知识库上一篇高效保存全网视频3步实现多平台离线观看下一篇Steam Economy Enhancer5分钟掌握Steam库存批量管理的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考