2013-05-02 56 views
0

假設的範圍是:≤X如何生成給定範圍內的迴文數字列表?

這是我曾嘗試:

>>> 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版

回答

5

你的方法可能是:

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

,你可以做到這一點,有一個非線性算法的唯一方法是不是測試生成迴文自己。

迴文可以通過採取以前的迴文生成,並將相同的數字添加到左側和右側,這是一個起點。

比方說,你開始在1:9左右:

111 
212 
313 
... 

而且也,你必須生成多個條目

可能的迴文是通過從1將每個數字獲得每個數字在範圍內相等...

1

這是一個有趣的練習!這裏是我的大上回文數發生器,爲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

2

我覺得這是一個有趣的任務,所以我給了我生鏽的蟒蛇技能一些練習。

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,bx是從1到9的任何數字(加上x可能爲0)。如果4是請求的長度,則模式是abba

generate_palindrome只需要收集所有需要長度的迴文「, 並照顧邊界。

該算法在O(2 * p)中,其中p是迴文數。

該算法確實有效。但是,由於我的python技能很生疏,所以對於更優雅的解決方案的任何建議都是值得讚賞的。

1

如果你想給你immidiately列表這將工作:

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比範圍更好,因爲它處理大列表更好,如記錄here

0

正如@它忍者寫的只是改變的步驟和停止

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

這會給所有的迴文給定範圍內

相關問題