找到指定长度的回文数
难度:
标签:
题目描述
代码结果
运行时间: 227 ms, 内存: 25.3 MB
/*
* 使用Java Stream的实现方式。
* 思路:
* 1. 判断回文数的长度intLength是奇数还是偶数。
* 2. 生成长度为(intLength + 1) / 2的前缀(回文数的前半部分)。
* 3. 通过前缀生成完整的回文数。
* 4. 如果生成的回文数不足以满足queries的需求,则返回-1。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PalindromeQueriesStream {
public List<Long> kthPalindrome(int[] queries, int intLength) {
int halfLen = (intLength + 1) / 2;
long start = (long) Math.pow(10, halfLen - 1);
long end = (long) Math.pow(10, halfLen) - 1;
return Arrays.stream(queries)
.mapToLong(q -> {
long num = start + q - 1;
if (num > end) {
return -1L;
} else {
StringBuilder sb = new StringBuilder(Long.toString(num));
String palindrome = sb.toString() + sb.reverse().toString().substring(intLength % 2);
return Long.parseLong(palindrome);
}
})
.boxed()
.collect(Collectors.toList());
}
public static void main(String[] args) {
PalindromeQueriesStream pq = new PalindromeQueriesStream();
int[] queries = {1, 2, 3, 4, 5, 90};
int intLength = 3;
System.out.println(pq.kthPalindrome(queries, intLength));
}
}
解释
方法:
此题解采用的方法是先计算出长度为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)
代码细节讲解
🦆
为什么在计算生成回文数的基数`base`时使用了`10 ** ((intLength - 1) // 2)`这个表达式?
▷🦆
在将字符串`s`转换为回文数时,为何奇数长度回文需要去掉一个字符进行反转,而偶数长度直接进行完整反转?
▷🦆
如果`queries`数组中包含重复的值,这种算法处理重复查询是否效率高,还是说存在更优化的处理方法?
▷🦆
题解中提到,如果`q`大于`9 * base`则返回-1。这个`9 * base`的界限是如何确定的,能否解释其背后的数学逻辑?
▷