时间戳

首页 > 解决方案 > 将数组附加到矩阵时的奇怪行为

go - 将数组附加到矩阵时的奇怪行为

问题描述

我错过了一些关于切片的基本知识，这导致我的结果最终看起来很奇怪。

是的，这是来自 leetcode 的一个问题。我用它来学习围棋，因为我发现用新语言解决算法对我很有帮助。我不需要算法的答案，也不需要知道如何修复算法。我只想知道为什么当我附加另一个值时我的附加值会发生变化。

首先这是我的代码：

type node struct {
    value int
    children []*node
}

func combinationSum(candidates []int, target int) [][]int {
    
    var output [][]int
    
    var acc []int
    
    combinationSum2(candidates, &output, target, acc, 0)
    
    return output
}

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {
    
    if(sum == target) {
        fmt.Println(acc)
        *output = append(*output, acc)
        fmt.Println(output)
        return
    }
    
    if(sum > target) {
        return
    }
    
    for i := 0; i < len(candidates); i++ {
        combinationSum2(candidates[i:], output, target, append(acc, candidates[i]), sum + candidates[i])
    }
    
}

我正在使用 Candidate=[2,3,5] 和 target=8 测试这段代码

正确的输出应该是 [[2,2,2,2],[2,3,3],[3,5]]；但是，我的代码返回 [[2,2,2,5],[2,3,3],[3,5]]

有趣的是，当我在 if 语句中记录 acc 值和附加 acc 值后的输出时，似乎我附加的值在附加第二个数组后发生了变化。

acc = [2 2 2 2]
output = &[[2 2 2 2]]

acc = [2 3 3]
output = &[[2 2 2 5] [2 3 3]]

acc = [3 5]
output = &[[2 2 2 5] [2 3 3] [3 5]]

我尝试在本地运行它，并得到相同的奇怪行为。这是什么原因造成的？

标签： go

解决方案

正如我在评论中所写，原始代码中的问题在于combinationSum2函数中的附加用法。append用于传递由电流acc扩展的电流到candidate方法combinationSum2。我已向此功能添加了更多日志记录

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {
    if sum == target {
        fmt.Println("Acc:", acc)
        *output = append(*output, acc)
        fmt.Println("Output:", output)
        return
    }

    if sum > target {
        return
    }

    for i := 0; i < len(candidates); i++ {
        extendedAcc := append(acc, candidates[i])
        fmt.Printf("Extended: %v %p\n", extendedAcc, extendedAcc)
        combinationSum2(candidates[i:], output, target, extendedAcc, sum+candidates[i])
    }
}

并收到以下结果（这只是几个有趣的第一行）

Extended: [2] 0x14000130008
Extended: [2 2] 0x14000130030
Extended: [2 2 2] 0x1400013c020
Extended: [2 2 2 2] 0x1400013c020
Acc: [2 2 2 2]
Output: &[[2 2 2 2]]
Extended: [2 2 2 3] 0x1400013c020
Extended: [2 2 2 5] 0x1400013c020
Extended: [2 2 3] 0x1400013c040
Extended: [2 2 3 3] 0x1400013c040

如您所见，extendedAcc添加后的变量Output仍然具有相同的地址（它们在值之后打印为十六进制）。该地址的最终值[2 2 2 5]就是您在 中看到的值Output。它不是的原因是[2 2 3 3]append 在内部如何工作的结果。如果当前数组中没有足够的空间，它会创建一个新数组并返回一个切片给它。当您比较extendedslice 的地址时，这种行为是可见的。

这是正常工作的解决方案：

package main

import "fmt"

type node struct {
    value    int
    children []*node
}

func combinationSum(candidates []int, target int) [][]int {
    var output [][]int
    var acc []int
    combinationSum2(candidates, &output, target, acc, 0)
    return output
}

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {
    if sum == target {
        fmt.Println(acc)
        *output = append(*output, acc)
        fmt.Println(output)
        return
    }

    if sum > target {
        return
    }

    for i := 0; i < len(candidates); i++ {
        currentAcc := make([]int, 0, len(acc) + 1)
        currentAcc = append(currentAcc, acc...)
        currentAcc = append(currentAcc, candidates[i])
        combinationSum2(candidates[i:], output, target, currentAcc, sum+candidates[i])
    }
}

func main() {
    combinationSum([]int{2, 3, 5}, 8)
}

或者，该combinationSum2函数可能如下所示：

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {
    if sum == target {
        fmt.Println(acc)
        accCopy := make([]int, 0, len(acc))
        accCopy = append(accCopy, acc...)
        *output = append(*output, accCopy)
        fmt.Println(output)
        return
    }

    if sum > target {
        return
    }

    for i := 0; i < len(candidates); i++ {
        combinationSum2(candidates[i:], output, target, append(acc, candidates[i]), sum+candidates[i])
    }
}

在我看来，这通常不太安全，但可以正常解决这个问题。

推荐阅读