來自topcoder srm的特殊字符串問題634 div 2

Question

我的python似乎適用於輸入字符串的長度不是很大，但是很長的字符串失敗了。問題說明如下：

字符串S在滿足以下兩個屬性時稱爲特殊字符： S中的每個字符都是'0'或'1'。 每當S = UV，其中U和V都是非空字符串時，U按照字典順序嚴格小於V. 例如，字符串S =「00101」是特殊的，因爲我們具有「0」<「0101」，「00」<「101」，「001」<「01」和「0010」<「1」。 給你一個保證特殊的字符串電流。設N是當前的長度。考慮按字母順序排列的所有長度爲N的特殊字符串的列表。計算並返回列表中當前緊接的字符串。如果當前恰好是列表中的最後一個字符串，請返回空字符串。

這裏是我的Python代碼：

class SpecialStrings(object): 
    def findNext(self, current): 
     if current == '0': 
      return '1' 
     N = len(current) 
     iter_times = 2 ** N - int(current, 2) - 1 
     temp_current = current 
     for i in range(iter_times): 
      temp_s = self.get_next_string(temp_current) 
      if self.is_special(temp_s): 
       return temp_s 
      if temp_s[0] == '1': 
       return '' 
      temp_current = temp_s 
     return '' 

    def get_next_string(self, s): 
     next_string = bin(int(s, 2) + 1) 
     next_string = next_string[2:] 
     if len(next_string) < len(s): 
      temp_zero = '0' * (len(s) - len(next_string)) 
      next_string = temp_zero + next_string 
     return next_string 

    def is_special(self, s): 
     for i in range(1, len(s)): 
      left = s[:i] 
      right = s[i:] 
      if left >= right: 
       return False 
     return True 

我收到異常終止與輸入 「0111111111111111111111111111」 和 「001111111111111111111111111111111111111111」。當我試圖用它們中的任何一個在本地進行測試時，我的電腦內存已經耗盡......

這裏有什麼問題？是否因爲我的算法效率不高？如何解決它？

非常感謝你!!!!!

Answer 1

您可能正在使用Python2。在Py2中，range()（您的第8行）返回一個列表。例如。 range(3)返回[0,1,2]。因此range(iter_times)會創建一個耗盡內存的大型列表。簡單的解決方法：使用xrange代替。 Refer

---

但隨着xrange，你可能很快得到另一個錯誤：

OverflowError: Python int too large to convert to C long

因爲傳遞給x範圍參數不能超過其最大簽訂長。例如。在我的機器xrange(0x7fffffff)是好的，而xrange(0x80000000)可以觸發錯誤。 Refer

解決方法：在您的第8行中，改爲使用while True:。因爲如果代碼按預期工作，則循環應該在返回for循環結束之前返回結果或空字符串。所以不需要使用for循環。

---

接下來的麻煩，當你使用「而真正的」，輸入「0111111111111111111111111111」應該可以正常工作，但「001111111111111111111111111111111111111111」將繼續計算。這是算法問題。您使用蠻力，預計大型輸入需要很長的計算時間。您可能需要查找特殊字符串的模式以改進算法。