Golang生成组合错误。

Question

Golang生成组合错误。

3

我正在处理一个编程问题

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数字的组合。

当输入 n = 5，k = 4 时，输出应为[[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]]，以下是我的 Golang 解决方案：

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

我认为我的解决方案是正确的，但它返回了[[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]]。

调试后，我发现在一开始将[1 2 3 4]添加到结果中，但后来更改为[1 2 3 5]，导致出现两个[1 2 3 5]的重复。但我无法找出问题所在。

- Tsonglew

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leaf bebop · Accepted Answer

这是在使用append时常见的错误。

当你运行c:=append(*comb,i)代码时，它会尝试首先使用底层数组中分配的内存来添加新项，只有在无法这样做时才创建一个新的切片。因为它们共享同一块基础内存，所以这就是将[1 2 3 4]变为[1 2 3 5]的原因。

要解决这个问题，在想要追加到结果中时请先进行复制。

now := make([]int,len(*comb))
copy(now,*comb)
*result = append(*result,now)

或者使用复制的快捷方式:

*result = append(*result, append([]int{},*comb...))

更新：

要理解我所说的底层内存，就必须先了解 Go 语言切片的内部模型。

在 Go 语言中，切片有一个名为 SliceHeader 的数据结构，可以通过 reflect 包访问，并且在使用 unsafe.Sizeof 和取地址时引用它。

SliceHeader 负责三个元素：Len、Cap 和一个指向包含切片数据的内存的 Ptr。前两个元素很简单：它们就是 len() 和 cap() 的作用。最后一个元素是一个 uintptr 类型的指针，指向切片所包含的数据的内存。

当你进行浅复制（shallow-copy）一个切片时，会创建一个新的 SliceHeader，但其中包含相同的内容，包括 Ptr。因此，底层内存不会被复制，而是共享的。