我一直在嘗試使用回溯來解決這個(gè)問題，但在跟蹤找到的答案方面遇到了問題。我的代碼：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"))當(dāng)我嘗試運(yùn)行此代碼時(shí)，它輸出以下內(nèi)容：[[], []]；但我預(yù)料到了這一點(diǎn)[['255', '255', '11', '135'], ['255', '255', '111', '35']]：當(dāng)我取消注釋代碼中的兩個(gè) print() 時(shí)，它輸出以下內(nèi)容：[['255', '255', '11', '135']][['255', '255', '111', '35'], ['255', '255', '111', '35']][[], []]由此我推斷我的邏輯總體上是正確的，但存儲(chǔ)在類ans變量中的答案Solution不知何故搞砸了。有人可以幫我解決這個(gè)問題嗎？感謝，并有一個(gè)愉快的一天！
2 回答
守著星空守著你
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超8個(gè)贊
python 通過引用傳遞參數(shù)，以便path您附加到ans和path.pop()是對象
您需要復(fù)制給回溯的路徑對象（path.copy()在 py3 中，path[:]在 py2 中）：
self.backtrack(path.copy(), s[i:]) ^^^^^^^^^^^
catspeake
TA貢獻(xiàn)1111條經(jīng)驗(yàn) 獲得超0個(gè)贊
您應(yīng)該通過返回值來跟蹤解決方案的狀態(tài)。
當(dāng)找到解決方案時(shí)，您返回True并停止回溯。
聚苯乙烯
您可以將該方法轉(zhuǎn)換為靜態(tài)方法，因?yàn)榇鸢概c對象狀態(tài)無關(guān)Solution，從而能夠使用不同線程解決多個(gè)問題。
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"))
添加回答
舉報(bào)
0/150
提交
取消