SPOJ Next Palindrome

我想解決SPOJ問題5：爲給定的輸入找到下一個最大的整數「迴文」;也就是說，十進制表示法中的整數從左到右和從右到左讀取相同的整數。SPOJ Next Palindrome

請看看這個問題here

而不是使用蠻力搜索的，我試着計算下一個迴文。但我的代碼仍然返回TLE（即超出時間限制），我很沮喪...你介意給我一個提示嗎？

這是我在Python 3.X

if __name__ == '__main__': 
    n = int(input()) 
    for i in range(n): 
     string = input() 
     length = len(string) 
     ans = "" 
     if length %2 == 0 : 
      half = length // 2 
      str_half = string[0:half] 
      ans = str_half + str_half[::-1]   
      if(ans <= string): 
       str_half = str(int(str_half) + 1) 
       ans = str_half + (str_half[0:half])[::-1] 
      print(ans) 
     else: 
      half = length // 2 
      str_half = string[0:half] 
      ans = str_half + string[half] + str_half[::-1] 
      if(ans<= string):    
       str_half = str(int(str_half+string[half]) + 1) 
       ans = str_half + (str_half[0:half])[::-1] 
      print(ans)

來源

2012-01-12 Bear

什麼輸入失敗？什麼投入工作？ – sarnold 2012-01-12 02:15:25

什麼是TLE？ 15字符 – Woot4Moo 2012-01-12 02:16:06

我認爲沒有輸入失敗... TLE意味着超出時間限制 – Bear 2012-01-12 02:17:23

輸入可能很長。問題陳述說「不超過1000000位」。所以可能有幾十個數字的測試用例。將這樣一根弦分成兩半，顛倒一半並追加它們需要一點時間。但據我所知，Python的字符串處理非常好，所以這只是對這個問題的一小部分貢獻。

什麼是長時間是將這種長度的字符串轉換爲數字和巨大的數字字符串。對於K = 10 ** 200000 + 2，單獨的步驟str_half = str(int(str_half+string[half]) + 1)在這裏幾乎花了一秒鐘。計算機上的速度可能會更快，但是SPOJ的機器速度很慢，其中一種情況可能會使您超出時間限制。

所以你必須避免轉換，直接在字符串表示（數字的可變列表）上工作。

來源

2012-01-12 12:14:16

thx，AC現在:)，str_half = str（int（str_half + string [half]）+ 1）是真正的原因！ – Bear 2012-01-12 12:33:59

不錯。恭喜AC。 – 2012-01-12 12:35:09

代碼因此，基於這個問題讓找出最長的迴文是什麼的情況下K.length == 1。這個情況可以安全地忽略，因爲沒有大於作爲K的迴文的K的值。這同樣適用於K.length == 2。因此，僞代碼，以評估這看起來如下：

if K.length <= 2 
    pass

當K.length == 3，我們關心的值是K [0]和K [2]這給了我們的邊界。例如K == 100。我們關心的值是1和0。如果K [0]是大於比K [2]我們知道我們必須使K [2] = K [0]並且我們完成了。另一個例子是K == 200第一個大的值是202，這是第一個相等的素數。如果K [0] == K [2]和K < 999，我們將K [1]增加1，然後完成。僞代碼如下：

if K[0] > K[2] 
     K[2] = K[0] 
if K[0] == K[2] and K < 999 
     K[1]++

如果K中的所有值都是9（999,9999等），則將K增加2並結束該過程。我會將算法的一般形式留給你，除非你最終被卡住了。

來源

2012-01-12 02:36:08 Woot4Moo

SPOJ Next Palindrome

回答

相關問題