LeetCode 题解工作台
k 镜像数字的和
一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。 比方说， 9 是一个 2 镜像数字。 9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。 相反地， 4 不是一个 2 镜像数字。 4 在二进制下为 100…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数学·结合·enumeration
答案摘要
对于一个 k 镜像数字，我们可以将其分为两部分：前半部分和后半部分。对于偶数长度的数字，前半部分和后半部分完全相同；对于奇数长度的数字，前半部分和后半部分相同，但中间的数字可以是任意数字。 我们可以通过枚举前半部分的数字，然后根据前半部分构造出完整的 k 镜像数字。具体步骤如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·enumeration 题型思路
题目描述
一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。
- 比方说，
9是一个 2 镜像数字。9在十进制下为9，二进制下为1001，两者从前往后读和从后往前读都一样。 - 相反地，
4不是一个 2 镜像数字。4在二进制下为100，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。
示例 1：
输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
十进制 二进制
1 1
3 11
5 101
7 111
9 1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。
示例 2：
输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
十进制 三进制
1 1
2 2
4 11
8 22
121 11111
151 12121
212 21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。
示例 3：
输入：k = 7, n = 17 输出：20379000 解释：17 个最小的 7 镜像数字分别为： 1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
提示：
2 <= k <= 91 <= n <= 30
解题思路
方法一：折半枚举 + 数学
对于一个 k 镜像数字，我们可以将其分为两部分：前半部分和后半部分。对于偶数长度的数字，前半部分和后半部分完全相同；对于奇数长度的数字，前半部分和后半部分相同，但中间的数字可以是任意数字。
我们可以通过枚举前半部分的数字，然后根据前半部分构造出完整的 k 镜像数字。具体步骤如下：
- 枚举长度：从 1 开始枚举数字的长度，直到找到满足条件的 k 镜像数字。
- 计算前半部分的范围：对于长度为 的数字，前半部分的范围是 。
- 构造 k 镜像数字：对于每个前半部分的数字 ，如果长度为偶数，则直接将 作为前半部分；如果长度为奇数，则将 除以 10 得到前半部分。然后将前半部分的数字反转并添加到后半部分，构造出完整的 k 镜像数字。
- 检查 k 镜像数字：将构造出的数字转换为 k 进制，检查其是否是回文数。
- 累加结果：如果是 k 镜像数字，则将其累加到结果中，并减少计数器 。当计数器 减至 0 时，返回结果。
时间复杂度主要取决于枚举的长度和前半部分的范围。由于 的最大值为 30，因此在实际操作中，枚举的次数是有限的。空间复杂度 ，因为我们只使用了常数级别的额外空间。
class Solution:
def kMirror(self, k: int, n: int) -> int:
def check(x: int, k: int) -> bool:
s = []
while x:
s.append(x % k)
x //= k
return s == s[::-1]
ans = 0
for l in count(1):
x = 10 ** ((l - 1) // 2)
y = 10 ** ((l + 1) // 2)
for i in range(x, y):
v = i
j = i if l % 2 == 0 else i // 10
while j > 0:
v = v * 10 + j % 10
j //= 10
if check(v, k):
ans += v
n -= 1
if n == 0:
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(1) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Understand the importance of generating numbers that are palindromes in both base-10 and base-k.
- question_mark
Recognize that brute-force checking all numbers is inefficient and a more optimized approach is needed.
- question_mark
Evaluate how well the candidate numbers are being generated and filtered for the k-mirror condition.
常见陷阱
外企场景- error
Failing to optimize the search space and brute-forcing all potential numbers, which results in inefficiency.
- error
Misunderstanding the dual palindrome condition for base-10 and base-k, leading to incorrect numbers being considered.
- error
Overcomplicating the solution by not focusing on direct number generation strategies for palindromes.
进阶变体
外企场景- arrow_right_alt
Generalize the approach to handle larger values of n, beyond the limit of 30.
- arrow_right_alt
Consider how the algorithm might be adjusted if k were allowed to be greater than 9.
- arrow_right_alt
Investigate the performance of the solution for edge cases, such as when n = 1 or k = 2.