请教一个关于Go中的切片问题

采用回溯算法用Go解下面这道组合问题,过程中遇到一个问题!

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

采用典型的回溯算法。

var result [][]int
var nums []int

func combine(n int, k int) [][]int {
    result=[][]int{} 
    nums=[]int{}
    backtracking(n, k, 1)
    return result
}
func backtracking(n, k, start int) {
    if len(nums) == k {
        // 符合条件的组合加入result
        result = append(result, nums)
        //fmt.Println(nums)
        //fmt.Printf("%v,%d,%p\n", result, i, result)
        return // 返回空
    }
    for i := start; i <= n; i++ {
        nums = append(nums, i)
        backtracking(n, k, i+1)
        nums = nums[:len(nums)-1]
    }
}

输出的结果却是:[[4 4] [4 4] [4 4] [4 4] [4 4] [4 4]]
于是通过Println进行测试(代码中注释掉的),结果是[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]证明nums中保存的结果没有问题。
那么很有可能是result = append(result, nums)的问题。于是输出result的值。结果却是:

[[1 2]],0xc000004078
[[1 3] [1 3]],0xc000078480
[[1 4] [1 4] [1 4]],0xc00005e060
[[2 3] [2 3] [2 3] [2 3]],0xc00005e060
[[2 4] [2 4] [2 4] [2 4] [2 4]],0xc00007e000      
[[3 4] [3 4] [3 4] [3 4] [3 4] [3 4]],0xc00007e000

又看了下,而且nums和result地址并不一样, 想不明白为什么会输出这样的结果?

[1],0xc000012088
[1 2],0xc0000120d0
[[1 2]],0xc0000040d8
[1 3],0xc0000120d0
[[1 3] [1 3]],0xc000078480
[1 4],0xc0000120d0
[[1 4] [1 4] [1 4]],0xc00005e060
[2],0xc0000120d0
[2 3],0xc0000120d0
[[2 3] [2 3] [2 3] [2 3]],0xc00005e060
[2 4],0xc0000120d0
[[2 4] [2 4] [2 4] [2 4] [2 4]],0xc00007e000
[3],0xc0000120d0
[3 4],0xc0000120d0
[[3 4] [3 4] [3 4] [3 4] [3 4] [3 4]],0xc00007e000
[4],0xc0000120d0

而输出正确的结果只要,进行如下修改:

var result [][]int
var nums []int

func combine(n int, k int) [][]int {
    result=[][]int{} 
    nums=[]int{}
    backtracking(n,k,1)
    return result
}

func backtracking(n, k, start int) {
    if len(nums)==k {
        temp:=make([]int,k) // 改成如下
        copy(temp,nums)
        result=append(result,temp)
        //result=append(result,nums)
        return // 返回空
    }
    for i:=start;i<=n;i++ {
        nums=append(nums,i)
        backtracking(n,k,i+1)
        nums=nums[:len(nums)-1]
    }
}

结果输出正确结果[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
这是为什么呢?

也有想过可能是append之后存放符合条件组合切片的地址变了,本质上应该是一个深拷贝和浅拷贝混合作用的结果。但还是没能理清楚,不能说服自己。

求大佬指点。

全部评论
因为每次循环中的那个nums底层指向的都是同一个数组吧,后一次循环中往切片里添加的数据覆盖了上一次底层数组中的数据
1 回复 分享
发布于 2022-07-10 20:20
这就是go语言中的解法吧,突然有种不一样的感觉
点赞 回复 分享
发布于 2022-07-01 15:04
result = append(result, append([]int{}, num…))
点赞 回复 分享
发布于 2022-07-16 23:00
因为其实切片是个引用类型的, 按照第一种写法 我们直接append到result中的num, 一直就是num,只是你看着每一次append的值不一样,但我们后面还会对这个num进行修改增加和删除 这样就会影响到result中的结果随着num的改变而改变. 所以需要copy一份新的temp slice 追加到result中~~
点赞 回复 分享
发布于 2022-07-30 13:05

相关推荐

01-15 17:34
保定学院 Java
数学转码崽:学历没优势就得卷项目和实习啊,但是我看了一下你这个项目,什么雪花算法,搜索引擎,Docker,minio这些都属于通用的东西啊,根本不算亮点,没有任何业务相关性。 还有第二个看到统一鉴权,分片上传估计面试官都不想看了。连我一个偶尔刷刷牛客简历的都看多了,面试官估计早都看吐了。。。 秋招结束了,就尽量找找中小厂吧,毕竟你现在转行已经没时间了,高低有一段实习经历
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务