假设范围为：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
您的方法可以是：
palindromes = [x for x in xrange(min, max) if isPalindrome(x)]
你能做到这一点并使用非线性算法的唯一方法是自己生成回文，而不是测试。
回文可以通过取前一个回文，并在左侧和右侧添加相同的数字来生成，所以这是一个起点。
假设您从1:开始
可能的回文是通过将1:9的每个数字左右相加获得的：
111
212
313
...
而且，你必须生成几个条目，其中每个数字在范围内都相等。。。
我觉得这是一项有趣的任务，所以我对我生疏的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。
CCD_ 11只需要收集所有所需长度的回文’，并注意边界。
该算法在O(2*p(中，其中p是回文数。
算法确实有效。然而，由于我的python技能已经生疏，任何关于更优雅解决方案的建议都值得赞赏。
这是一个有趣的练习！这是我对回文数生成器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。
如果你想让它立即给你一个列表，这将起作用：
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要好得多，因为它更好地处理大列表，如本文所述。
受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，但与OP的版本进行了简单的经验比较，对于基数为10的所有小于1000000的回文，我用OP的版本得到了约400ms，用我的版本得到约0.7ms。
附言：这可以扩展到高于10的基数，但这需要在两个生成器中使用明确的预定义数字数组，而不是范围。
正如@it忍者所写的那样，只需更改步骤并停止
def palindrome_range(start,stop,step=1):
ret=[x for x in xrange(start,stop,step) if str(x)==str(x)[::-1]]
return ret
这将给出给定范围内的所有回文