今天,我正在研究某人使用Python3的堆算法进行回溯的解决方案。解决方案如下:
def permute(self, nums):
def backtrack(start, end):
if start == end:
ans.append(nums[:])
for i in range(start, end):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start+1, end)
nums[start], nums[i] = nums[i], nums[start]
ans = []
backtrack(0, len(nums))
return ans
现在我看到ans.append(nums[:])
这一行,写nums[:]
的意义是什么?不会正确地编写nums
函数吗?
发布于 2019-07-15 08:52:51
不,这是不同的,因为在for循环中,您正在改变nums
nums[start], nums[i] = nums[i], nums[start]
如果您将对nums
的引用附加到您的答案中,而不是添加一个独立的副本,那么您将改变an的所有子元素,并最终得到一个完全相同的排列列表,所有排列都反映了最终的值。您可以简单地尝试一下,并查看结果:
def permute(nums):
def backtrack(start, end):
if start == end:
ans.append(nums)
for i in range(start, end):
# changing sums which will be reflected in all
# references to nums in the ans array
nums[start], nums[i] = nums[i], nums[start]
backtrack(start+1, end)
nums[start], nums[i] = nums[i], nums[start]
ans = []
backtrack(0, len(nums))
return ans
permute([1, 2, 3])
都是一样的:
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
您可以确认它们都指向内存中的同一对象:
l = permute([1, 2, 3])
[id(el) for el in l]
> [140539119291912, # all the same reference
140539119291912,
140539119291912,
140539119291912,
140539119291912,
140539119291912]
通过使用ans.append(nums[:])
,您可以复制一个副本,这样nums
的进一步突变就不会影响您已有的组合。
发布于 2019-07-15 08:50:50
考虑以下几点
>>> a = [1,2,3]
>>> b = [a]
>>> b[0].append(4)
>>> a
[1, 2, 3, 4]
正如您所看到的,修改b[0]
会修改a
,因为您已经将对象a
存储在b
中,而不仅仅是a
的值。使用[:]
创建列表的副本,因此。
>>> a = [1,2,3]
>>> b = [a[:]]
>>> b[0].append(4)
>>> a
[1, 2, 3]
所以关键是要传递值,而不是对象本身。
https://stackoverflow.com/questions/57032196
复制相似问题