LeetCode Weekly 92:867. 回文素数

先来看一下题目:

LeetCode 867. 回文素数

求出大于或等于 N 的最小回文素数。

回顾一下,如果一个数大于 1,且其因数只有 1 和它自身,那么这个数是素数

例如,2,3,5,7,11 以及 13 是素数。

回顾一下,如果一个数从左往右读与从右往左读是一样的,那么这个数是回文数。

例如,12321 是回文数。

示例 1:

输入:6
输出:7

示例 2:

输入:8
输出:11

示例 3:

输入:13
输出:101

提示:

  • 1 <= N <= 10^8
  • 答案肯定存在,且小于 2 * 10^8

分析

我当时做的时候是先写了一个生成器找素数,然后判断是不是回文数,素数生成器是这样的:

class Solution:
    def get_primes(self):
        primes = [2]
        yield primes[0]
        now = 3
        while True:
            if not any(now % prime == 0 for prime in primes if prime < now ** 0.5 + 1):
                yield now
                primes.append(now)
            now += 1
    
    def primePalindrome(self, N):
        """
        :type N: int
        :rtype: int
        """
        primes = self.get_primes()
        prime = next(primes)
        while prime < N:
            prime = next(primes)
        is_palindrome = lambda s: str(s) == ''.join(list(str(s))[::-1])
        while not is_palindrome(prime):
            prime = next(primes)
        return(prime)

很遗憾这个方案超时了,因为在N很大的时候,他会找出所有比N小的素数,显然是不现实的。

我们仔细分析一下就会知道,其实回文数是比素数更苛刻的要求,因为10101的下一个回文数是10201,而这中间还有一百个数,其中自然会有素数。

另外找到下一个比N大的回文数比找下一个比N大的素数简单很多。具体的方案是这样子的:

  1. 如果N是回文数直接返回,
  2. 根据整数N产生三个字符串front,middle和end,其中front是前半部分,如果N的位数是奇数的话middle是中间的数字否则middle为空,end是front的逆序字符串,
  3. 判断front+middle+end拼成的整数是否比N大,是的话返回这个整数,
  4. 否的话查找下一个比(front + middle + 1) + end拼成的整数大的回文数。

例如寻找比122大的回文数:

  1. 122不是回文数,生成front=‘’1‘’,middle=‘’2‘’,end=‘’1‘’三个字符串,
  2. 生成的整数121比122小,开始找比131大的回文数,
  3. 132是回文数,返回。

我们不断根据这个方法找到新的回文数,然后判断是否为素数就可以了。

代码实现

def nextPalindrome(n):
    is_palindrome = lambda s: str(s) == ''.join(list(str(s))[::-1])
    if is_palindrome(n):
        return n
    original = str(n)
    front = original[:len(original) // 2]
    middle = original[len(original) // 2] if len(original) % 2 else ''
    end = front[::-1]
    mirror = int(front + middle + end)
    if mirror > n:
        return mirror
    else:
        return nextPalindrome(int(str(int(front + middle) + 1) + end))
def is_prime(n):
    return not any(n % x == 0 for x in range(2, int(n ** 0.5) + 1))
class Solution:
    def primePalindrome(self, N):
        """
        :type N: int
        :rtype: int
        """
        find = False
        n = nextPalindrome(N)
        while not find:
            if is_prime(n):
                find = True
            else:
                n = nextPalindrome(n + 1)
        return n

N=10000的话结果是10301,这个算法只判断了10101,10201,10301三个数是不是素数,还是很高效的。如果是最初的算法,只是找到比10000大的素数就已经超时了。

结语

要善于把握不同的选择方案的成本,在这个例子中找下一个回文数的成本比找下一个素数的成本小得多。

最后祝大家享受生活,享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菜鸟前端工程师

JavaScript学习笔记020-日期对象0倒计时

1021
来自专栏desperate633

LintCode 硬币排成线 II题目分析代码

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币,直到没有硬币为止。计算两个人分别拿到的硬币总价值,价值高的人获胜。

662
来自专栏owent

POJ PKU 3277 City Horizon 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3277

823
来自专栏数说工作室

庖丁解牛切割数据!| 【SAS Says·扩展篇】

【SAS Says·扩展篇】庖丁解牛割数据! | 3. call PRXSUBSTR () 0. 前集回顾 1. 新的问题 2. 初识 PRXSUBSTR() ...

3326
来自专栏菩提树下的杨过

ruby学习笔记(4)-动态修改类的属性

动态语言之所以“动态”,最明显的特征就是:类实例的行为/属性可以在new出后,动态修改!个人觉得这种处理相对java/c#(静态语言)来说,更符合现实世界。 ...

1997
来自专栏我的小碗汤

栈:我们能干的事情多着呢

老师:同学们大家好,这些节课我们来讲一下栈。那么什么是栈呢。栈是一种后进先出的线性表,它是按照后进先出的原则存储数据。Last In First Out ,简称...

803
来自专栏大数据挖掘DT机器学习

[笔记]使用Python一步一步地来进行数据分析

原文 http://www.cnblogs.com/nxld/p/6058998.html 你已经决定来学习Python,但是你之前没有编程经验。因此,你常常...

7136
来自专栏专知

【LeetCode 500】关关的刷题日记27 Keyboard Row

关关的刷题日记27 – Leetcode 500. Keyboard Row 题目 Given a List of words, return the word...

2975
来自专栏小工匠技术圈

【Java小工匠聊高并发】--CountDownLatch

  在讲CountDownLatch的应用场景之前,我们先在现实生活中,找到一个对应的场景。例如班主任带一帮孩子去春游,春游回家前,班主任需要清点人数,确保每个...

1263
来自专栏JAVA高级架构开发

面向对象编程,再见!

作为程序员,你是使用函数式编程还是面向对象编程方式?在本文中,拥有 10 多年软件开发经验的作者从面向对象编程的三大特性——继承、封装、多态三大角度提出了自己的...

2730

扫码关注云+社区

领取腾讯云代金券