教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以「宫水三叶的刷题日记」仓库中 LeetCode/471-480/479. 最大回文数乘积困难.md 为核心完整还原这道困难题的数学推导与「枚举 数学」解法并结合仓库源码逐行拆解其实现细节、剪枝技巧与复杂度边界。读完本文你将掌握「回文数构造 因子分解枚举」这一类题目的通用思考路径能够独立推导并实现任意 $n$ 位整数乘积的最大回文数求解方案。题目描述与输入输出约定给定一个整数 $n$返回可表示为两个 $n$ 位整数乘积的最大回文整数。 因为答案可能非常大所以返回它对 $1337$ 取余的结果。Tag「枚举」、「数学」难度困难数据范围$1 \le n \le 8$示例分析示例 1输入n 2 输出987 解释99 x 91 9009, 9009 % 1337 987这里9009是回文数正读反读一致且可以分解为两个 2 位数99与91的乘积在「两个 2 位整数乘积」所能构成的所有回文数中9009是最大者取模 $1337$ 后得到987。示例 2输入n 1 输出91 位数的乘积范围为 $1 \times 1$ 到 $9 \times 9$其中最大的回文数是9可表示为 $3 \times 3$ 或 $9 \times 1$ 等直接输出9。关键约定两个因子必须是恰好 $n$ 位的整数即取值范围为 $[10^{n-1}, 10^n - 1]$返回值是对 $1337$ 取余后的结果而非回文数本身$n$ 最大为 8这意味着回文数可能高达 16 位远超int表示范围实现时必须使用long等 64 位类型。核心思路一乘积的位数只有两种可能对于两个 $n$ 位整数 $a, b$取值范围 $[10^{n-1}, 10^n - 1]$它们的乘积 $P a \times b$ 满足$$ 10^{2n-2} \le P \le (10^n - 1)^2 10^{2n} $$因此 $P$ 的位数要么是 $2n$要么是 $2n - 1$。原题解给出了一个关键结论当 $n 1$ 时我们总能在数位为 $2n$ 的乘积中找到答案。也就是说两个 $n$ 位整数可以乘出一个恰好 $2n$ 位的回文数且这个数必然不小于任何 $2n-1$ 位的回文乘积因为 $2n$ 位数的数量级本身就大于 $2n-1$ 位数。因此搜索时只需关注 $2n$ 位的回文数即可。边界情况$n 1$ 时$2n 2$ 位乘积中最大的回文数是99但99 9 × 11而 11 不是 1 位数无法分解为两个 1 位整数因此需要单独处理直接返回9。这正是题解代码中第一行if (n 1) return 9;的由来。核心思路二回文数的前半部分唯一决定整体回文数的本质特性是「左右对称」因此一个 $2n$ 位的回文数其前半部分高 $n$ 位唯一决定了后半部分低 $n$ 位只需枚举前半部分再将后半部分「镜像」拼接即可构造出完整回文数。设枚举到的前半部分为 $i$构造完整回文数的过程为num i 的完整数值 t i while t ! 0: num num * 10 (t % 10) t / 10这个过程等价于把i的十进制位按从低位到高位的顺序依次「追加」到num的末尾。例如i 99时num 99, t 99第 1 轮num 99 * 10 9 999t 9第 2 轮num 999 * 10 9 9999t 0得到回文数9999前半99 后半镜像99。再如i 12时得到1221。关键优化点由于目标是「最大回文数」只需按照从大到小的顺序枚举前半部分 $i$从 $10^n - 1$ 递减到 $0$那么第一个能被分解为两个 $n$ 位整数乘积的回文数就一定是全局最大解无需继续搜索。一个 $n$ 位数的最大值为 $10^n - 1$例如 $n 2$ 时为 99因此枚举起点为max 10^n - 1。核心思路三利用乘法交换律只枚举较大因子构造出候选回文数num后需要判断它能否分解成两个 $n$ 位整数的乘积即是否存在 $a, b \in [10^{n-1}, 10^n - 1]$ 使得 $a \times b num$。由于乘法满足交换律$a \times b b \times a$枚举数对 $(a, b)$ 时只需要枚举其中的较大者避免重复检查。题解代码中的内层循环for (long j max; j * j num; j--) { if (num % j 0) return (int)(num % 1337); }这里有两个重要细节枚举方向j从max即 $10^n - 1$开始递减保证检查的是数对中的较大因子终止条件j * j num一旦j小于 $\sqrt{num}$那么即使存在因子也必然已经在前面的枚举中作为「较大因子」被检查过另一因子更大因此无需继续。同时若j 10^{n-1}则较小因子必然不是 $n$ 位数同样无需继续——终止条件j * j num恰好把这两类情况一并覆盖是一个简洁而完整的剪枝。当num % j 0时说明num可分解为 $j$ 与 $num / j$且两者都是 $n$ 位数num / j j max且大于等于 $10^{n-1}$此时num就是答案返回num % 1337。完整代码与逐行解读原题解给出的 Java 实现如下题解文档class Solution { public int largestPalindrome(int n) { if (n 1) return 9; // n 1 时不存在两位的 1 位数因子分解直接返回 int max (int) Math.pow(10, n) - 1; // n 位数的最大值如 n 2 时为 99 for (int i max; i 0; i--) { // 按从大到小枚举回文数前半部分 long num i, t i; while (t ! 0) { // 镜像拼接后半部分构造完整回文数 num num * 10 (t % 10); t / 10; } for (long j max; j * j num; j--) { // 只枚举较大的因子 j并剪枝到 sqrt(num) if (num % j 0) return (int)(num % 1337); // 找到能整除的 n 位因子即为最大解 } } return -1; // 理论不可达仅保证编译完整性 } }逐行要点代码位置作用细节说明if (n 1) return 9;处理边界两位回文99无法分解为两个 1 位数最大的可行解是 1 位数9int max (int) Math.pow(10, n) - 1;计算枚举上界Math.pow返回double需强转int$n \le 8$ 时 10^n - 1 \le 99999999$不会溢出long num i, t i;初始化用long承接拼接结果避免 16 位回文数溢出intwhile (t ! 0)镜像构造逐位取t的最低位拼接到num尾部构造出 $2n$ 位回文for (long j max; j * j num; j--)因子枚举利用交换律只枚举较大因子j * j num是关键的 $\sqrt{num}$ 剪枝if (num % j 0) return (int)(num % 1337);命中返回第一个被整除的回文数即为最大解按题意取模 $1337$复杂度分析时间复杂度$O(10^{2n})$外层循环枚举回文串前半部分复杂度为 $O(10^n)$内层循环检查回文数能否被分解为 $n$ 位因子最坏情况下枚举 $O(10^n)$ 个j整体为两层枚举的乘积 $O(10^n \times 10^n) O(10^{2n})$。虽然 $n \le 8$ 时最坏情况是 $10^{16}$ 量级但得益于「从大到小枚举 首个命中即返回」的策略实际平均运行次数远低于上界。空间复杂度$O(1)$仅使用若干常数级变量无额外数据结构。从源码结构看该题在仓库中的定位本仓库LogicStack-LeetCode是「刷穿 LeetCode」系列的文章集合每篇题解文档同时挂靠在多个按 Tag 分类的索引下。本题在仓库中的定位可以从以下两条线索确认数学索引Index/数学.md 第 39 行收录了 479. 最大回文数乘积推荐指数 与本题的「枚举 数学」Tag 完全对应回文串索引Index/回文串问题.md 收录了 5. 最长回文子串、9. 回文数、131. 分割回文串、132. 分割回文串 II 等题目可作为回文类问题的横向对比阅读。由此可以推断仓库中的索引体系Index/目录与题解正文LeetCode/目录是一一对应的同一道题可以同时出现在多个 Tag 索引中便于读者按算法思想检索同类题目这也正是本题「枚举 数学」双 Tag 的原因。关联题解回文数问题家族对比本题的核心操作是「构造回文数」与「判断回文数」这两点在仓库中还有更基础的同族题目可以对照学习1. 回文数判断——9. 回文数简单该题给出了三种判断整数是否为回文的方法字符串解法转字符串后翻转比较时间与空间复杂度均为 $O(\log_{10} n)$完全翻转用long承接翻转结果后与原值比对避免int溢出部分翻转利用「前半部分 后半部分翻转」的特性只翻转到一半处理回文长度为奇/偶两种情况x t || x t / 10时间复杂度 $O(\log_{10} n)$、空间复杂度 $O(1)$。本题正是把「部分翻转」的思想反向运用由前半部分正向构造出完整回文数再结合数学枚举寻找最大可行解。2. 字符串回文——5. 最长回文子串中等 与 131/132. 分割回文串这几题处理的是「字符串中的回文子串」涉及中心扩展、Manacher、动态规划与回溯剪枝等技巧与本题的「整数回文构造」互为补充。若想系统梳理回文类问题可参照 Index/回文串问题.md 中的完整题目清单。延伸思考为什么返回-1是理论不可达的代码末尾的return -1;在 $n 1$ 时已被前置分支拦截在 $n \ge 2$ 时根据原题解的结论「数位为 $2n$ 的乘积中总能找到回文答案」外层循环必然命中某个合法回文数因此-1永远不会被返回它仅是为了满足 Java 方法必须返回int的编译约束而存在的兜底语句。另外值得注意的一个实现细节是外层循环的终止条件是i 0即前半部分可以枚举到0。当i 0时构造出的回文数是0虽然它本身也是回文且满足分解$0 0 \times 0$但 $0$ 不是 $n$ 位数不过由于算法保证在 $i$ 更大时就能命中答案这一分支在实际执行中不会真正影响结果。小结一道题的完整解题链回顾整道题解题链条可以归纳为四个步骤定位答案位数两个 $n$ 位数的乘积只有 $2n$ 或 $2n-1$ 位且 $n 1$ 时答案必在 $2n$ 位中缩小枚举空间回文数的后半部分由前半部分唯一确定只需枚举前半部分且按从大到小顺序保证「首中即最优」构造回文数用num num * 10 (t % 10)的逐位镜像法构造 $2n$ 位回文分解检验利用乘法交换律只枚举较大因子并以j * j num完成 $\sqrt{num}$ 剪枝。这一「构造 枚举 剪枝」的组合拳是处理「最大回文乘积」「最大回文子串」「回文数判断」等回文族问题的通用方法论也正是本题被归类为「枚举 数学」双 Tag 的原因所在。对照仓库中 Index/数学.md 与 Index/回文串问题.md 的题目清单反复练习即可将这类题目的套路内化。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐AlgoNote 题解精讲 | LeetCode 0479「最大回文数乘积」数学推导 回文数构造枚举法AlgoNote 题解精讲 | LeetCode 0479「最大回文数乘积」数学推导 回文数构造枚举法 本文基于「算法通关手册AlgoNote」的 0教程文档知识库LogicStack-LeetCode 题解精读LeetCode 952 按公因数计算最大组件大小枚举质因数 并查集LogicStack LeetCode 题解精读LeetCode 952 按公因数计算最大组件大小枚举质因数 并查集 本文基于 LogicStack教程文档LogicStack-LeetCode 题解精讲LeetCode 1775 通过最少操作次数使数组的和相等枚举 贪心 数学LogicStack LeetCode 题解精讲LeetCode 1775 通过最少操作次数使数组的和相等枚举 贪心 数学 本篇技术指南围绕「宫水教程文档上一篇Astryx 贡献指南深度解读PR 意图、公共 API 与 CLI 约定全解析下一篇OpenProject 12.2.4 版本解析journal 数据清理迁移与四项关键缺陷修复创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考