LeetCode 题解工作台
找出最大的 N 位 K 回文数
给你两个 正整数 n 和 k 。 如果整数 x 满足以下全部条件，则该整数是一个 k 回文数 ： x 是一个 回文数 。 x 可以被 k 整除。 以字符串形式返回 最大的 n 位 k 回文数 。 注意 ，该整数 不 含前导零。 示例 1： 输入： n = 3, k = 5 输出： "595" 解释：…
5
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个 正整数 n 和 k。
如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：
x是一个 回文数。x可以被k整除。
以字符串形式返回 最大的 n 位 k 回文数。
注意，该整数 不 含前导零。
示例 1：
输入： n = 3, k = 5
输出： "595"
解释：
595 是最大的 3 位 k 回文数。
示例 2：
输入： n = 1, k = 4
输出： "8"
解释：
1 位 k 回文数只有 4 和 8。
示例 3：
输入： n = 5, k = 6
输出： "89898"
提示：
1 <= n <= 1051 <= k <= 9
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on n and k. With remainder tracking and DP, time is O(n * k) and space is O(n * k) in the worst case. Simple brute force is infeasible due to large n, highlighting the need for state transition optimization. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if you can construct the palindrome from halves rather than brute force.
- question_mark
Watch for handling the modulo of partially built numbers.
- question_mark
Consider state transitions to prune invalid prefixes efficiently.
常见陷阱
外企场景- error
Failing to account for leading zeros when building palindromes.
- error
Recalculating full numbers instead of using remainder DP, causing TLE.
- error
Ignoring symmetric digit placement leading to non-palindromic candidates.
进阶变体
外企场景- arrow_right_alt
Find the smallest n-digit palindrome divisible by k.
- arrow_right_alt
Return all n-digit palindromes divisible by k.
- arrow_right_alt
Determine the largest palindrome divisible by k within a range of n values.