go - GoLang 中的 HouseRobber 编程任务中的错误

Question

问题陈述相当简单:

Given a list of integers return the maximum sum of non adjacentelements.

.例如 houseRobber([5,0,0,5]) => 10 和 houseRobber([2,1,2]) => 4

One solution I decided on has 2 parts:

1. 生成所有可行的索引列表

   (例如 [5,0,0,5] => [[0,2],[0,3],[1,3]])

2. 确定给定索引集的最大元素总和。

   (例如 [5,0,0,5],[[0,2],[0,3],[1,3]] => 10)

所以我开始实现我的解决方案。我已将脚本包设为主要包并包含一个我自己的失败测试，​​以便任何人都可以轻松地在自己的机器上自行运行它。

package main
import(
    "fmt"
)
/*
concat takes 2 arrays of integer arrays and concatonates them.
*/
func concat(a,b [][]int) [][]int{
    for _,k := range b{
        a = append(a,k)
    }
    return a
}
/*
helper takes an array of integers inGroup which have been included to a given
sub set and an integer lastHouse which is the maximum index for the array it 
returns the array of integer arrays representing all possible sets of indices 
for non adjacent elements including the indicies provided in inGroup.
*/
func helper(inGroup []int,lastHouse int) [][]int{
    if len(inGroup) == 0 {
        return concat(helper([]int{0},lastHouse),helper([]int{1},lastHouse))
    }
    highest := inGroup[len(inGroup)-1]
    if highest <= (lastHouse-3){
        return concat(helper(append(inGroup,highest+2),lastHouse),
                      helper(append(inGroup,highest+3),lastHouse))
    }
    if highest==lastHouse-2{
        return [][]int{append(inGroup,highest+2)}
    }
    return [][]int{inGroup}
}
/*
saturated is a wrapper function for the helper that does the heavy lifting. 
*/
func saturated(n int) [][]int{
    return helper([]int{},n-1)
}
/*
Given a list of integers and a list of indicies the subSetSum function returns 
the sum of the elements at the given indicies.
*/      
func subSetSum(values, indicies []int) int{
    ret := 0
    for _,k := range indicies{
        ret += values[k]
    }
    return ret
}
/*
houseRobber is the main method, taking an array of numbers and returning an integer, 
the max sum of non adjacent elements
*/
func houseRobber(nums []int) int{
    if(len(nums) == 0){
        return 0
    }
    if(len(nums) == 1){
        return nums[0]
    }
    combos := saturated(len(nums))
    temp := 0
    ret := 0
    bestCombo := 0
    for n,k := range combos{
        temp = subSetSum(nums,k)
        if temp > ret {
            ret = temp
            bestCombo = n
        }
    }
    fmt.Println(combos[bestCombo])
    return ret
}

func main(){
        houseRobber([]int{1,2,3,4,5,6,7,8,9,10,11,12,13,14})
        houseRobber([]int{1,2,3,4,5,6,7,8,9,10,11,12,13,
                  14,15,16,17,18,19,20,21,22,23,24,25,26})
}

打印:[1 3 5 7 9 12 13] & [1 3 5 7 9 11 13 15 17 20 23 25 25] 作为非相邻索引确定有最大总和。 但是等等!12 和 13 是相邻的!那是怎么发生的？唯一附加到 inGroup 数组的是最高 +2 和最高 +3，但是数组中既没有包含 10 也没有包含 11，那么 13 是如何到达那里的呢？此外，第二个结果末尾的额外 25 似乎也超出了我认为应该发生的范围。例如。如果仅附加 highest+2 和 highest+3 值，如何将 highest+0 附加到 inGroup？

Obviously this bug is causing some tests to fail but the problem isnot ubiquitous, as a majority of tests pass.

我确信这里有一个解释，但目前它正在逃避我。

Answer 1

您似乎在使用 append 函数时遇到了一个微妙的问题。

您不应像在函数中那样使用 append 创建新数组。

相反，复制它们并将值附加到复制的数组。

如果您将对 append 的调用替换为此处定义的 copyAndAppend:

func copyAndAppend(i []int, vals ...int) []int {
    j := make([]int, len(i), len(i)+len(vals))
    copy(j, i)
    return append(j, vals...)
}

您的代码似乎可以正常工作。

详情请看这里:

unexpected slice append behaviour