有如下求全排列代码:
package main
import (
"fmt"
)
func main() {
res := permute([]int{5,4,6,2})
fmt.Println(res)
}
var result [][]int
func permute(nums []int) [][]int {
result = make([][]int,0)
track := make([]int,0)
trackBack(nums,track)
return result
}
func trackBack(nums []int, track []int) {
if len(track) == len(nums) {
//tmp := make([]int,len(nums))
//copy(tmp,track)
//result = append(result,tmp)
result = append(result,track)
return
}
for _,i := range nums {
// 已经在路径中的剪枝剪掉
if isInSlice(track,i) {
continue
}
track = append(track,i)
trackBack(nums,track)
track = track[:len(track)-1]
}
}
func isInSlice(nums []int,item int) bool {
for _,i := range nums {
if i == item {
return true
}
}
return false
}
运行结果如下:
[[5 4 2 6] [5 4 2 6] [5 6 2 4] [5 6 2 4] [5 2 6 4] [5 2 6 4] [4 5 2 6] [4 5 2 6] [4 6 2 5] [4 6 2 5] [4 2 6 5] [4 2 6 5] [6 5 2 4] [6 5 2 4] [6 4 2 5] [6 4 2 5] [6 2 4 5] [6 2 4 5] [2 5 6 4] [2 5 6 4] [2 4 6 5] [2 4 6 5] [2 6 4 5] [2 6 4 5]]
由于切片底层都是公用一份内存,修改子切片的值也会影响到父切片,所以正常的使用方式应该是在每次 append 的时候要使用一个 tmp 切片来 copy 一个复制的值,然后 append tmp 切片,不然结果里的值都将会是最后 append 的元素的值(因为它们都是公用的一份内存数据),但是这个问题比较诡异的地方是,他只有相邻的两两元素是一样的,不符合预期,有大佬遇到过类似的问题么?
1
vzard OP 找到原因了,是切片内存自动扩容和缩容的坑:
``` // The append built-in function appends elements to the end of a slice. If // it has sufficient capacity, the destination is resliced to accommodate the // new elements. If it does not, a new underlying array will be allocated. // Append returns the updated slice. It is therefore necessary to store the // result of append, often in the variable holding the slice itself: // slice = append(slice, elem1, elem2) // slice = append(slice, anotherSlice...) // As a special case, it is legal to append a string to a byte slice, like this: // slice = append([]byte("hello "), "world"...) func append(slice []Type, elems ...Type) []Type ``` 当 cap 不够的时候会自动扩容,当多次执行`track = track[:len(track)-1]`这样的操作之切片又会自动缩容,每次扩容和缩容都会导致底层数组的内存重新申请,每两次内存重新申请之前的 append 的值就会一样,增加日志可以验证: ``` Cap Before: 1, track: [5] Cap Before: 2, track: [5 4] Cap Before: 4, track: [5 4 6] Cap Before: 4, track: [5 4 6 2] Cap After: 4, track: [5 4 6] Cap After: 4, track: [5 4] Cap Before: 4, track: [5 4 2] Cap Before: 4, track: [5 4 2 6] Cap After: 4, track: [5 4 2] Cap After: 4, track: [5 4] Cap After: 2, track: [5] Cap Before: 2, track: [5 6] Cap Before: 4, track: [5 6 4] Cap Before: 4, track: [5 6 4 2] Cap After: 4, track: [5 6 4] Cap After: 4, track: [5 6] Cap Before: 4, track: [5 6 2] Cap Before: 4, track: [5 6 2 4] Cap After: 4, track: [5 6 2] Cap After: 4, track: [5 6] Cap After: 2, track: [5] Cap Before: 2, track: [5 2] Cap Before: 4, track: [5 2 4] Cap Before: 4, track: [5 2 4 6] Cap After: 4, track: [5 2 4] Cap After: 4, track: [5 2] Cap Before: 4, track: [5 2 6] Cap Before: 4, track: [5 2 6 4] Cap After: 4, track: [5 2 6] Cap After: 4, track: [5 2] Cap After: 2, track: [5] Cap After: 1, track: [] Cap Before: 1, track: [4] Cap Before: 2, track: [4 5] Cap Before: 4, track: [4 5 6] Cap Before: 4, track: [4 5 6 2] Cap After: 4, track: [4 5 6] Cap After: 4, track: [4 5] Cap Before: 4, track: [4 5 2] Cap Before: 4, track: [4 5 2 6] Cap After: 4, track: [4 5 2] Cap After: 4, track: [4 5] Cap After: 2, track: [4] Cap Before: 2, track: [4 6] Cap Before: 4, track: [4 6 5] Cap Before: 4, track: [4 6 5 2] Cap After: 4, track: [4 6 5] Cap After: 4, track: [4 6] Cap Before: 4, track: [4 6 2] Cap Before: 4, track: [4 6 2 5] Cap After: 4, track: [4 6 2] Cap After: 4, track: [4 6] Cap After: 2, track: [4] Cap Before: 2, track: [4 2] Cap Before: 4, track: [4 2 5] Cap Before: 4, track: [4 2 5 6] Cap After: 4, track: [4 2 5] Cap After: 4, track: [4 2] Cap Before: 4, track: [4 2 6] Cap Before: 4, track: [4 2 6 5] Cap After: 4, track: [4 2 6] Cap After: 4, track: [4 2] Cap After: 2, track: [4] Cap After: 1, track: [] Cap Before: 1, track: [6] Cap Before: 2, track: [6 5] Cap Before: 4, track: [6 5 4] Cap Before: 4, track: [6 5 4 2] Cap After: 4, track: [6 5 4] Cap After: 4, track: [6 5] Cap Before: 4, track: [6 5 2] Cap Before: 4, track: [6 5 2 4] Cap After: 4, track: [6 5 2] Cap After: 4, track: [6 5] Cap After: 2, track: [6] Cap Before: 2, track: [6 4] Cap Before: 4, track: [6 4 5] Cap Before: 4, track: [6 4 5 2] Cap After: 4, track: [6 4 5] Cap After: 4, track: [6 4] Cap Before: 4, track: [6 4 2] Cap Before: 4, track: [6 4 2 5] Cap After: 4, track: [6 4 2] Cap After: 4, track: [6 4] Cap After: 2, track: [6] Cap Before: 2, track: [6 2] Cap Before: 4, track: [6 2 5] Cap Before: 4, track: [6 2 5 4] Cap After: 4, track: [6 2 5] Cap After: 4, track: [6 2] Cap Before: 4, track: [6 2 4] Cap Before: 4, track: [6 2 4 5] Cap After: 4, track: [6 2 4] Cap After: 4, track: [6 2] Cap After: 2, track: [6] Cap After: 1, track: [] Cap Before: 1, track: [2] Cap Before: 2, track: [2 5] Cap Before: 4, track: [2 5 4] Cap Before: 4, track: [2 5 4 6] Cap After: 4, track: [2 5 4] Cap After: 4, track: [2 5] Cap Before: 4, track: [2 5 6] Cap Before: 4, track: [2 5 6 4] Cap After: 4, track: [2 5 6] Cap After: 4, track: [2 5] Cap After: 2, track: [2] Cap Before: 2, track: [2 4] Cap Before: 4, track: [2 4 5] Cap Before: 4, track: [2 4 5 6] Cap After: 4, track: [2 4 5] Cap After: 4, track: [2 4] Cap Before: 4, track: [2 4 6] Cap Before: 4, track: [2 4 6 5] Cap After: 4, track: [2 4 6] Cap After: 4, track: [2 4] Cap After: 2, track: [2] Cap Before: 2, track: [2 6] Cap Before: 4, track: [2 6 5] Cap Before: 4, track: [2 6 5 4] Cap After: 4, track: [2 6 5] Cap After: 4, track: [2 6] Cap Before: 4, track: [2 6 4] Cap Before: 4, track: [2 6 4 5] Cap After: 4, track: [2 6 4] Cap After: 4, track: [2 6] Cap After: 2, track: [2] Cap After: 1, track: [] ``` |