2

假设范围是：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

4

6 回答 6

7

你的方法可能是：

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

您可以做到这一点并拥有非线性算法的唯一方法是自己生成回文，而不是测试。

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

假设您从以下位置开始1：

可能的回文数是通过将 1:9 的每个数字添加到左侧和右侧来获得：

111
212
313
...

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

于 2013-05-02T17:43:53.327 回答
4

我觉得这是一项有趣的任务，所以我对我生疏的 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 技能生疏，任何关于更优雅解决方案的建议都值得赞赏。

于 2013-05-02T18:54:37.307 回答
2

这是一个有趣的运动！这是我对回文数生成器 O(n^(1/2)) 的看法：

def palindrome_number_generator():
    yield 0    
    lower = 1
    while True:
        higher = lower*10
        for i in xrange(lower, higher):    
            s = str(i)
            yield int(s+s[-2::-1])
        for i in xrange(lower, higher):    
            s = str(i)
            yield int(s+s[::-1])
        lower = higher


def palindromes(lower, upper):
    all_palindrome_numbers = palindrome_number_generator()
    for p in all_palindrome_numbers:
        if p >= lower:
            break
    palindrome_list = [p]
    for p in all_palindrome_numbers:
        # Because we use the same generator object,
        # p continues where the previous loop halted.
        if p >= upper:
            break
        palindrome_list.append(p)
    return palindrome_list


print palindromes(1, 120)

因为它是数字，所以生成器必须单独处理 0：它应该包含 0 但不包含 010。

于 2013-05-02T17:57:02.820 回答
1

如果您希望它立即为您提供列表，这将起作用：

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在这种情况下，这比范围要好得多，因为它更好地处理大列表，如此处所述。

于 2013-05-02T19:24:50.907 回答
1

受 Quant Metropolis 答案的启发，这是我对在不同基础（从 2 到 10）中生成回文的看法。

首先，我们定义一个辅助生成器，它为我们提供所需长度的所有数字：

def nums_in_base(ndigits=3, b=10, _toplevel=True):
    """
    generate all nubmers in the given base of the given length
    `_toplevel` controls whether to add 0 at the beginning in the process of recursive calls
    """
    if ndigits == 0:
        yield ''
    else:
        for num in nums_in_base(ndigits-1, b, False):
            for i in range(int(_toplevel), b):
                yield str(i) + num

请注意，它返回字符串。

现在我们编写回文生成器本身：

def any_base_digit_palindromes(n_max_half_digits, b=10):
    """
    generate all palindromes in the given base and
    less than the given length
    palindromes consist of two parts, `n_max_half_digits` controls
    the maximum length of those halves 
    i.e., real max length of a palindrome is double the `n_max_half_digits`
    """
    if n_max_half_digits > 1:
        yield from digit_palindromes(n_max_half_digits - 1, b)

    for num in nums_in_base(n_max_half_digits, b):
        yield num + num[-2::-1]
        yield num + num[::-1]

不确定 big-O，但对于所有小于 1,000,000 的以 10 为底的回文数，我与 OP 的版本进行了简单的经验比较，我的 OP 版本约为 400 毫秒，我的版本约为 0.7 毫秒。

PS 这可以扩展到高于 10 的基数，但这需要在两个生成器中使用明确的预定义数字数组而不是范围。

于 2020-03-01T22:49:21.000 回答
0

就像@it-ninja 写的那样，改变步骤并停止

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

这将给出给定范围内的所有回文

于 2016-06-01T17:01:10.363 回答