找到指定长度的回文数

难度: Medium

给你一个整数数组 queries 和一个正整数 intLength ，请你返回一个数组 answer ，其中 answer[i] 是长度为 intLength 的 正回文数 中第 queries[i] 小的数字，如果不存在这样的回文数，则为 -1 。

回文数 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。

示例 1：

输入：queries = [1,2,3,4,5,90], intLength = 3
输出：[101,111,121,131,141,999]
解释：
长度为 3 的最小回文数依次是：
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
第 90 个长度为 3 的回文数是 999 。

示例 2：

输入：queries = [2,4,6], intLength = 4
输出：[1111,1331,1551]
解释：
长度为 4 的前 6 个回文数是：
1001, 1111, 1221, 1331, 1441 和 1551 。

提示：

1 <= queries.length <= 5 * 10⁴
1 <= queries[i] <= 10⁹
1 <= intLength <= 15

Submission

运行时间: 227 ms

内存: 25.3 MB

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        ans = [-1] * len(queries)
        base = 10 ** ((intLength - 1) // 2)
        for i, q in enumerate(queries):
            if q <= 9 * base:
                s = str(base + q - 1)
                s += s[-2::-1] if intLength % 2 else s[::-1]
                ans[i] = int(s)
        return ans

Explain

此题解采用的方法是先计算出长度为intLength的回文数的生成基数base。如果intLength是奇数，回文数的前半部分长度为(intLength // 2) + 1，如果是偶数，则为intLength // 2。然后基于base生成回文数。例如，如果intLength为3，base为10，那么第一个回文数是101 (即base + 0)，第二个是111 (即base + 1)，以此类推。对于每个查询q，如果q小于或等于9 * base（最大可能的回文数数量），那么生成第q个回文数；否则，返回-1。生成回文数时，对于奇数长度的回文，将s的前半部分除去最后一个字符后反转并拼接；对于偶数长度的回文，直接将s反转并拼接。

时间复杂度: O(m * n)

空间复杂度: O(m)

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        ans = [-1] * len(queries)  # 初始化答案数组为-1
        base = 10 ** ((intLength - 1) // 2)  # 计算回文数的生成基数
        for i, q in enumerate(queries):  # 遍历每个查询
            if q <= 9 * base:  # 检查是否有足够的回文数可以生成
                s = str(base + q - 1)  # 生成回文数的前半部分
                if intLength % 2 == 1:
                    s += s[-2::-1]  # 奇数长度回文，去掉一个字符反转
                else:
                    s += s[::-1]  # 偶数长度回文，完整反转
                ans[i] = int(s)  # 将生成的回文数转换为整数并存储
        return ans  # 返回答案

Explore

这个表达式用于确定回文数的前半部分的起始点。对于一个长度为`intLength`的数字，其前半部分要么包含中间的数字（奇数长度），要么不包含（偶数长度）。例如，长度为3的数，前半部分是两位数（包括中间的一位），长度为4的数，前半部分也是两位数。表达式`10 ** ((intLength - 1) // 2)`计算的是给定长度回文数前半部分的最小值，即`intLength`为3时，基数为10，为4时，基数也为10。这个基数用来生成从最小的该长度回文数开始的数列。

在回文数中，如果长度为奇数，中间的字符是对称的轴，不需要重复。因此，生成回文数时，我们取字符串`s`的前半部分加上中间的字符，然后对前半部分（不包括中间字符）进行反转并附加到后半部，从而形成完整的回文数。如果长度为偶数，所有字符都需要有一个对应的镜像字符，因此可以直接将整个前半部分反转并附加到后半部。

这种算法对于包含重复查询值的`queries`数组依然有效，但不是最优的。每个查询都单独计算，即使查询值相同。更优化的方法可以是首先对`queries`进行排序并使用哈希表存储已计算的回文数，这样当遇到重复的查询时，可以直接从哈希表中获取结果，避免重复计算。

界限`9 * base`来自于回文数生成的方式和可能的最大数量。给定一个基数`base`，最小的回文数是`base`（如10），当`intLength`为3时，最大的回文数前半部分是`base + 8`（如18），因此可以生成的回文数数量是9（从10到18）。因此，`9 * base`是指在这个`base`范围内，最多可以生成的不同回文数的数量。如果`q`超过这个范围，说明请求的回文数不存在于当前长度的定义范围内。