我一直在嘗試使用回溯來解決這個問題，但在跟蹤找到的答案方面遇到了問題。我的代碼：class Solution: def restore_ip(self, s): self.ans = [] self.backtrack([], s) return self.ans def backtrack(self, path, s): if s == "" and len(path) == 4: #print(self.ans) self.ans.append(path) #print(self.ans) return if s == "" or len(path) >= 4: return for i in range(1, len(s)+1): if i > 3: break if int(s[:i]) > 255: break if i != 1 and s[0] == 0: break path.append(s[:i]) self.backtrack(path, s[i:]) path.pop()a = Solution()print(a.restore_ip("25525511135"))當我嘗試運行此代碼時，它輸出以下內容：[[], []]；但我預料到了這一點[['255', '255', '11', '135'], ['255', '255', '111', '35']]：當我取消注釋代碼中的兩個 print() 時，它輸出以下內容：[['255', '255', '11', '135']][['255', '255', '111', '35'], ['255', '255', '111', '35']][[], []]由此我推斷我的邏輯總體上是正確的，但存儲在類ans變量中的答案Solution不知何故搞砸了。有人可以幫我解決這個問題嗎？感謝，并有一個愉快的一天！
2 回答
守著星空守著你
TA貢獻1799條經驗 獲得超8個贊
python 通過引用傳遞參數，以便path您附加到ans和path.pop()是對象
您需要復制給回溯的路徑對象（path.copy()在 py3 中，path[:]在 py2 中）：
self.backtrack(path.copy(), s[i:]) ^^^^^^^^^^^
catspeake
TA貢獻1111條經驗 獲得超0個贊
您應該通過返回值來跟蹤解決方案的狀態。
當找到解決方案時，您返回True并停止回溯。
聚苯乙烯
您可以將該方法轉換為靜態方法，因為答案與對象狀態無關Solution，從而能夠使用不同線程解決多個問題。
class Solution:
def restore_ip(self, s):
self.ans = []
self.backtrack([], s)
return self.ans
def backtrack(self, path, s):
if s == "" and len(path) == 4:
self.ans = path
return True
if s == "" or len(path) >= 4:
return False
for i in range(1, len(s)+1):
if i > 3:
break
if int(s[:i]) > 255:
break
if i != 1 and s[0] == 0:
break
path.append(s[:i])
if self.backtrack(path, s[i:]):
return True
path.pop()
a = Solution()
# ['255', '255', '11', '135']
print(a.restore_ip("25525511135"))
添加回答
舉報
0/150
提交
取消