时间戳

首页 > 解决方案 > 使用指针追加到切片 [][]int 时出错

go - 使用指针追加到切片 [][]int 时出错

问题描述

当我试图从 LC 解决一个问题“子集 II ”时，我遇到了一个奇怪的问题。该代码从给定的集合生成一个幂集。但是，当我运行代码时它失败了，因为其中一组不正确。

集合 [0,3,5,7] 被 [0,3,5,9] 替换（因此被附加两次）。

在将集合附加到 res 之前，我有一个打印语句（在代码中突出显示），它会打印正确的幂集。

我能想到的唯一问题是使用指针将值附加到切片中，但是由于它不会同时运行，我不明白为什么会有竞争条件。感谢有人能指出我的错误。

package main

import (
    "fmt"
    "sort"
)

func ValueCount( nums []int) map[int]int{
  hm := make(map[int]int)
  for _,v := range(nums){
    if c, ok := hm[v]; ok {
      hm[v] = c + 1
    }else{
      hm[v] = 1
    }
  }
  return hm
}

func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    res = append(res,[]int{})
    sort.Ints(nums)
  hashMap := ValueCount(nums)
  var t []int
  printTest(nums, t, &res, hashMap)
    return res
}


func printTest(nums []int, t []int, res *[][]int, hm map[int]int) {
  if len(nums) == 0 {
    return
  }
  for i:= 0; i < len(nums); {
    v := nums[i]
    x := nums[i:]
    for  k:= 0; k< hm[v]; k++ {
      var a,b []int
      for z:= 0; z<k+1; z++ { 
        a = append(t,x[z])
      }
      fmt.Println(a) // <--------- Prints the values that gets appended to res
      *res = append(*res, a)    
      b = a
      printTest(nums[i+hm[v]:], b, res, hm)
    }
    i += hm[v]
  }
  
}

func main(){
    n := []int{9,0,3,5,7}
    fmt.Println("Find the power set of:", n)
    fmt.Println(subsetsWithDup(n))
}

// [0,3,5,7] changes to 
// [0,3,5,9] in the output

标签： gopowerset

解决方案

使用（和重用）切片结果时要非常小心——尤其是在以后更改这些切片值时。由于切片具有支持数组，因此引用的数据可能会以非常意想不到的方式发生变化！

快速解决您的问题的方法是将切片结果复制到新切片。这确保了对原始切片的更改不会引入错误（尤其是在递归算法中）。

要复制切片：

func copyIntSlice(a []int) []int {
    c := make([]int, len(a))
    copy(c, a) // `a` can now grow/shrink/change without affecting `c`
    return c
}

只需从您的主代码中调用它：

aCopy := copyIntSlice(a)
*res = append(*res, aCopy)

printTest(nums[i+hm[v]:], aCopy, res, hm)

https://play.golang.org/p/1p8Z4sV9foQ

推荐阅读