Medium

题目描述

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

回文数是正着读和倒着读都一样的数字。回文数不能有前导零。

示例 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^4
  • 1 <= queries[i] <= 10^9
  • 1 <= intLength <= 15

提示：

  • 对于任意的 queries[i] 和 intLength 值，你如何检查是否至少存在 queries[i] 个长度为 intLength 的回文数？
  • 由于回文数正着读和倒着读都一样，考虑如何有效地找到回文数的前一半（ceil(intLength/2) 位数字）。

解题思路

解题思路

这道题的关键洞察是：回文数由其前一半数字完全确定，后一半是前一半的镜像。

核心思路：

  1. 对于长度为 n 的回文数，我们只需要确定前 ceil(n/2) 位数字
  2. 例如长度为 5 的回文数 12321，只需要确定前 3 位 123，后面的 21 是 12 的镜像
  3. 长度为 4 的回文数 1221，只需要确定前 2 位 12，后面的 21 是 12 的镜像

算法步骤：

  1. 计算前一半的长度：halfLen = ceil(intLength / 2)
  2. 计算前一半可能的数字范围：从 10^(halfLen-1) 到 10^halfLen - 1
  3. 总的回文数个数为：10^halfLen - 10^(halfLen-1)
  4. 如果查询的序号超过总数，返回 -1
  5. 否则，找到对应的前一半数字，然后构造完整的回文数

构造回文数：

  • 奇数长度：前一半 + 去掉最后一位的前一半的逆序
  • 偶数长度：前一半 + 前一半的逆序

时间复杂度 O(q × intLength)，其中 q 是查询次数，空间复杂度 O(1)。

代码实现

class Solution {
public:
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        vector<long long> result;
        
        // 计算前一半的长度
        int halfLen = (intLength + 1) / 2;
        
        // 前一半的最小值和最大值
        long long halfStart = pow(10, halfLen - 1);
        long long halfEnd = pow(10, halfLen) - 1;
        
        // 总的回文数个数
        long long totalCount = halfEnd - halfStart + 1;
        
        for (int query : queries) {
            if (query > totalCount) {
                result.push_back(-1);
                continue;
            }
            
            // 找到对应的前一半
            long long halfNum = halfStart + query - 1;
            
            // 构造回文数
            string halfStr = to_string(halfNum);
            string palindrome = halfStr;
            
            // 根据长度奇偶性添加后一半
            if (intLength % 2 == 0) {
                // 偶数长度：直接镜像
                reverse(halfStr.begin(), halfStr.end());
                palindrome += halfStr;
            } else {
                // 奇数长度：去掉中间数字后镜像
                reverse(halfStr.begin(), halfStr.end());
                palindrome += halfStr.substr(1);
            }
            
            result.push_back(stoll(palindrome));
        }
        
        return result;
    }
};

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        result = []
        
        # 计算前一半的长度
        half_len = (intLength + 1) // 2
        
        # 前一半的最小值和最大值
        half_start = 10 ** (half_len - 1)
        half_end = 10 ** half_len - 1
        
        # 总的回文数个数
        total_count = half_end - half_start + 1
        
        for query in queries:
            if query > total_count:
                result.append(-1)
                continue
            
            # 找到对应的前一半
            half_num = half_start + query - 1
            
            # 构造回文数
            half_str = str(half_num)
            
            if intLength % 2 == 0:
                # 偶数长度：直接镜像
                palindrome = half_str + half_str[::-1]
            else:
                # 奇数长度：去掉中间数字后镜像
                palindrome = half_str + half_str[-2::-1]
            
            result.append(int(palindrome))
        
        return result

public class Solution {
    public long[] KthPalindrome(int[] queries, int intLength) {
        long[] result = new long[queries.Length];
        
        // 计算前一半的长度
        int halfLen = (intLength + 1) / 2;
        
        // 前一半的最小值和最大值
        long halfStart = (long)Math.Pow(10, halfLen - 1);
        long halfEnd = (long)Math.Pow(10, halfLen) - 1;
        
        // 总的回文数个数
        long totalCount = halfEnd - halfStart + 1;
        
        for (int i = 0; i < queries.Length; i++) {
            if (queries[i] > totalCount) {
                result[i] = -1;
                continue;
            }
            
            // 找到对应的前一半
            long halfNum = halfStart + queries[i] - 1;
            
            // 构造回文数
            string halfStr = halfNum.ToString();
            string palindrome = halfStr;
            
            // 根据长度奇偶性添加后一半
            if (intLength % 2 == 0) {
                // 偶数长度：直接镜像
                char[] chars = halfStr.ToCharArray();
                Array.Reverse(chars);
                palindrome += new string(chars);
            } else {
                // 奇数长度：去掉中间数字后镜像
                char[] chars = halfStr.ToCharArray();
                Array.Reverse(chars);
                palindrome += new string(chars, 1, chars.Length - 1);
            }
            
            result[i] = long.Parse(palindrome);
        }
        
        return result;
    }
}

/**
 * @param {number[]} queries
 * @param {number} intLength
 * @return {number[]}
 */
var kthPalindrome = function(queries, intLength) {
    const result = [];
    const halfLen = Math.ceil(intLength / 2);
    const start = Math.pow(10, halfLen - 1);
    const end = Math.pow(10, halfLen) - 1;
    const maxPalindromes = end - start + 1;
    
    for (let query of queries) {
        if (query > maxPalindromes) {
            result.push(-1);
            continue;
        }
        
        const halfNum = start + query - 1;
        const halfStr = halfNum.toString();
        let palindrome;
        
        if (intLength % 2 === 0) {
            palindrome = halfStr + halfStr.split('').reverse().join('');
        } else {
            palindrome = halfStr + halfStr.slice(0, -1).split('').reverse().join('');
        }
        
        result.push(parseInt(palindrome));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(q × intLength)q 为查询次数，每次查询需要 O(intLength) 时间构造回文数字符串
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目