當(dāng)我試圖從LC解決一個(gè)問(wèn)題“子集II”時(shí)，我遇到了一個(gè)奇怪的問(wèn)題。該代碼從給定的功率集生成一個(gè)功率集。但是，當(dāng)我運(yùn)行代碼時(shí)，它失敗了，因?yàn)槠渲幸粋€(gè)集合不正確。集合 [0，3，5，7] 被替換為 [0，3，5，9]（因此被追加兩次）。在將集合附加到 res 之前，我有一個(gè) print 語(yǔ)句（在代碼中突出顯示），它打印正確的功率集。我能想到的唯一問(wèn)題是使用指針將值附加到切片中，但是由于它不會(huì)同時(shí)運(yùn)行，我不明白為什么會(huì)出現(xiàn)爭(zhēng)用條件。如果有人能指出我的錯(cuò)誤，請(qǐng)表示贊賞。package mainimport ( "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
2 回答
猛跑小豬
TA貢獻(xiàn)1858條經(jīng)驗(yàn) 獲得超8個(gè)贊
該錯(cuò)誤發(fā)生在第 40 行：
a = append(t, x[z])
快速修復(fù)方法是更改此循環(huán)：for
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)
}
對(duì)此：
for k := 0; k < hm[v]; k++ {
var a, b []int
a = make([]int, len(t))
copy(a, t)
for z := 0; z < k+1; z++ {
a = append(a, 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)
}
這與Go如何使用切片作為數(shù)據(jù)結(jié)構(gòu)有關(guān)。當(dāng)內(nèi)置函數(shù)的第一個(gè)參數(shù)是切片參數(shù)時(shí)，它會(huì)復(fù)制一些對(duì)程序員來(lái)說(shuō)不直觀的切片內(nèi)部數(shù)據(jù)。然后，它修改了參數(shù)切片 和新創(chuàng)建的切片 。appendta
如果您有興趣了解更多信息，我建議您閱讀切片內(nèi)部。
完整程序已編輯：
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
a = make([]int, len(t))
copy(a, t)
for z := 0; z < k+1; z++ {
a = append(a, 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))
}
新輸出：
Find the power set of: [9 0 3 5 7]
[0]
[0 3]
[0 3 5]
[0 3 5 7]
[0 3 5 7 9]
[0 3 5 9]
[0 3 7]
[0 3 7 9]
[0 3 9]
[0 5]
[0 5 7]
[0 5 7 9]
[0 5 9]
[0 7]
[0 7 9]
[0 9]
[3]
[3 5]
[3 5 7]
[3 5 7 9]
[3 5 9]
[3 7]
[3 7 9]
[3 9]
[5]
[5 7]
[5 7 9]
[5 9]
[7]
[7 9]
[9]
[[] [0] [0 3] [0 3 5] [0 3 5 7] [0 3 5 7 9] [0 3 5 9] [0 3 7] [0 3 7 9] [0 3 9] [0 5] [0 5 7] [0 5 7 9] [0 5 9] [0 7] [0 7 9] [0 9] [3] [3 5] [3 5 7] [3 5 7 9] [3 5 9] [3 7] [3 7 9] [3 9] [5] [5 7] [5 7 9] [5 9] [7] [7 9] [9]]
aluckdog
TA貢獻(xiàn)1847條經(jīng)驗(yàn) 獲得超7個(gè)贊
使用（和重用）切片結(jié)果時(shí)要非常小心 - 特別是在以后更改這些切片值時(shí)。由于切片具有后備數(shù)組，因此引用的數(shù)據(jù)可能會(huì)以非常意外的方式更改！
問(wèn)題的快速解決方法是將切片結(jié)果復(fù)制到新切片。這可確保對(duì)原始切片的更改不會(huì)引入 bug（尤其是在遞歸算法中）。
復(fù)制切片：
func copyIntSlice(a []int) []int {
c := make([]int, len(a))
copy(c, a) // `a` can now grow/shrink/change without affecting `c`
return c
}
然后只需從您的主代碼中調(diào)用它：
aCopy := copyIntSlice(a)
*res = append(*res, aCopy)
printTest(nums[i+hm[v]:], aCopy, res, hm)
https://play.golang.org/p/1p8Z4sV9foQ
- 2 回答
- 0 關(guān)注
- 127 瀏覽
添加回答
舉報(bào)
0/150
提交
取消