如何在给定的范围内生成回文数字列表？

Question

假设范围是：1≤X≤120

这就是我尝试过的：

>>> def isPalindrome(s):
    ''' check if a number is a Palindrome '''
    s = str(s)
    return s == s[::-1]

>>> def generate_palindrome(minx,maxx):
    ''' return a list of Palindrome number in a given range '''
    tmpList = []
    for i in range(minx,maxx+1):
        if isPalindrome(i):
            tmpList.append(i)

    return tmpList

>>> generate_palindrome(1,120)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111]

然而，这是O(n)。

如何改进此算法以使其更快？

PS.这是Python 2.7

Answer 1

你的方法可能是：

palindromes = [x for x in xrange(min, max) if isPalindrome(x)]

唯一的方法就是自己生成回文，而不是测试。

一个回文可以通过取上一个回文，并在左右两侧添加相同的数字来生成，所以这是一个起点。

假设您从1开始：

可能的回文是通过将从1:9到左右的每个数字相加得到的：

111
212
313
...

而且，还必须生成几个条目，其中每个数字在范围内都相等。。。

Answer 2

如果您希望它立即给您一个列表，这将起作用：

def palindrome_range(start,stop,step=1):
    ret=[x for x in xrange(start,step,stop) if str(x)==str(x)[::-1]]
    return ret

但是，如果需要生成器，可以使用：

def palindrome_range(start,stop,step=1):
    for x in xrange(start,stop,step):
        if str(x)==str(x)[::-1]:
            yield x

这将有助于你在很大程度上加快事情取决于你在使用它。例如，如果您想遍历回文，那么生成器将很好地为您服务。但是，如果需要整个列表，则返回常规列表会更好。然而，值得注意的是，在这种情况下，xrange比range要好得多，因为它处理大列表更好，如文档所述here。

Answer 3

我发现这是一个有趣的任务，所以我给了我生锈的Python技能一些练习。

def generate_palindromes_with_length(l):
''' generate a list of palindrome numbers with len(str(palindrome)) == l '''
    if l < 1:
        return []
    if l == 1:
        return [x for x in range(10)]
    p = []
    if (l % 2):
        half_length = (l - 1) / 2
        for x in xrange(0, 10):
            for y in xrange(10 ** (half_length - 1), 10 ** half_length):
                p.append(int(str(y) + str(x) + str(y)[::-1]))
    else:
        half_length = l / 2
        for x in xrange(10 ** (half_length - 1), 10 ** half_length):
            p.append(int(str(x) + str(x)[::-1]))
    p.sort()
    return p


def generate_palindrome(minx, maxx):
''' return a list of palindrome numbers in a given range '''
    min_len = len(str(minx))
    max_len = len(str(maxx))
    p = []
    for l in xrange(min_len, max_len + 1):
        for x in generate_palindromes_with_length(l):
            if x <= maxx and x >= minx:
                p.append(x)
    p.sort
    return p

generate_palindromes_with_length是这里的关键部分。该函数生成具有给定小数位数的回文。它对小数点后的奇数和偶数使用不同的策略。示例：如果请求长度5，它将生成模式为abxba的回文，其中a、b、x是1到9之间的任意数字（加上x可以是0）。如果4是请求的长度，则模式为abba。

generate_palindrome只需要收集所有所需长度的回文， 还要注意边界。

算法是O（2*p），p是回文数。

算法确实有效。然而，由于我的python技术已经不成熟，任何关于更优雅的解决方案的建议都是值得赞赏的。