leetcode
leetcode 751 ~ 800
回文质数

回文质数

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.6 MB


/*
 * 思路:
 * 1. 使用Java Stream来简化代码,尤其是在数字生成和过滤的部分。
 * 2. 生成从 n 开始的无限流,并过滤出质数和回文数。
 * 3. 使用 filter 和 findFirst 终结操作来获取第一个符合条件的数字。
 */
import java.util.stream.Stream;

public class Solution {
    public int primePalindrome(int n) {
        return Stream.iterate(n, i -> i + 1)
                     .filter(this::isPalindrome)
                     .filter(this::isPrime)
                     .findFirst()
                     .orElse(-1);
    }

    private boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    private boolean isPalindrome(int num) {
        String s = Integer.toString(num);
        return s.equals(new StringBuilder(s).reverse().toString());
    }
}

解释

方法:

这个题解的思路是预先计算出一系列回文质数,并将它们存储在一个列表中。然后,对于给定的整数 n,它遍历这个列表,找到第一个大于或等于 n 的回文质数,并返回这个数。这种方法的关键在于预计算的回文质数列表必须足够大,以涵盖所有可能的输入值 n。

时间复杂度:

O(k),其中 k 是预先计算的回文质数的数量

空间复杂度:

O(k),其中 k 是预先计算的回文质数的数量

代码细节讲解

🦆
为什么选择预先计算回文质数并存储在列表中,而不是实时计算?这种方法的优势和劣势是什么?
预先计算回文质数并存储在列表中的主要优势是效率。通过预计算并存储这些数,程序可以直接访问这些数据,从而避免了每次查询时重复进行质数检验和回文检验的计算开销。特别是在多次查询时,这种方法可以显著减少总计算时间。然而,这种方法的主要劣势是初始化成本较高(需要预先执行一次较为复杂的计算),并且需要额外的内存空间来存储这个列表。此外,如果输入范围非常广,预先计算出所有可能的回文质数可能会变得不切实际。
🦆
在预先计算回文质数列表时,如何确定列表的大小以确保能覆盖所有可能的输入值n?
在预先计算回文质数列表时,确定列表大小的关键是分析输入值n的可能范围和回文质数的密集程度。一种策略是先设定一个上限(比如2*10^8),然后计算所有小于此上限的回文质数。这样可以确保对于任意小于上限的n,都有一个回文质数可以直接返回。需要注意的是,这种方法的有效性依赖于合理估计输入n的最大可能值,并确保列表在该值以上有足够的回文质数。若实际使用中n的最大值超出预计,列表则需要重新计算和扩展。
🦆
如果输入的n非常接近2*10^8,这种方法的效率如何?是否存在更优的算法来处理这种极端情况?
如果输入的n非常接近2*10^8,该方法的效率取决于列表中是否包含足够靠近2*10^8的回文质数。如果列表中的回文质数足够密集,查找效率依然可以保持较高。但如果列表中没有足够近的数,可能需要扩展列表,这将导致效率降低。对于这种极端情况,可以考虑采用动态计算的策略,即当找不到合适的预存回文质数时,实时计算大于n的下一个回文质数。这种方法虽然计算成本较高,但可以确保总能找到答案,且不受预存数据的限制。

相关问题