在Golang中使用回溯算法时如何正确复制数组?

2024年 2月 14日 75.5k 0

在golang中使用回溯算法时如何正确复制数组?

在Golang中使用回溯算法时,正确复制数组是一个重要的问题。回溯算法通常需要在递归过程中对数组进行修改,但有时我们需要保存原始数组的状态以便回溯到上一步。在这种情况下,我们不能简单地将原始数组直接赋值给一个新变量,因为它们共享同一块内存空间,修改一个数组会影响到另一个数组。解决这个问题的方法是使用深拷贝,即创建一个新的数组并将原始数组的值依次复制到新数组中。在Golang中,可以使用copy()函数来完成这个操作,它会按字节级别复制数组的内容,确保新数组和原始数组完全独立。通过正确复制数组,我们可以在回溯算法中安全地操作数组,而不会影响到原始数据的状态。

问题内容

我有一个带有值 [1, 2, 3] 的简单数组,我想找到所有排列。我不明白为什么在循环中断程序之前移动“复制”部分代码。

func generatePermutations(curr, remains []int) [][]int {
if len(remains) == 0 {
return [][]int{curr}
}

var res [][]int

// DOESN'T WORK
c, r := make([]int, len(curr)), make([]int, len(remains))
copy(c, curr)
copy(r, remains)

for i := 0; i 登录后复制

当复制位于循环之外时,结果如下:
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

当复制位于循环内时,结果如下:
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

在第一个输出中,有两个带有 [3,3,3] 的数组,这是错误的

解决方法

你说我既不修改“c”或“r”也不附加到它们,这部分是正确的。

在循环的第一次迭代中,
切片 ccurr 指向不同的支持数组,所以这很好。

但是当你这么做的时候

curr = c

登录后复制

稍后,您实际上将两个切片分配为指向同一个支持数组。

这意味着在第二次迭代中,您的 append 可以修改 currcurr (“可以”,因为调整大小会更改 curr 的支持数组)。

这就是导致您在上面看到的奇怪行为的原因。

go 中的切片有点棘手,所以当你知道你会改变并传递它们时,最好避免分配,而是坚持完全复制它们(就像在“works”情况下所做的那样)。

为了进一步阅读,这是一个很好的资源:https://go.dev/blog/slices-简介

以上就是在Golang中使用回溯算法时如何正确复制数组?的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论