class Solution {
public:
vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
}
};
2217. 找到指定长度的回文数
给你一个整数数组 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 * 1041 <= queries[i] <= 1091 <= intLength <= 15原站题解
php 解法, 执行用时: 188 ms, 内存消耗: 29.9 MB, 提交时间: 2023-09-04 17:16:50
class Solution {
/**
* @param Integer[] $queries
* @param Integer $intLength
* @return Integer[]
*/
function kthPalindrome($queries, $intLength) {
$ans = array_fill(0, count($queries), 0);
$base = 10 ** intval(($intLength - 1) / 2);
foreach ( $queries as $i => $q ) {
if ( $q > 9 * $base ) {
$ans[$i] = -1;
continue;
}
$v = $base + $q - 1; // 回文数左半部分
$x = $v;
if ( $intLength % 2 == 1 ) $x = intval($x / 10); // 去掉最低位
while ( $x > 0 ) {
$v = $v*10 + $x%10; // 翻转 x 到 v 后
$x = $x = intval($x / 10);
}
$ans[$i] = intval($v);
}
return $ans;
}
}
golang 解法, 执行用时: 68 ms, 内存消耗: 8.6 MB, 提交时间: 2023-09-04 17:10:40
func kthPalindrome(queries []int, intLength int) []int64 {
ans := make([]int64, len(queries))
base := int(math.Pow10((intLength - 1) / 2))
for i, q := range queries {
if q > 9*base {
ans[i] = -1
continue
}
v := base + q - 1 // 回文数左半部分
x := v
if intLength%2 == 1 { x /= 10 } // 去掉最低位
for ; x > 0; x /= 10 {
v = v*10 + x%10 // 翻转 x 到 v 后
}
ans[i] = int64(v)
}
return ans
}
python3 解法, 执行用时: 320 ms, 内存消耗: 26 MB, 提交时间: 2023-09-04 17:10:00
'''
左半：10... 递增
右半: 反转，
'''
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