leetcode
leetcode 1151 ~ 1200
找到指定长度的回文数

找到指定长度的回文数

难度:

标签:

题目描述

代码结果

运行时间: 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)`这个表达式?
这个表达式用于确定回文数的前半部分的起始点。对于一个长度为`intLength`的数字,其前半部分要么包含中间的数字(奇数长度),要么不包含(偶数长度)。例如,长度为3的数,前半部分是两位数(包括中间的一位),长度为4的数,前半部分也是两位数。表达式`10 ** ((intLength - 1) // 2)`计算的是给定长度回文数前半部分的最小值,即`intLength`为3时,基数为10,为4时,基数也为10。这个基数用来生成从最小的该长度回文数开始的数列。
🦆
在将字符串`s`转换为回文数时,为何奇数长度回文需要去掉一个字符进行反转,而偶数长度直接进行完整反转?
在回文数中,如果长度为奇数,中间的字符是对称的轴,不需要重复。因此,生成回文数时,我们取字符串`s`的前半部分加上中间的字符,然后对前半部分(不包括中间字符)进行反转并附加到后半部,从而形成完整的回文数。如果长度为偶数,所有字符都需要有一个对应的镜像字符,因此可以直接将整个前半部分反转并附加到后半部。
🦆
如果`queries`数组中包含重复的值,这种算法处理重复查询是否效率高,还是说存在更优化的处理方法?
这种算法对于包含重复查询值的`queries`数组依然有效,但不是最优的。每个查询都单独计算,即使查询值相同。更优化的方法可以是首先对`queries`进行排序并使用哈希表存储已计算的回文数,这样当遇到重复的查询时,可以直接从哈希表中获取结果,避免重复计算。
🦆
题解中提到,如果`q`大于`9 * base`则返回-1。这个`9 * base`的界限是如何确定的,能否解释其背后的数学逻辑?
界限`9 * base`来自于回文数生成的方式和可能的最大数量。给定一个基数`base`,最小的回文数是`base`(如10),当`intLength`为3时,最大的回文数前半部分是`base + 8`(如18),因此可以生成的回文数数量是9(从10到18)。因此,`9 * base`是指在这个`base`范围内,最多可以生成的不同回文数的数量。如果`q`超过这个范围,说明请求的回文数不存在于当前长度的定义范围内。

相关问题