我最近一直在練習 leetcode，剛剛完成了“組合總和”的問題（刪節，完整的陳述可以在https://leetcode.com/problems/combination-sum/找到）。
給定一個由不同整數候選者組成的陣列和一個目標整數目標，回傳一個包含所有唯一候選者組合的串列，其中所選數字總和為目標。您可以按任何順序回傳組合。
可以從候選人中無限次選擇相同的數字。如果至少一個所選數字的頻率不同，則兩個組合是唯一的。
我使用簡單的回溯方法正確解決了問題，該方法構建了一個解決方案部分，然后使用以下幫助函式將其附加到陣列 ans（部分是一個串列）
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def helper(candidates, target, partial):
if target == 0:
ans.append(partial[:])
return
if target < 0:
return
for i in range(0,len(candidates)):
partial.append(candidates[i])
helper(candidates[i:], target-candidates[i], partial)
partial.pop()
candidates.sort()
helper(candidates,target,[])
return ans
這段代碼有效，我很滿意。但是，如果我將最后一行更改為：
partial = partial[:-1]
該解決方案不再有效。特別是，元素不會像我想要的那樣被洗掉，并且我的 ans 陣列最終會得到包含大量不正確元素的解決方案。直覺上，我希望這些能夠達到從部分中洗掉最后一個元素的相同目的。
我懷疑這與我缺少的參考和串列切片有關。為什么我解決了電話號碼的 leetcode 問題組合時沒有這個問題（請參閱https://leetcode.com/problems/letter-combinations-of-a-phone-number/），它要求列舉所有可能的給定一串數字，來自數字字母電話映射的字串？
這里我使用了相同的輔助函式結構：
def letterCombinations(self, digits: str) -> List[str]:
ans = []
MAPPING = ('0', '1', "abc", "def", 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz')
def helper(s, partial_sol):
if len(s) == 0:
ans.append(partial_sol)
return
else:
for i in MAPPING[int(s[0])]:
partial_sol = partial_sol i
helper(s[1:], partial_sol)
partial_sol = partial_sol[:-1]
if len(digits) == 0:
return ans
helper(digits, "")
return(ans)
我的解決方案是正確的。請注意，盡管我使用了 [:-1] 方法，該方法不適用于串列上的第一個問題，但適用于字串上的這個問題。所以我可以看到字串與串列的情況是不同的（就像在電話號碼問題中，partial 是字串而不是串列），我只是不知道它到底是什么，或者為什么。
簡而言之，我的問題是：
- Why does my solution for Combination Sum not work when I change from popping partial to:
partial = partial[:-1]
- Why does that solution not work for Combination Sum (which uses lists) but it does for Letters from a Phone Number (which uses strings)?
uj5u.com熱心網友回復：
你是對的，它與參考和list切片有關。
partial.pop()將list系結修改為partial就地。
partial = partial[:-1]制作 的淺拷貝list，并重新系結 partial到新的list.
這是一個重要的區別，因為重新系結不會更改參考原始 的任何其他別名list，其中包括呼叫者對相同的list.的系結。為了使兩個幾乎表現得等效（pop更加高效，而不像切片，將出錯的空白list），你可以使用：
partial[:] = partial[:-1]
它將原始內容重新分配list給淺拷貝的內容，或者具有與以下相同（可能略好）的性能pop：
# Errors on empty list like pop
del partial[-1]
# Or to silently do nothing when applied to an empty list:
del partial[-1:]
它直接洗掉元素而不回傳它。
這些都不能與 一起使用str，因為它們str是不可變的；不可能str在原地修改相同的別名，您只能新建str并重新系結給定名稱，這不適用于這種情況。一個簡單的解決方案是讓您的代碼可以使用str將其轉換為 a list，或者，如果 ASCII/latin-1 字符出現在將str其編碼為bytes然后轉換為bytearray，這是可變的并且可能允許您使用您的代碼更直接地期望可變序列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/406120.html
標籤：